Introduction

I will try to demonstrate what rogue key attack is by ZK HACK IV puzzle Supervillain. see the repo

Puzzle Legend:

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. Based the reasoning in the Power of Proofs-of-Possession paper, 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...

If you want to have a try yourself(I really suggest that) visit the puzzle page.

Setup and Hints

BLS signatures

As follows from the BLS paper:

The BLS signature scheme operates in a prime order group and supports simple threshold signature generation, threshold key generation, and signature aggregation. To review, the scheme uses the following ingredients:

A bilinear pairing:

$$$
e: \ G_0 \times G_1 \to G_T
$$$

The pairing is efficiently computable, non-degenerate, and all three groups have prime order q. We let g_0 and g_1 be generators of G_0 and G_1 respectively.

No worries if it's not clear right away, just focus on the special property of pairing that we are looking for: Imagine you have two powerful energy crystals. One crystal belongs to G_0(yellow), and the other belongs to G_1(purple). When you combine these crystals in a special magic device(here pairing function e comes into play), it creates an amazing energy burst:

Now, here's the twist: if you double the energy in the purple crystal or the yellow crystal before combining them, the energy burst you get is also twice as powerful. This works with any number you choose to multiply the crystals' energies with.

This energy combination is easy to perform (efficiently computable), always produces a unique burst for different energy levels (non-degenerate), and the number of different energy levels for the crystals and bursts is a big prime number q.

The main idea is that we can move the amount of energy (scalar) we use to amplify the crystals around, and the result (energy burst) will still be correct. This special property is what makes the bilinear pairing so incredible and useful!

A hash function:

$$$
H: \ M \to G_0
$$$

The so-called hash to group function converts any message into a unique element of a specific group.

Following the metaphor, imagine a high-tech scanner that, when given a piece of information (message), generates a unique yellow crystal with specific energy properties from the yellow energy collection (G_0). This special scanner ensures that each piece of information always produces the same unique crystal.

Now the BLS signature scheme is defined as follows:

• Key Generation (KeyGen):

  1. Choose a random secret key:

  $$$
  sk = \alpha \in \mathbb{Z}_q
  $$$

  1. Compute public key:

  $$$
  pk = g_1^\alpha \in G_1
  $$$

• Signing (Sign): Given a secret key $$sk$$ and a message $$m$$,

  1. Output the signature:

  $$$
  \sigma = H(m)^\alpha \in G_0

  $$$

  *The signature is a single group element.

• Verification (Verify): Given a public key $$pk$$, a message $$m$$, and a signature $$\sigma$$,

  1. Check:

  $$$
  e(g_1, \sigma) = e(pk, H(m))
  $$$

  1. Since

  $$$
  \sigma = H(m)^\alpha \ pk = g_1^\alpha
  $$$

  1. We have:

  $$$
  e(g_1, H(m)^\alpha) = e(g_1^\alpha, H(m))
  $$$

  Remember the special property of the bilinear pairing: it allows us to move the exponent (in this case, $$\alpha$$) around.

  And allow us to check that:

  $$$
  e(g_1, H(m)^\alpha) = e(g_1^\alpha, H(m))
  $$$

  This property is what lets us verify the signature, ensuring that it was created using the corresponding secret key.

• Signature Aggregation: Given multiple triples $$(pk_i, m_i, \sigma_i)$$ for $$i = 1, \ldots, n$$, anyone can aggregate the signatures

  $$$
  \sigma_1, \ldots, \sigma_n \in G_0
  $$$

  into a single aggregate signature $$\sigma'$$ by computing their sum

  $$$
  \sigma' = \sigma_1 + ... + \sigma_n \in G_0
  $$$

  Public key aggregation works the same

  $$$
  pk' = pk_1 + ... + pk_n
  $$$

  To verify an aggregate signature $$\sigma'$$, check if

  $$$
  e(g_1, \sigma') = e(pk', H_0(m_1))
  $$$

Here's code snippet from puzzle that shows public key aggregation:

let aggregate_key = public_keys
    .iter()
    .fold(G1Projective::from(new_key), |acc, (pk, _)| acc + pk)
    .into_affine();

One more concept we need before the attack explanation is modular inverse (additive in our case).

Rogue key attack

The rogue key attack exploits the fact that the aggregated signature and the aggregated public key are simply the sums of all individual keys. By carefully creating a new key (called the rogue key), we can negate the contributions of the honest keys.

As was shown in previous section aggregated public key and signature is just a summs of corresponding elements.

let aggregate_key = public_keys
    .iter()
    .fold(G1Projective::from(new_key), |acc, (pk, _)| acc + pk)
    .into_affine();

To start forging, we need to create initial keypair:

• Let our secret key be zero(we will use it to sign malicious message): $$sk = 0$$

• Thus the corresponding public key will be:

  $$$
  pk' = g_1^0 \in G_1
  $$$

let new_secret: Fr = Fr::zero();

To negate the contributions of honest participants keys, we need to find a starting point on this cycle such that the sum of steps will lead us back to our public key

$$$
pk' = g_1^0
$$$

let honest_aggregated_pk = public_keys
    .iter()
    .fold(G1Projective::zero(), |acc, (pk, _)| acc + pk);

// create rogue key
let new_key = G1Affine::generator()
    .mul(new_secret) // pk = g1^sk = g1^0
    .sub(honest_aggregated_pk.clone()) // find point that negates all honest keys
    .into_affine();

This starting point is our "negation key" or "rogue key". When we add this rogue key to the aggregated key, it cancels out the contributions of all other keys and make aggregated key equal $$g_1^0$$.

$$$
(rogue \ public \ key) \ pk_r = pk' - pk_1 - ... - pk_n
$$$

And thats basically it! As for the signature forging we do pretty much the same:

1. Sign the malicious message (e.g. invalid block header) m_r with zero secret key

   $$$
   sk = 0 \ \sigma' = H(m_r)^0
   $$$

2. Find inverse of honest signatures sum:

   $$$
   (rogue \ signature) \ \sigma_r = \sigma' - \sigma_1 - ... - \sigma_n
   $$$

Finally we have m_r, pk_r, \sigma_r that we can use to convince third party that malicious message m_r is signed by all participans:

$$$
Aggregated \ key: \ pk_1 + ... + pk_n + pk_r = pk' = g_1^0 \ \ \ Aggregated \ signature: \ \sigma_1 + ... + \sigma_n + \sigma_r = \sigma' = H(m_r)^0
$$$

Verification looks as follows:

$$$
e(g_1, \sigma') = e(pk', H(m)) \ \ \ e(g_1, H(m)^0) = e(g_1^0, H(m))
$$$

In puzzle context we do not need to calculate negation signature since aggregation (by legend) is done on attackers end. Thus we can simply sign message with $$sk = 0$$ and use it ($$H(m)^0$$).

let aggregate_signature = bls_sign(new_secret, message);

Rogue key attack specific ends here, now we only need one last piece to solve the whole puzzle.

Hacking Proof of Secret Key Knowledge

According to the puzzle legend:

Bob designed a proof-of-possession scheme based on the B-KEA assumption he found in the Sapling security analysis paper by Mary Maller.

In this scheme, each participant should provide proof of knowledge of the secret key corresponding to their public key, which will be used for aggregation:

#[allow(dead_code)]
fn pok_prove(sk: Fr, i: usize) -> G2Affine {
    derive_point_for_pok(i).mul(sk).into()
}

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

To create such a proof, we need to:

1. Call derive_point_for_pok(i) to get a point for index i, where i is an index in a global list of participants. Note that the RNG is seeded every time we call the function (with the same seed).

2. Multiply the derived point by the secret key sk_i.

The problem is that we don't know the secret key that corresponds to the rogue key pk_r (and there is no way to compute the secret key directly from the public key). Let's denote it as sk_r.

Note that since the rogue public key

$$$
pk_r = g_1^{sk_r}
$$$

is an inverse of the sum of honest keys, its corresponding secret key sk_r is an inverse of the sum of honest secret keys.

Fortunately, we have a list of all honest participants $$(pk_i, proof_i)$$ pairs where:

$$$
pk_i = g_1^{sk_i} \ \ \ \text{proof}_i = r^{(i+1) \cdot sk_i}
$$$

Forging the Proof

It follows that since pk_r is an additive inverse of the sum of honest public keys, sk_r itself is an inverse of the sum of honest secret keys:

$$$
s_{k_r} = -(\sum_{j=0}^{i}sk_j)
$$$

Thus, the proof we are looking for might be denoted as follows:

$$$
proof_r = r^{(idx+1) \cdot (-\sum_{j=0}^{i}sk_j)}
$$$

Where $$idx$$ is a new key index and $$r$$ is the same value that we get from the pre-seeded RNG function. (We already know both these values.)

In order to get the remaining part of the equation, which is

$$$
r^{-\sum_{j=0}^{i}sk_j}
$$$

we should "remove" other indexes from honest proofs like this:

$$$
r^{(i+1) \cdot sk_i \cdot (-1 \cdot (i+1))} = r^{sk_i}
$$$

After that, we will be able to add these parts together and negate the result to get the final piece of the equation we need:

$$$
r^{sk_r} = r^{-\sum_{j=0}^{i}sk_j}
$$$

The last step will be to multiply $$r^{sk_r}$$ by our new key index $$idx + 1$$ to get proof of knowledge of sk_r:

$$$
proof_r = r^{(idx+1) \cdot sk_r}
$$$

SK POK Forging Plan

Let's recap the plan step by step:

1. Clear the index multiplier $$i+1$$ from every proof we have.

2. Add the cleaned elements together.

3. Negate the sum to get the additive inverse.

4. Multiply it by our new key index.

Here's how this is implemented in the code:

let new_proof = public_keys
    .iter()
    .enumerate()
    .fold(G2Projective::zero(), |acc, (i, (_, proof))| {
        let inverse_factor = Fr::from(i as u64 + 1).inverse().unwrap();
        acc + proof.mul(inverse_factor)      // clear idx factor
    })
    .mul(Fr::from(new_key_index as u64 + 1)) // multiply by new_key_index to follow proof generation
    .neg()                                   // negate
    .into_affine();

Congratulations! We have successfully forged the multisignature and bypassed the KOSK assumption in the Supervillain puzzle. 🎉🦹‍♂️

To learn more about how to defend against rogue key attacks and dive deeper into how BLS works follow original paper: BLS Multi-Signatures With Public-Key Aggregation

Stay curious, stay secure!