# Write-up for ZK Hack IV puzzle 2: Super Villain

writeup.md

Write-up for ZK Hack IV puzzle 2: Super Villain

Purpose

This puzzle is about forging an aggregate key in order to validate a malicious message.

Bob has been designing a new optimized signature scheme for his L1 based on BLS signatures. Specifically, he wanted to be able to use the most efficient form of BLS signature aggregation, where you just add the signatures together rather than having to delinearize them. In order to do that, he designed a proof-of-possession scheme based on the B-KEA assumption he found in the the Sapling security analysis paper by Mary Maller [1]. Based the reasoning in the Power of Proofs-of-Possession paper [2], he concluded that his scheme would be secure. After he deployed the protocol, he found it was attacked and there was a malicious block entered the system, fooling all the light nodes...

[1] https://github.com/zcash/sapling-security-analysis/blob/master/MaryMallerUpdated.pdf [2] https://rist.tech.cornell.edu/papers/pkreg.pdf

Details

The signature scheme can be divided into two parts.

1. Every signer submit their public key and sign a specific message.

The specific message is just the index of each signer, from 1 to num_signer. When signing the message, every signer picks up a random G2 point, then multiply it withindex. In addition, they multiply the result with their own secret key.

To verify their signatures, a verifier do a batch check to see whether

$e(pk_i, -sig_i) \cdot e(G_1, proof_i) = 1$

By definition, we have:

1. $sig_i = [index \cdot rand_i] G_2$
2. $proof_i = [index \cdot rand_i \cdot sk_i] G_2$
3. $pk_i = [sk_i] G_1$

Thus the first equation can be expanded as:

$e(pk_i, -sig_i) \cdot e(G_1, proof_i) = e([sk_i]G_1, [-index \cdot rand_i]G_2) \cdot e(G_1, [index \cdot rand_i \cdot sk_i] G_2)$

By definition of bilinear pairing, we have:

$e([a]G_1, [b]G_2) = e(G_1, G_2)^{a \cdot b} = e(G_1, G_2)^a \cdot e(G_1, G_2)^b$

Then we have:

$e([sk_i]G_1, [-index \cdot rand_i]G_2) \cdot e(G_1, [index \cdot rand_i \cdot sk_i] G_2) = \e(G_1, G_2)^{- sk_i \cdot index \cdot rand_i} \cdot e(G_1, G_2)^{sk_i \cdot index \cdot rand_i} = 1$

The first equation is satisfied.

2. Use BLS key aggregation to aggregate all public keys and verify the signed (same) message

The BLS signature aggregation scheme is very similar to the above multi signer scheme. First, every signer sign the same message with their own secret keys.

$bls_sig_i = [sk_i]G_2(H(M))$

where $[sk_i] G_1 = pk_i$

Then verify all the signatures in aggregation form:

$e(\sum pk_i, -G_2(H(M))) \cdot e(G_1, \sum bls_sig_i)) = 1$

The validity of the above equation can be easily proven according to Step 1 prove process.

Hack

To hack the BLS signature aggregation scheme, we can make up a forged key to be added in the key aggregation step. If our forged key can cancel out all other signers' keys, then the scheme can be hacked easily.

That means our key should have the form $key_f = - \sum sk_i + sk_f$. When it gets aggregated, it will cancel others' keys via:

$bls_sig_f = [sk_f]G_2(H(M_2))$

$e([\sum sk_i + key_f]G_1, -G_2(H(M_2))) \cdot e(G_1, bls_sig_f) \ = e(\sum pk_i + [sk_f]G_1, -G_2(H(M_2))) \cdot e(G_1, bls_sig_f) = 1$

($H(M_2)$ means another malicious message instead of the original message $M$ which was signed by all other signer)

The above attack equation looks viable, but how to insert our forged $key_f$ into the public keys list? Since our forged $key_f$ needs to know all other signers $sk_i$, at first glance it is impossible to make our $key_f$ valid in the proofs of possession check.

It turns out that if we know all the proofs and their corresponding indexes in Step 1, it is easy to

forge a new proof for our $sk_f$, we don't need to forge a proof for $key_f$. The steps are described below:

1. for every $proof_i$, we aggregate it into our $old_proof_f$:

   $old_proof_f = \sum proof_i \cdot \frac{new_index}{i} \ = \sum [new_index \cdot rand_i \cdot sk_i]G_2 = new_index \cdot \sum [rand_i \cdot sk_i] G_2$

2. our new index proof can be derived as:

   $new_proof_f = [new_index \cdot rand_f \cdot sk_f] G_2 - old_proof_f \ = new_index \cdot [rand_f \cdot sk_f - \sum rand_i \cdot sk_i]G_2$

3. since proofs of possession check is a pairing check, our $new_proof_f$ can happily cancel out all other proofs:

   $e([key_f]G_1, -[new_index \cdot rand_f]G_2) \cdot e(G_1, new_proof_f) \ = e(G_1, G_2)^{(\sum sk_i- sk_f) \cdot new_index \cdot rand_f + new_index \cdot (rand_f \cdot sk_f) - \sum new_index \cdot rand_i \cdot sk_i } \= 1$

This satisfies our goal.