Explanation for the zkhack puzzle

Supervillain.md

The Scenario

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...

Bob's Source Code

Bob's BLS signature scheme was exploited by a rogue public key attack. The attack was enabled because the protocol did not use fiat-shamir to simulate randomness. Below is a detailed account of the attack.

Pairings

Some elliptic curves have asymmetric groups $\mathbb{G}_1$ and $\mathbb{G}_2$ where there is an operation known as a pairing. Given $g_1 \in \mathbb{G}_1$ and $g_2 \in \mathbb{G}_2$, a pairing is denoted as $e(g_1,g_2)$ and produces an element in a 3rd group $\mathbb{G}_T$. Given a scalar $a$, an important equivalence is: $$e([a]g_1,g_2) = e(g_1,[a]g_2) = [a]e(g_1,g_2)$$

BLS Signatures

BLS signatures use pairings to provide aggregation and verification techniques. A message can be hashed to a group element $h$ and that element can then be signed and verified by comparing:

$$ e(pk, h) = e(g_1,[sk]h)$$

Its easy to see that this is equal if we rewrite it as:

$$e([sk]g_1, h) = e(g_1,[sk]h)$$

$$e([sk]g_1, h) = e([sk]g_1,h)$$

This same verification procedure works to aggregate signatures of many keypairs.

$$ e(\sum_{i=0}^{len(pk)} pk_i, h) = e(g_1, \sum_{i=0}^{len(sk)} [sk_i]h)$$

Bob's implementation provides a slight varient to these equations, but it is the same:

fn bls_verify(pk: G1Affine, sig: G2Affine, msg: &[u8]) {
    assert!(Bls12_381::multi_pairing(
        &[pk, G1Affine::generator()],
        &[hasher().hash(msg).unwrap().neg(), sig]
    )
    .is_zero());
}

$$ e(\sum_{i=0}^{len(pk)} pk_i, [-1]h) + e(g_1, \sum_{i=0}^{len(sk)} [sk_i]h) = 0 $$

With a slight transformation we can prove it is the same equation:

$$ [-1]e(\sum_{i=0}^{len(pk)} pk_i, h) + e(g_1, \sum_{i=0}^{len(sk)} [sk_i]h) = 0 $$

$$ e(\sum_{i=0}^{len(pk)} pk_i, h) = e(g_1, \sum_{i=0}^{len(sk)} [sk_i]h)$$

The Rogue Public Key Attack

A rogue public key attack is where with the knowledge of other public keys in the aggregate signature, one can craft a public key and secret key that will allow you to spoof the BLS signature validation.

The rogue public key ($rk$) can be derived using this formula where $pk$ is a list of other public keys in the signature:

$$rk = [sk]g_1 − \sum_{i=0}^{len(pk)}pk_i$$

Notice that $sk$ will not be a valid secret key for $rk$ (meaning $[sk]g_1 \not= rk$). It will, however, provide a way to sign a message with $sk$ and spoof the aggregate BLS signature validation.

let other_pks: G1Affine = public_keys
    .iter()
    .fold(G1Projective::zero(), |acc, (pk, _)| acc + pk)
    .into_affine();
let sk = Fr::from(100_u64); // Any key would work
let rogue_key = ((G1Affine::generator() * sk) - other_pks).into_affine();

With this secret key one can sign any message and verify it with all of the public keys:

let aggregate_signature = bls_sign(sk, message);
let aggregate_key = public_keys
    .iter()
    .fold(G1Projective::from(rogue_key), |acc, (pk, _)| acc + pk)
    .into_affine();

bls_verify(aggregate_key, aggregate_signature, message)

This works because the rogue public key negates all of the the other public keys, leaving only the secret key created in the rogue public key protocol. It can easily be seen based on the way that the rogue key is derived:

$$ e(rk + \sum_{i=0}^{len(pk)} pk_i, h) = e(g_1, [sk]h) $$

$$ e([sk]g_1 - \sum_{i=0}^{len(pk)} pk_i + \sum_{i=0}^{len(pk)} pk_i, h) = e(g_1, [sk]h) $$

$$ e([sk]g_1, h) = e(g_1, [sk]h) $$

$$ e([sk]g_1, h) = e([sk]g_1, h) $$

This attack should not be possible to do in this protocol because of the proof of key verification required. For every public key registered, there must be a proof that there is knowlege of the secret key which generated it. In order to exploit the protocol, one must find a way to find a valid proof for our rogue public key.

Fiat-Shamir

Many protocols rely on the concept of the Random Oracle Model for their security proofs. While in the real world there exists no such thing as a truely random oracle, we can simulate this using hash functions in a process call the Fiat-Shamir heuristic. If all previous pieces of public data are part a hash digest, the hash output can be used to simulate an random value.

In this implementation fiat-shamir is not implemented, and the random seed is set inside of the derive_point_for_pok function. G2Affine::rand(rng) will always be the same value.

fn derive_point_for_pok(i: usize) -> G2Affine {
    let rng = &mut ark_std::rand::rngs::StdRng::seed_from_u64(20399u64);
    G2Affine::rand(rng).mul(Fr::from(i as u64 + 1)).into()
}

This means that unlike a valid fiat-shamir implementation, the value of that function can be predicted ahead of time.

Producing a Rogue Key Proof

Now that it is known that that the base point in the proof-of-key protocol is not random, but rather fixed, it can be used to exploit the protocol and find a proof for a rogue public key.

Let $g_2$ be the generator used by all of the proof of key proceedures:

let rng = &mut ark_std::rand::rngs::StdRng::seed_from_u64(20399u64);
let g2 = G2Affine::rand(rng);

The proof formula is as follows:

$$pok_i = [i+1][sk]g_2$$

Remember the protocol used to generate the rogue key:

$$rk = [sk]g_1 − \sum_{i=0}^{len(pk)}pk_i$$

A similar formula can be used to spoof the proof-of-key protocol. Let $sk_i$ be the $i$ th secret key of the signature scheme. In order to create a fake proof, we have to find an answer to this equation.

$$ pok = [len(sk)+1]([sk]g_2 - \sum_{i=0}^{len(sk)} [sk_i]g_2) $$

Let $p_i$ represent the $i$ th proof. The above formula is equivilent to:

$$ pok = [len(p)+1]([sk]g_2 - \sum_{i=0}^{len(p)} ([(i+1)^{-1}]p_{i} ) $$

Since all of the proofs have the same base of $g_2$, one can get $\sum [sk_i]g_2$ by negating the $i+1$ part of the scalar multiplication in the proof:

let other_proofs = public_keys
    .iter()
    .enumerate()
    .fold(G2Projective::zero(), |acc, (i, (_, proof))| {
        acc + (proof.mul(Fr::from(i as u64 + 1).inverse().unwrap()))
    })
    .into_affine();

Now it is simple to obtain the proof for our rogue key:

let rogue_proof = ((g2 * sk) - other_proofs)
    .mul(Fr::from(new_key_index as u64 + 1))
    .into_affine();

pok_verify(rogue_key, new_key_index, rogue_proof);

Because the POK protocol did not correctly implement fiat-shamir, an attacker was able to implement the rogue public key exploit in a few steps:

1. Create a rogue public key which negates the other public keys in the signature scheme
2. Sign the message with the secret key from the rogue public key protocol
3. Spoof the POK protocol by deriving a valid proof from the proofs of other parties in the signature scheme