ZK HACK: 1st puzzle write up posted November 2021

Last Tuesday was the start of ZK HACK, a "7-week virtual event featuring weekly workshops and advanced puzzle solving competitions". All related to zero-knowledge proofs, as the name suggests. The talks of the first day were really good, and you can rewatch them here. At the end of the first day, a puzzle called Let's hash it out was released. This post about solving this puzzle.

The puzzle

The puzzle is a Github repo containing a Rust program. If you run it, it displays the following message:

Alice designed an authentication system in which users gain access by presenting it a signature on a username, which Alice provided. One day, Alice discovered 256 of these signatures were leaked publicly, but the secret key wasn't. Phew. The next day, she found out someone accessed her system with a username she doesn't know! This shouldn't be possible due to existential unforgeability, as she never signed such a message. Can you find out how it happend and produce a signature on your username?

Looking at the code, it looks like there's indeed 256 signatures over 256 messages (that are just hexadecimal strings though, not usernames).

The signature verification

The signatures are BLS signatures (a signature scheme that makes use of pairing and that I've talked about it here).

Looking at the code, there's nothing fancy in there. There's a verification function:

pub fn verify(pk: G2Affine, msg: &[u8], sig: G1Affine) {
    let (_, h) = hash_to_curve(msg);
    assert!(Bls12_381::product_of_pairings(&[
        (
            sig.into(),
            G2Affine::prime_subgroup_generator().neg().into()
        ),
        (h.into(), pk.into()),
    ])
    .is_one());
}

which pretty much implements the BLS signature verification algorithm to check that

$$ e(\text{sig}, -G_2) \cdot e(\text{h}, \text{pk}) = 1 $$

Note: if you read one of the linked resource, "BLS for the rest of us", this should make sense. If anything is confusing in this section, spend a bit of time reading that article.

We know that the signature is simply the secret key $sk$ multiplied with the message:

$$\text{sig} = [\text{sk}]h$$

The public key is simply the secret key $\text{sk}$ hidden in the second group:

$$\text{pk} = [\text{sk}]G_2$$

So the check gives us:

$$ \begin{align} & \;e([sk]h, -G_2) \cdot e(h, [sk]G2) \ =& \;e(h, G_2)^{-\text{sk}} \cdot e(h, G_2)^\text{sk} \ =& \;1 \end{align} $$

The hash to curve

Actually, the username is not signed directly. Since a signature is the first argument in the pairing it needs to be an element of the first group (so $[k]G_1$ for some value $k$).

To transform some bytes into a field element $k$, we use what's called a hash-to-curve algorithm. Here's what the code implements:

pub fn hash_to_curve(msg: &[u8]) -> (Vec<u8>, G1Affine) {
    let rng_pedersen = &mut ChaCha20Rng::from_seed([
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1,
    ]);
    let parameters = CRH::<G1Projective, ZkHackPedersenWindow>::setup(rng_pedersen).unwrap();
    let b2hash = blake2s_simd::blake2s(msg);
    (
        b2hash.as_bytes().to_vec(),
        CRH::<G1Projective, ZkHackPedersenWindow>::evaluate(¶meters, b2hash.as_bytes())
            .unwrap(),
    )
}

What I'm reading is that it:

1. initializes some collision-resistant hash function (CRH) from a hardcoded seed
2. uses the BLAKE2 hash function to hash the username (msg) into 256 bits.
3. Uses the CRH to hash the BLAKE2 digest into a group element

Looking at CRH, it's simply a Pedersen hashing (I've talked about that hash function here) that converts a series of bits $b_1, b_2, b_3, \cdots$ into

$$ [b_1]G_{1,1} + [b_2]G_{1, 2} + [b_3]G_{1, 3} + \cdots $$

where the $G_{1,i}$ are curve points that belongs to the first group (generated by $G_1$) and derived randomly via the hardcoded seed (in a way that prevents anyone from guessing their discrete logarithm).

What are we doing?

What are we looking for? We're trying to create a valid signature (maybe a signature forgery attack then?) on our own nickname (so more than just an existantial forgery, a chosen-message attack).

We can't change the public key (so no rogue key attack), and the message is fixed. This leaves us with the signature as the only thing that can be changed. So indeed, a signature forgery attack.

To recap, we have 256 valid signatures:

• $e(\text{sig}_1, -G_2) \cdot e(h(m_1), \text{pk}) = 1$
• $\vdots$
• $e(\text{sig}_{256}, -G_2) \cdot e(h(m_{256}), \text{pk}) = 1$

and we want to forge a new one such that:

$$ e(\text{bad_sig}, -G_2) \cdot e(h(\text{"my nickname"}), \text{pk}) = 1 $$

Forging a signature

Reading on the aggregation capabilities of BLS, it seems like the whole point of that signature scheme is that we can just add things with one another. So let's try to think about adding signatures shall we?

What happens if I add two signatures?

$$ \begin{align} &\; \text{sig}_1 + \text{sig}_2 \ =&\; [\text{sk}]h_1 + [\text{sk}]h_2 \end{align} $$

if only we could factor $sk$ out... but wait, we know that $h_1$ and $h_2$ are additions of the same curve points (by definition of the Pedersen hashing):

$$ \begin{align} &\; \text{sig}_1 + \text{sig}_2 \ =&\; [\text{sk}]h_1 + [\text{sk}]h_2 \ =&\; \text{sk}\ &\; + \text{sk} \end{align} $$

where the $b_{i}$ (resp. $b'_{i}$) are the bits of $h_1$ (resp. $h_2$). So the added signature are equal to the signature of the added bitstrings:

$$ [b_{1} + b'{1},\; b{2} + b'{2},\; b{3} + b'_{3},\; \cdots] $$

We just forged a signature! Now, that shouldn't mean much, because remember, these bits represent the output of a hash function and a hash function is resistant against pre-image attacks.

Wait a minute...

Our hash function is a collision-resistant hash function, but that's it.

Linear combinations

OK, so we forged a signature by adding two signatures. But we probably didn't get what we wanted, what we wanted is to obtain the bits $\tilde{b}_1, \tilde{b}_2, \tilde{b}_3, \cdots$ that represent the hashing of my own username.

Maybe if we add more signatures together we can get? Actually, we can use all the signatures and combine them. And not just by adding them, we can take any linear combination (we're in a field, not constrained by 0 and 1).

So here's the system of equations that we have to solve:

• $\tilde{b}_1 = x_1 b_1 + x_2 b'_1 + x_3 b''_1$
• $\vdots$
• $\tilde{b}_{256} = x_1 b_{256} + x_2 b'_{256} + x_3 b''_{256}$

Note that we can see that as solving $xA = b$ where each row of the matrix $A$ represents the bits of a digest, and $b$ is the bitvector of my digest (the hash of my username).

Once we find that linear combinations, we just have to apply it to the signatures to obtain a signature that should work on my username :)

$$ \text{bad_sig} = x_1 \text{sig}_1 + x_2 \text{sig}_2 + x_3 \text{sig}_3 + \cdots $$

Coding the answer

Because I couldn't find a way to solve a system of equations in Rust, I simply extracted what I needed and used Sage to do the complicated parts. Here's the Rust code that creates the matrix $A$ and the vector $b$:

// get puzzle data
let (_pk, ms, _sigs) = puzzle_data();

// here's my name pedersen hashed
let (digest_hash, _digest_point) = hash_to_curve("mimoo".as_bytes());

// what's that in terms of bits?
use ark_crypto_primitives::crh::pedersen::bytes_to_bits;
let bits = bytes_to_bits(&digest_hash);
let bits: Vec<u8> = bits.into_iter().map(|b| b as u8).collect();

// order of the subgroup of G1
println!("R = GF(0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001)");

// xA = b
print!("A = matrix(R, [");
for m in ms {
    let (digest, _point) = hash_to_curve(&m);
    let bits = bytes_to_bits(&digest);
    let bits: Vec<u8> = bits.into_iter().map(|x| x as u8).collect();
    print!("{:?}, ", bits);
}
println!("b = vector(R, {:?})", bits);

Note: the system of equation is over some field $R$. Why? Because eventually, the linear combination happens between curve points that are elements of the first group, generated by $G_1$, and as such are scalars that live in the field created by the order of the group generated by $G_1$.

In sage, I simply have to write the following:

x = A.solve_left(b)

and back in Rust we can use these coefficients to add the different signatures with one another:

let mut bad_sig = G1Projective::zero();
for (coeff, sig) in coeffs.into_iter().zip(sigs) {
    let coeff = string_int_to_field_el(coeff);
    bad_sig += sig.mul(coeff);
}

// the solution
verify(pk, "mimoo".as_bytes(), bad_sig.into());

It works!