Write-up for ZK Hack IV puzzle F2: Supervillain

Author: Nicolas IOOSS
Date: 2024-01-24
Puzzle: https://zkhack.dev/zkhackIV/puzzleF2.html, https://github.com/ZK-Hack/puzzle-supervillain

1. Subject

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

This subject involves many notions which could be hard to understand: BLS signatures, B-KEA assumption... Let's start from the Rust code to understand what Bob's signature scheme does.

2. Public keys on BLS12-381

Bob's signature scheme was implemented in a Rust containing a single source file, src/main.rs. Function main starts by loading something from a file (line 71):

let public_keys: Vec<(G1Affine, G2Affine)> = from_file("public_keys.bin");

Types G1Affine and G2Affine are imported from ark_bls12_381. This Rust crate documents:

This library implements the BLS12-381 curve generated by Sean Bowe. The name denotes that it is a Barreto-Lynn-Scott curve of embedding degree 12, defined over a 381-bit (prime) field.

People familiar with ZK Hack already encountered this curve several times in past editions, including in the very first puzzle.

This write-up will focus on the properties of BLS12-381 which are actually used in the puzzle:

There are actually two curves in BLS12-381, named $G_1$ and $G_2$. They are generated by two points, $g_1$ and $g_2$, which share the same prime order $r$ = 52435875175126190479447740508185965837690552500527637822603658699938581184513. The curves use the same scalar field $\mathbb{F}_r$.
Points on these curves can use several coordinate systems. In Rust, the types G1Affine, G1Projective, G2Affine and G2Projective represent points on the curves using affine coordinates and projective coordinates.
There exists a bilinear pairing function $e: G_1 \times G_2 \rightarrow G_T$ which combines points on $G_1$ and $G_2$ into an element of group $G_T$. In Rust, function pairing from trait ark_ec::pairing::Pairing provides this function and function multi_pairing is used to compute several pairings in an efficient way.

As Arkworks is using the additive notation for groups, this write-up will also use them: the product of a point $P$ with a scalar $s$ is written $[s]P$ instead of $P^s$.

A signature scheme on curves such as BLS12-381 can be designed with the pubclic key being either in $G_1$ or in $G_2$ (both options work fine, but a scheme needs to choose which one is used). To find out what signature the puzzle uses, let's see what functions bls_sign and bls_verify are doing (lines 48-58):

fn bls_sign(sk: Fr, msg: &[u8]) -> G2Affine {
    hasher().hash(msg).unwrap().mul(sk).into_affine()
}

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());
}

These functions read as follow:

To sign a message $msg$ with the secret key $sk \in \mathbb{F}_r$, bls_sign first maps it to a point on curve $G_2$ with a hash-to-point function. The signature is $sig = [sk]Hash(msg) \in G_2$.
To verify the signature $sig$ of message $msg$ with the public key $pk \in G_1$, bls_verify verifies that $e(pk, -Hash(msg)) + e(g_1, sig) = 0_{G_T}$. This is equivalent to verifying that $e(pk, Hash(msg)) = e(g_1, sig)$.

This works if the secret key $sk \in \mathbb{F}_r$ is associated with the public key $pk = [sk]g_1 \in G_1$.

3. Some proofs of knowledge

After function main loads some public keys, it calls pok_verify on each of them (lines 73-76):

public_keys
    .iter()
    .enumerate()
    .for_each(|(i, (pk, proof))| pok_verify(*pk, i, *proof));

The verification function is (lines 30-36):

fn pok_verify(pk: G1Affine, i: usize, proof: G2Affine) {
    assert!(Bls12_381::multi_pairing(
        &[pk, G1Affine::generator()],
        &[derive_point_for_pok(i).neg(), proof]
    )
    .is_zero());
}

This function verifies that $e(Pk_i, -R_i) + e(g_1, \pi_i) = 0_{G_T}$, with:

$R_i \in G_2$ being the result of derive_point_for_pok(i),
$(Pk_i, \pi) \in G_1 \times G_2$ being Rust variables named pk and proof for each item of public_keys.

Using the bilinearity property of $e$, this equation is equivalent to:

$$e(Pk_i, R_i) = e(g_1, \pi_i)$$

Why is this function verifying this? The subject contains a link to the Sapling security analysis paper by Mary Maller. This analysis defined the B-KEA assumption (Bilinear Knowledge-of-Exponent Assumptions) in a way which helps understanding the equation. If $Pk_i$ is associated with the secret key $sk_i \in \mathbb{F}_r$ (meaning: $Pk_i = [sk_i]g_1$), the B-KEA assumption states that $\pi_i = [sk_i]R_i$.

This is a possible way for the party $i$ to prove the knowledge of secret key $sk_i$ in a Zero-Knowledge way. For this to be a sound argument of knowledge, some properties need to be guaranteed on $R_i$ and this write-up will not attempt to prove the robustness of this protocol. Instead, let's assume that $\pi_i = [sk_i]R_i$ in the provided data, as the other parties are assumed to be honest.

What is $R_i$?

Function derive_point_for_pok is defined as (lines 21-24):

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 function generates a deterministic random point $R \in G_2$ and computes $R_i = [i + 1]R \in G_2$. $R$ is generated by sampling a $x$ coordinate and trying to craft a point for it (in function Distribution<Affine<P>>::sample). This construction ensures that no one knows the discrete logarithm of $R$ (which is the number $\rho \in \mathbb{F}_r$ such that $R = [\rho]g_2$) and this property is useful to prove that some protocols are secure.

To summarize, function main starts by loading some pairs $(Pk_i, \pi_i)$ and verifies that $\pi_i = [sk_i]R_i = [sk_i (i + 1)]R$ with $Pk_i = [sk_i]g_1$ without actually knowing $sk_i$. Such a verification can be understood as a proof-of-possession scheme (POP), which aims at verifying that each party $i$ knows $sk_i$.

4. Aggregating signatures

After loading the public keys, function main lets the attacker define their own public key new_key and proof new_proof, verifies the proof with function pok_verify, computes an aggregation public key (named aggregate_key) and verifies that the attacker can forge a valid signature for an arbitrary message with this public key.

To translate this into mathematics, let's introduce more notations:

$n$ is the number of public keys which were loaded. In Rust, this is new_key_index = public_keys.len().
$Pk_n$ and $\pi_n$ are variables new_key and new_proof.
$Apk$ is the aggregation public key.
$msg$ is a message to be signed and $sig$ its signature verifiable with $Apk$.

Function main:

calls pok_verify to verify $\pi_n = [sk_n(n + 1)]R$ with some $sk_n$ such that $Pk_n = [sk_n]g_1$,
computes: $$Apk = \sum_{i=0}^n Pk_i$$
calls bls_verify to verify $sig = [ask]Hash(msg)$ with $ask \in \mathbb{F}_r$ the aggregation secret key such that $Apk = [ask]g_1$.

Can we compute $ask$? The aggregation public key is:

$$Apk = \sum_{i=0}^n Pk_i = \sum_{i=0}^n [sk_i]g_1 = \left[\sum_{i=0}^n sk_i\right]g_1$$

Therefore (with Elliptic-Curve Discrete Logarithm property):

$$ask = \sum_{i=0}^n sk_i$$

Computing this secret key requires the cooperation of all signers, which is unlikely. Nonetheless, the equation of the signature becomes:

$$sig = [ask]Hash(msg) = \sum_{i=0}^n [sk_i]Hash(msg)$$

This signature is the sum of the signature of the message using each key! It can be computed by making each party sign the message and adding each signature.

This is a BLS signature aggregation scheme: signing a message with the aggregation key should require all parties to perform the signature with their own key $sk_i$. Nevertheless, there seems to be a vulnerability somewhere enabling a party to craft a valid signature without involving any other party!

5. The rogue key attack

The previous sections presented a BLS signature aggregation scheme. In this scheme, the aggregation public key is the sum of the public keys of earch party. Can the last party cheat by adding a key which would "cancel" the other keys in some way? Yes, by using:

$$Pk_n = -\sum_{i=0}^{n-1} Pk_i$$

Doing so, the sum of all $Pk_i$ becomes $Apk = O_{G_1}$ (the point at infinity of curve $G_1$) and the aggregation secret key is $ask = 0$. Attacking the scheme this way is very visible and protocols could have countermeasures detecting the unexpected use of zero as a secret key.

To make the attack less visible (and more difficult to detect and defend against), an attacker can choose a value $\alpha \in \mathbb{F}_r$ and make the aggregation secret key be this value.

$$\alpha = ask = \sum_{i=0}^n sk_i = sk_n + \sum_{i=0}^{n-1} sk_i$$

$$sk_n = \alpha - \sum_{i=0}^{n-1} sk_i$$

This secret key cannot be computed because the attacker does not know the other $sk_i$.

Nevertheless, their public key is:

$$Pk_n = [sk_n]g_1 = \left[\alpha - \sum_{i=0}^{n-1} sk_i\right]g_1 = [\alpha]g_1 - \sum_{i=0}^{n-1} Pk_i$$

As all other public keys are known, this can be computed.

The proof of knowledge of $sk_n$ is:

$$\pi_n = [sk_n]R_n = \left[\alpha - \sum_{i=0}^{n-1} sk_i\right]R_n = [\alpha]R_n - \sum_{i=0}^{n-1} [sk_i]R_n$$

This seems impossible to compute without knowing $sk_i$. However, using equations $R_n = [n + 1]R$ and $\pi_i = [sk_i (i + 1)]R$ enables to simplify this further. By introducing $(i + 1)^{-1}$ as the inverse of $i + 1$ in field $\mathbb{F}_r$.

$$[sk_i]R_n = [sk_i (n + 1)]R = \left[sk_i (n + 1) (i + 1) (i + 1)^{-1}\right]R = \left[(i + 1)^{-1} (n + 1)\right]\pi_i$$

Therefore:

$$\pi_n = [\alpha]R_n - \sum_{i=0}^{n-1} \left[(i + 1)^{-1} (n + 1)\right]\pi_i$$

The attacker can compute a proof $\pi_n$ about knowing $sk_n$ without actually knowing it! This is a vulnerability, possible thanks to the way $R_i$ is built.

To finally prove that the attacker can sign any message, the aggregation secret key $ask = \alpha$ can be directly used.

Here is a Rust implementation of this attack.

// Add to the top of src/main.rs: use ark_ff::Field;
// In function main:
    /* Enter solution here */
    let alpha = Fr::from(0xcafe_u64);
    let new_key = public_keys
        .iter()
        .fold(G1Affine::generator().mul(alpha), |acc, (pk, _)| acc - pk)
        .into_affine();
    let new_proof = public_keys
        .iter()
        .enumerate()
        .map(|(i, (_, proof))| {
            proof
                .mul(Fr::from(i as u64 + 1).inverse().unwrap() * Fr::from(new_key_index as u64 + 1))
        })
        .fold(
            derive_point_for_pok(new_key_index).mul(alpha),
            |acc, term| acc - term,
        )
        .into_affine();
    let aggregate_signature = bls_sign(alpha, message);
    /* End of solution */

    pok_verify(new_key, new_key_index, new_proof);
    let aggregate_key = public_keys
        .iter()
        .fold(G1Projective::from(new_key), |acc, (pk, _)| acc + pk)
        .into_affine();
    bls_verify(aggregate_key, aggregate_signature, message)

Conclusion

The puzzle implements a scheme to aggregate signatures of a message with several public keys. However, the last party is able to craft a rogue key enabling to fully control the aggregation secret key and to sign messages with it as if there were signed by all parties.

This is possible because of a vulnerability in the proof-of-possession scheme. Each party $i$ computes a proof $\pi_i$ that they know their secret key $sk_i$ and the last one is able to compute $\pi_n$ for a key $Pk_n$ which cancels all other keys without actually knowing $sk_n$.

niooss-ledger/zkhack2024_IV_puzzleF2_writeup.md