Breaking Down the Puzzles in ZK Hack IV

The Zellic cryptography team (Malte Leip, Mohit Sharma, and Avi Weinstock) and Sampriti Panda participated in the most recent ZK Hack competition, ZK Hack IV↗, consisting of three puzzles overall, with points determined by how fast one managed to solve it. We were happy to win the first puzzle and place second in the third one, securing a second place overall.

This ZK Hack’s puzzles consisted of small cryptographic applications written in Rust using the arkworks libraries↗. They combined the kind of cryptographic primitives that are typically used in projects surrounding ZK, but in each puzzle some kind of vulnerability was introduced as well. The task was then to understand the provided code, find the vulnerability theoretically, and then implement a solution leveraging the found vulnerability.

Puzzle 1: Gamma Ray

In the first puzzle, we were presented with parts of a small Zcash clone, the task being to double spend a note. Double spending is prevented in Zcash with the use of nullifiers; to spend a note, you must reveal a nullifier associated with that note, and this nullifier is then marked as used. Already used nullifiers are not allowed to be used anymore, so this prevents double spending as long as there is only one valid nullifier that can be computed for each note.

In the case of this puzzle, however, the relationship was roughly $nullifier = hash(secret)$ and $note = (secret\cdot basepoint).x$, where $basepoint$ is a point on an elliptic curve and $.x$ refers to the x-coordinate in affine coordinates. But if $(x,y)$ is a point in affine coordinates on this elliptic curve, then it holds that $-(x,y) = (x, -y)$ and thus has the same x-coordinate. Thus the note does not change if we replace $secret$ by $-secret$ (taken modulo the order of $basepoint$), but the hash changes, so we obtain a second nullifier associated with the note. A more detailed write-up can be found on the ZK Hack page for this puzzle↗.

This was our solution code:

let secret_hack = MNT4BigFr::from(MNT6BigFr::MODULUS) - MNT4BigFr::from(leaked_secret);
let nullifier_hack = <LeafH as CRHScheme>::evaluate(&leaf_crh_params, vec![secret_hack]).unwrap();

Puzzle 2: Supervillain

The second puzzle concerned a combination of aggregated BLS signatures with a simple proof-of-knowledge scheme. Both of those used a pairing $e: G_1 \times G_2 \to G_3$. We recently published an introductory article on pairings↗, so head over there if you would like an introduction.

In a sequence of signatures for a fixed hashed message $m\in G_2$, signature number $i$ is signed with a public key $pk_i$ of the form $pk_i = sk_i \cdot g$, with $g$ a fixed element of $G_1$. The signature is a normal BLS signature, so $sig_i = sk_i \cdot m$. Those can be aggregated with $sig = \sum_i sig_i$, $pk = \sum_i pk_i$ and then verified by checking $e(pk, m) = e(g, sig)$. That this equality follows from $e(pk_i, m) = e(g, sig_i)$, and that in turn these equalities hold, is a consequence of the bilinearity of $e$.

To prove that the signer actually knew $sk_i$, they can provide another elliptic curve element $pf_i$, and verification checks that $e(pk_i, i \cdot h) = e(g, pf_i)$, where $h\in G_2$ is a fixed element.

In the puzzle, we were then given a sequence of public keys and proofs $pk_1,\dots, pk_n$ and $pf_1,\dots,pk_n$ for which verification of the proof of knowledge of $sk_i$ succeeds (we do not get $sk_i$ though). Our task was to come up with $sk_{n+1}$ and $pf_{n+1}$, so that the proof-of-knowledge verification succeeds for this pair, and additionally a signature $sig$ that would verify as a BLS signature for a specific hashed message $m$ using the aggregate key $\sum_{i=1}^{n+1} pk_i$. This means our constraints were

$$e(pk_{n+1}, (n+1)\cdot h) = e(g, pf_{n+1})$$

and

$$e\left(\sum_{i=1}^{n+1} pk_i, m\right) = e(g, sig)$$

and we have available $e(pk_{i}, i\cdot h) = e(g, pf_{i})$ for $i\leq n$. The available equalities are usable for the first constraint but not the second, so to make the second one pass, we choose $pk_{n+1} = - \sum_{i=1}^{n} pk_i$ and $sig=0$, making both sides 0 by bilinearity¹. The left hand side of the first constraint can then be rewritten as follows.

$$\begin{align*} e(pk_{n+1}, (n+1)\cdot h) &= e\left( - \sum_{i=1}^{n} pk_i, (n+1)\cdot h\right) \\ &= - \sum_{i=1}^{n} e(pk_i, (n+1) \cdot h) \\ &= - \sum_{i=1}^{n} \frac{n+1}{i} e(pk_i, i \cdot h) \\ &= - \sum_{i=1}^{n} \frac{n+1}{i} e(g, pf_i ) \\ &= e\left(g, - \sum_{i=1}^{n} \frac{n+1}{i} pf_i\right) \end{align*}$$

The first constraint thus means that we must choose $pf_{n+1}$ in such a way that the following equality holds.

$$e\left(g, - \sum_{i=1}^{n} \frac{n+1}{i} pf_i\right) = e(g, pf_{n+1})$$

The puzzle is thus solved by using $pf_{n+1} = - \sum_{i=1}^{n} \frac{n+1}{i} pf_i$.

A more detailed write-up for this puzzle can again be found on its ZK Hack page↗.

This was our solution code:

let aggregate_rest = public_keys
    .iter()
    .fold(G1Projective::zero(), |acc, (pk, _)| acc + pk)
    .into_affine();
let new_key = aggregate_rest.neg();

let proofs_raw = public_keys
    .iter()
    .enumerate()
    .map(|(i, (_pk, proof))| *proof * Fr::from(i as u64 + 1).inverse().unwrap());
let proofs_add = proofs_raw.fold(G2Projective::zero(), |acc, el| acc + el).neg();
let new_proof = (proofs_add * Fr::from(new_key_index as u64 + 1)).into();

let aggregate_signature = G2Affine::zero();

Puzzle 3: Chaos Theory

In this puzzle, we again encountered BLS signatures, this time combined with ElGamal encryption. We were given an encrypted, authenticated message and had to find out which message it was, out of a small number of possibilities.

As in Puzzle 2, the sender has a secret key $sk_{send}$ with public key $pk_{send} = sk_{send} \cdot g$, and so does the receiver. The ElGamal ciphertext of the message $m$ is then given by $c = (pk_{send}, d)$ with $d = sk_{send}\cdot pk_{recv} + m$ (the receiver can decrypt by subtracting $sk_{send}\cdot pk_{recv} = sk_{recv}\cdot pk_{send}$ from $d$). The signature we are also provided is a BLS signature of a hash of the ElGamal ciphertext — so $s$ satisfying $e(g, s) = e(pk_{send}, hash(c))$.

We have a small number of possible messages $m'$ to check. To eliminate dependence on the message if we guessed correctly, we begin by considering $d - m'$, which will be $sk_{send}\cdot pk_{recv} = sk_{recv}\cdot pk_{send}$ in that case (and something different if $m' \neq m$). Thus, if $m' = m$, we will have

$$\begin{align*} &\phantom{=} e(d - m', hash(c)) \\ &= e( sk_{recv}\cdot pk_{send}, hash(c)) \\ &= sk_{recv}\cdot e(pk_{send}, hash(c)) \\ &= sk_{recv}\cdot e(g, s) \\ &= e(sk_{recv} \cdot g, s) \\ &= e(pk_{recv}, s). \end{align*}$$

While the middle steps above involve terms we do not know, we can check whether $e(d - m', hash(c)) = e(pk_{recv}, s)$. If this equality holds, then $m'=m$.

As with the other puzzles, a more detailed write-up can be found on its ZK Hack page↗.

This was our solution code:

for (i, msg) in messages.iter().enumerate() {
    let shared = blob.c.1 - msg.0;

    let lhs = { Bls12_381::pairing(shared, blob.c.hash_to_curve()) };
    let rhs = { Bls12_381::pairing(blob.rec_pk, blob.s) };

    if lhs == rhs {
        println!("Msg {i} is correct");
    }
}

Conclusion

We would like to thank ZK Hack for organizing this competition and Geometry Research for creating these three interesting puzzles.

About Us

Zellic’s dedicated zero-knowledge team combines a distinguished skill set in advanced cryptography, vulnerability research, and competitive hacking. We review circuits in Circom, Halo2, and other frameworks for zkEVMs, zkVMs, privacy and identity protocols, and interoperability infrastructure.

Notable clients include rollups (Scroll), coprocessors (Axiom), privacy primitives (Nocturne), and zk-bridges (Polyhedra).

Contact us↗ for a ZK audit.

Endnotes

1. I am writing $G_3$ additively here to simplify exposition. ↩