Puzzle Supervillain

gistfile1.txt

# Supervillain

## Problem Statement
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

## Solution

The puzzle is solved if two conditions are met:

- The attacker provides a valid proof-of-key and;
- The attacker provides a valid aggregate signature and aggregate public key combination for that public key.

This can be achieved via a rogue key attack, in which we calculate both a public key and signature for a discrete log we don't know.

### Forging Proof-of-Knowledge

First, let's calculate the public key by subtracting the attacker's public key from the aggregate of all other public keys in the system:
$$pk^{'} = pk_n + \sum_{i=0}^{n-1}-pk_ i$$

In rust:

```rust
let secret = Fr::from(BigInt!("123"));
let my_key = G1Affine::generator().mul(secret).into_affine();
let new_key = public_keys
    .iter()
    .fold(G1Projective::from(my_key), |acc, (key, _)| acc + key.neg())
    .into_affine();
```
To support the rogue key, a corresponding PoK is needed. We can calculate it from the other participant's PoK's

Let's recall that the $$i$$th signature is:

$$s_i=A*sk_i*(i+1)$$

Where:

- $$s_i$$  is the $$i$$th signature;
- $$sk_i$$ is the $$i$$th private key used to generate that signature;
- $$i$$ is the index of the participant and;
- $$A$$ is a random point $$G_2$$ point calculated inside `derive_point_for_pok`.

The goal is to forge signatures for all public keys that "sign" the same message. That's why we need to cancel out the individual indices (by multiplying with the inverse of $$i$$) and then multiply by $$n$$ that's `new_key_index`. By doing so, we obtain signatures for the same message $$n$$ from different public keys for which we don't know the corresponding secret keys.

$$rhs_i = ((n+1) * (i+1))^{-1}$$

Then, we aggregate the signatures $$pok_s^{'}$$ in the same way we did for $$pk^{'}$$:


$$pok_s^{'} = pok_n + \sum_{i=0}^{n-1} -(s_i*rhs_i )$$

In rust:

```rust
let my_proof = pok_prove(secret, new_key_index);
let new_proof = public_keys
    .iter()
    .enumerate()
    .fold(G2Projective::from(my_proof), |acc, (i, (_, proof))| {
        let rhs = Fr::from(new_key_index as u128 + 1) * Fr::from(i as u128 + 1).inverse().unwrap();
        acc + proof.mul(rhs).neg()
    })
    .into_affine();
```

Here, `my_proof` is the proof of knowledge $$pok_n$$ for the attacker's key $$sk_n$$ while `new_proof` is the rogue proof $$pok_n^{'}$$.

With the forged public key and corresponding proof of knowledge, we can pass the first validation.

To pass the second validation, we are going to forge aggregated proofs and signatures to fool the light client into thinking other participants signed an arbitrary message.

### Forging Signatures

In BLS aggregated signature validation, we can simply add up all the points for the signatures, public keys and validate all with just two pairings:

$$e(pk_{agg}, H(m)) = e(sig_{agg}, G_2)$$

Where:
- $$e$$ is a pairing function;
- $$H$$ is a hash-to-curve function;
- $$m$$ is our arbitrary message.

Which means the aggregated public keys $$pk_{agg}$$ we simple pass our forged public key $$pk^{'}$$, to be added with the other participants.

For the aggregated signature, we can forge a signature using the same technique of the forged PoK: subtract the aggregate signatures from our signature of the message $$m$$,  $$sig_n = sk_n * H(m)$$:

$$
sig_n^{'} = sig_n + \sum_{i=0}^{n-1}-sig_ i
$$

```rust
let my_sig = bls_sign(secret, message);
let fake_signature = public_keys
    .iter()
    .fold(G2Projective::from(my_sig), |acc, (_, proof)| acc + proof.neg())
    .into_affine();
```
and then add it to the summation valid signatures provided for PoKs:

$$sig_{agg}^{'} = sig_n^{'} + pok_{agg}$$

```rust
let aggregate_signature = public_keys
    .iter()
    .fold(G2Projective::from(fake_signature), |acc, (_, proof)| acc + proof)
    .into_affine();
```

In this part, `my_sig` is the signature generated by the attacker. The `fake_signature` is then constructed by aggregating all the proofs and subtracting `my_sig`. The `aggregate_signature` is the final signature that is broadcasted and will pass verification checks due to the rogue key attack.