Megaloblastt/supervillain.md Secret

## supervillain.md

      
    Raw
  

              supervillain.md
            
          
    Author

Michael ADJEDJ aka Megaloblastt
Puzzle Description

Getting the puzzle

ZKHack Puzzle address: https://zkhack.dev/zkhackIV/puzzleF2.html
Puzzle GitHub repository: https://github.com/ZK-Hack/puzzle-supervillain
Running the puzzle

Running the following command in the puzzle directory:
cargo run --release

gives the following output:
    ______ _   __  _   _            _
    |___  /| | / / | | | |          | |
       / / | |/ /  | |_| | __ _  ___| | __
      / /  |    \  |  _  |/ _` |/ __| |/ /
    ./ /___| |\  \ | | | | (_| | (__|   <
    \_____/\_| \_/ \_| |_/\__,_|\___|_|\_\
    

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

thread 'main' panicked at src/main.rs:53:5:
assertion failed: Bls12_381::multi_pairing(&[pk, G1Affine::generator()],
        &[hasher().hash(msg).unwrap().neg(), sig]).is_zero()
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Math Preliminaries

Elliptic Curve and Pairing

According to the puzzle description above, it uses BLS signatures. This signature scheme is quite simple to describe,
but requires advanced math techniques beforehand. Mainly, it uses what is called Pairings on Elliptic Curves.
I will describe here only what is required to understand the puzzle, and to solve it.
A pairing is a function which takes two input elements, and outputs one value. In most cases, the inputs cannot be
switched as they live in different mathematical groups. Let $\mathbb{G}{1}$ and $\mathbb{G}{2}$ denote these two groups.
A pairing is described as:
$$ e: \mathbb{G}_1 \times \mathbb{G}_2 \longrightarrow \mathbb{G} $$
These groups are cyclic, of same order, denoted as $r$, and for each there exists a special element that span the whole group.
These elements are called generators, and noted as $g_1$ and $g_2$. Using a multiplicative notation, any element $h$
in $\mathbb{G}_1$ (resp. in $\mathbb{G}_2$) is a power of $g_1$ (resp. $g_2$), ie $\exists k \in [0..r-1] | h = g_1^k$
(resp. $h = g_2^k$).
But pairings also have a very useful property: they are said to be bilinear. In simple words, it means that
combinations on the inputs translate in a equivalent way on the output. Mainly, the following equalities hold:
$$\begin{align*}
e(g_1^a, g_2^b) &= e(g_1, g_2^{a \cdot b}) = e(g_1^{a \cdot b}, g_2) = e(g_1, g_2) ^ {a \cdot b} \\\
e(g \cdot h, g_2) &= e(g, g_2) \cdot e(h, g_2) \\\
e(g_1, g \cdot h) &= e(g_1, g) \cdot e(g_1, h) \\\
e(g / h, g_2) &= e(g, g_2) / e(h, g_2) \\\
e(g_1, g/h) &= e(g_1, g) / e(g_1, h) \\\
\end{align*}$$
BLS Signatures

This elegent signature scheme uses the bilinear property of pairings.
The signer has a private key/public key pair $(sk, pk=g_1^{sk})$. To sign a given message $m$, he has to first hash it onto
the group $h(m) \in \mathbb{G}_2$, and compute the signature as $\sigma = h(m) ^ {sk}$.
The signature verification is done by checking the following equality:
$$ e(g_1, \sigma) \overset{?}{=} e(pk, h(m))$$
which holds in case of a legit signature since (using the bilinearity of the pairing), as:
$$ e(g_1, \sigma) = e(g_1, h(m)^{sk}) = e(g_1^{sk}, h(m)) = e(pk, h(m)) $$
Proof of possession

Additionaly to the BLS signature, there can be a proof that the associated private key is indeed known. In the case of
pairing-based schemes, this can be achieved by simply picking a random point $R$, the proof will be $\Pi = R^{sk}$.
NB: Without entering the details, the random point $R$ should really be random, and not correlated to any hash
or any other point.
Breaking the puzzle

Understanding the code

The main function is quite simple. Here are some parts, with explanations as comments:
    // Print the banner and puzzle description
    welcome();
    puzzle(PUZZLE_DESCRIPTION);
    // Extract a list of pair of elements in G1, G2
    let public_keys: Vec<(G1Affine, G2Affine)> = from_file("public_keys.bin");
    // This parts give more details about what was extracted in the above line:
    //  - the first element of each pair is a public key
    //  - the second element of each pair is proof of possession as explained above.
    // For each of them, check the proof indeed corresponds to the public key.
    public_keys
        .iter()
        .enumerate()
        .for_each(|(i, (pk, proof))| pok_verify(*pk, i, *proof));
    // pick a "random" message
    let message = b"YOUR GITHUB USERNAME";
The following sample tells us which variables should be set in order to solve the puzzle.
We need to:

Generate/craft a new public key (in $\mathbb{G}_1$)
Generate/craft a new proof for the aforementioned public key (in $\mathbb{G}_2$)
Generate/craft an aggregated signature, which should be validated with the previous extracted public keys, and the new one
we crafted.

    /* Enter solution here */

    let new_key = G1Affine::zero();
    let new_proof = G2Affine::zero();
    let aggregate_signature = G2Affine::zero();

    /* End of solution */
    // Verifies the proof associated with the crafted public key.
    pok_verify(new_key, new_key_index, new_proof);
    // Computes the aggregated public key, which is simply the sum of all public keys (including the crafted one)
    // NB: here the public keys (in G_1) are noted additively
    let aggregate_key = public_keys
        .iter()
        .fold(G1Projective::from(new_key), |acc, (pk, _)| acc + pk)
        .into_affine();
    // Check the aggregated signature verifies with the aggergated public keys.
    bls_verify(aggregate_key, aggregate_signature, message)
Analysing the math

As explained above, we need to generate values that satisfy three conditions:

Condition 1 Craft a valid public key
Condition 2 Craft a proof that is verified against the previous public key
Condition 3 Craft a signature which is verified against the aggregated public keys.

Satisfying Condition 1 is easy. Any element in $\mathbb{G}_1$ is a valid public key. We can either pick a random private key and
generate the associated public key, or simply pick a random element in $\mathbb{G}_1$ (but we won't know the associated private key).
Satisfying Condition 2 once we have a private/public key pair is easy. Moreover the following functions have been made available:
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()
}

#[allow(dead_code)]
fn pok_prove(sk: Fr, i: usize) -> G2Affine {
    derive_point_for_pok(i).mul(sk).into()
}
derive_point_for_pok pick a "random" point on the curve associated to an "id". The function pok_prove takes this
"random" point, and raises it to the private key. Looking at calls to pok_verify (which is meant to work symmetrically
to pok_prove - one generates the proof, the other verifies it) function tells us that the "id" is in fact the index of
each participant to the aggregated signature scheme + 1.
NB: The "random" point used to generate the proof is in fact a fixed point $\Gamma$ computed as
let rng = &mut ark_std::rand::rngs::StdRng::seed_from_u64(20399u64); G2Affine::rand(rng)
(ie the same for all participant), raised to the "id" of the target participant $\Gamma_i = \Gamma^{i+1}$, the proof now being $Proof_i = \Gamma_i^{sk_i} = \Gamma^{(i+1) \cdot sk_i}$.
Note that $\Gamma_i = \Gamma^{i+1}$ and $\Gamma_i^{1/{i+1}} = \Gamma$. We'll use these two relations later.
Crafting a signature is now the blocking point. If we follow the protocol honestly, this would require to know the private
key of each participant, which is believed to be hard... So let's put our black hat on, and act dishonestly!
Twisting the protocol

Warning
Math black magic starts here...

Let's write the conditions to be satisfied as mathematical expressions (again, Condition 1 is easy since any element in $\mathbb{G}_1$
is valid). Note that we'll keep the multiplicative notation.
Let $n+1$ be the total number of participants in the signature process, participants will be denoted as $P_i$ for $i \in [0..n]$. The puzzle requires to craft data associated with $P_n$.
Let $pk_n$ denote the public key associated to participant $n$, and $Proof_n$ his associated proof. Satisfying Condition 2 means:
$$e(pk_n, \Gamma_n) \overset{?}{=} e(g_1, Proof_n)$$
Let's now focus on Condition 3
Let $\Sigma$ denote the aggregated signature on the message $m$, it should be verified against the aggregated public key, which is the product of all the public keys:
$$e(\prod_{i=0}^n pk_i, h(m)) \overset{?}{=} e(g_1, \Sigma)$$
The easiest way to satisfy the above equation is to set $\Sigma = h(m)$ and $$\prod_{i=0}^{n}{pk_i} = g_1$$ This means
$$pk_n = g_1 / \prod_{i=0}^{n-1}{pk_i}$$
Let's see whether we can craft a proof that will be validated against this public key.
Remember that for participant $n$ we want to have:
$$e(pk_n, \Gamma_n) = e(g_1, Proof_n)$$
Replacing $pk_n$ by its values gives us:
$$\begin{align*}
e(pk_n, \Gamma_n) &= e(g_1 / \prod_{i=0}^{n-1}{pk_i}, \Gamma_n)   &||& &\\\
&= e(g_1 / \prod_{i=0}^{n-1}{pk_i}, \Gamma_n)                     &||& &\\\
&= e(g_1, \Gamma_n) / e(\prod_{i=0}^{n-1}{pk_i}, \Gamma_n)        &||& \texttt{<= pairing left-linearity} &\\\
&= e(g_1, \Gamma_n) / e(\prod_{i=0}^{n-1}{pk_i}, \Gamma^{n+1})    &||& \texttt{<= } \Gamma_n = \Gamma^{n+1} &\\\
&= e(g_1, \Gamma_n) / \prod_{i=0}^{n-1} \left( e(pk_i, \Gamma^{n+1}) \right)                &||& \texttt{<= pairing left-linearity} &\\\
&= e(g_1, \Gamma_n) / \prod_{i=0}^{n-1} \left( e(pk_i, \Gamma_i^{\dfrac{n+1}{i+1}}) \right) &||& \texttt{<= } \Gamma = \Gamma_i^{1/(i+1)} &\\\
&= e(g_1, \Gamma_n) / \prod_{i=0}^{n-1} \left( e(pk_i, \Gamma_i)^{\dfrac{n+1}{i+1}} \right) &||& \texttt{<=  pairing right-linearity} &\\\
&= e(g_1, \Gamma_n) / \prod_{i=0}^{n-1} \left( e(g_1, Proof_i)^{\dfrac{n+1}{i+1}} \right)   &||& \texttt{<= } e(pk_i, \Gamma_i) = e(g_1, Proof_i) &\\\
&= e(g_1, \Gamma_n) /  \left( e \left( g_1, \prod_{i=0}^{n-1}{Proof_i^ {\dfrac{n+1}{i+1}}} \right) \right) &||& \texttt{<= pairing right-linearity} &\\\
e(pk_n, \Gamma_n) &= e \left( g_1, \Gamma_n / \prod_{i=0}^{n-1}{Proof_i^ {\dfrac{n+1}{i+1}}} \right) &||& \texttt{<= pairing right-linearity} &
\end{align*}$$
Finally, by setting $$Proof_n = \Gamma_n / \prod_{i=0}^{n-1}{Proof_i^ {\dfrac{n+1}{i+1}}}$$ we'll have $e(pk_n, \Gamma_n) = e(g_1, Proof_n)$ which is the desired equation.
Inserting our results into the code

Let's start by setting the easiest value:
let aggregate_signature = hasher().hash(message).unwrap();
Then, the public key, and the associated proof:
let new_key = (  
                 G1Projective::from(G1Affine::generator()) - 
                 public_keys
                   .iter()
                   .fold(G1Projective::zero(), |acc, (pk, _)| acc + pk)
               ).into_affine();
let new_proof = (
                  derive_point_for_pok(new_key_index) - 
                  public_keys
                    .iter()
                    .enumerate()
                    .fold(G2Projective::zero(), 
                         |acc, (idx, (_, proof))| 
                         acc + proof.mul(Fr::from(idx as u64+1u64).inverse().unwrap())).mul(Fr::from(new_key_index as u64+1))
                  .into_affine()
                ).into_affine();
Running the completed code now goes without raising an exception, meaning we solved the puzzle!