ZK Hack IV - Supervillain

This is the solution of the challenge “Supervillain” from ZK Hack IV . It was possible to forge a Proof of Possession of a private key used in BLS signature thanks to the linearity of the scheme.

Details

Author: Geometry research

Points: 904

Description

A good rogue must be able to complete the obstacle course within a specific amount of time.

Puzzle link

Solution

The scheme is using a BLS Multi-Signatures With Public-Key Aggregation. It uses $n$ private keys $x_i$ with their corresponding public keys $Q_i = x_i \cdot G$. The scheme signs a single message $m$.

While debugging the code I noticed that the code uses 9 existing public keys.

To solve the puzzle we are requested to create an additional public key with index 9. The aggregate public key is computed as the sum of all the public keys $Q = Q_0 + \ldots + Q_9$. To sign a message, each participants compute $\sigma_i = x_i\cdot H(m)$. Where $H$ is a hash function mapping a message to a point on the curve. Then the aggregate signature $\sigma$ should be computed as the sum of all the signatures: $$\sigma = \sum_{i=0}^9 \sigma_i$$

To verify the signature the following equality is checked: $$e(Q,-H(m)) + e(G, \sigma) \stackrel{?}{=} 0$$

The signature is considered as valid if the equality holds. A common pitfall of such implementation is that a malicious participant can choose their public key to be: $$\stackrel{\sim}{Q_9} = Q_9 - \sum_{i=0}^8 Q_i$$

This attack is called a rogue public-key attack. Then the attacker can claim that the other participant signed a message $m$ for the signature $\sigma = x_9\cdot H(m)$ even thought it was sign only by the attacker since:

$\begin{aligned} e(Q,-H(m)) + e(G, \sigma) &=& e(Q_9 - \sum_{i=0}^8 Q_i + \sum_{i=0}^8 Q_i ,-H(m)) + e(G, \sigma) \\ &=& e(Q_9, -H(m)) + e(G, x_9\cdot H(m)) \\ &=& e(x_9 \cdot G, -H(m)) + e(G, x_9\cdot H(m)) \\ &=& 0 \end{aligned}$

The verification pass. One way to prevent such attacks is to use a Proofs-of-Possession. This variant of this mechanism is implemented in the code and prevent applying directly the attack.

In the code, for a user $i$ (encoded on a usize variable), the proof of possession (POP) $\Pi_i$ uses a point $R$ on the same curve and is computed such that $\Pi_i = (i+1) \cdot x_i \cdot R$. The main difference here with the previous paper is that in the paper the POP is computed such that:

$$\Pi_i = H(<Q_i>) \cdot x_i \cdot R$$

The verification of the POP is a standard BLS verification: $$e(Q_i, -(i+1) \cdot R) + e(G, \Pi_i) \stackrel{?}{=} 0$$

Since the modified POP is linear, it is possible to forge a new POP for $i=10$ from the previous ones. We want to forge a proof $\Pi_{\mathrm{rogue}}$ for the previous rogue public key $\tilde{Q}_{9}$

$$\Pi_{\mathrm{rogue}}= 10 (x_9 - \sum_{i=0}^8 x_i) \cdot R = 10 x_9 \cdot R - 10 x_0 \cdot R- 10 x_1 \cdot R - \ldots$$

Since we already know the values $\Pi_0 = x_0 \cdot R, \Pi_1 = 2x_1 \cdot R, \Pi_2 = 3x_2 \cdot R, \ldots$ from the previous POPs we can compute $\Pi_{\mathrm{rogue}} = 10 x_9 \cdot R - 10\sum (i+1)^{-1} \Pi_i$ and it will pass the POP verification. The public key is not check to be the point to infinity thus we can even simplify the solution by using $x_9 = 0$. In this case $\stackrel{\sim}{Q_9} = -\sum_{i=0}^8 Q_i$ and the signature will be zero for any message. The corresponding Rust code to build the rogue proof is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/* Rogue proof */
let one: Fr = MontFp!("1");
let mut index: Fr = one;
for n in 0..public_keys.len() {
    let tmp = index.inverse().unwrap();
    new_proof = new_proof.add(public_keys[n].1.mul(tmp));
    index = index + one;
}
let ten: Fr = MontFp!("10");
let new_proof = (new_proof.neg() * ten).into_affine();

Finally we can compute the rogue public key and the signature in Rust:

1
2
3
4
5
6
7
8

/* Rogue public key */
for n in 0..public_keys.len() {
    new_key = new_key.add(public_keys[n].0);
}
let new_key = new_key.neg().into_affine();

/* Signature */
let aggregate_signature = G2Affine::zero();

Here is my repository solution. you can verify to run properly by running:

1

$ cargo run -r