# Writeup for ZK Hack IV Puzzle 3: Chaos Theory

## Statement

> Bob designed a new one time scheme, that's based on the tried and true method of encrypt + sign. He combined ElGamal encryption with BLS signatures in a clever way, such that you use pairings to verify the encrypted message was not tampered with. Alice, then, figured out a way to reveal the plaintexts...

As indicated by the prompt, the challenge is centered an authenticated encryption scheme based on Elgamal Encryption and BLS signatures.

## Examing the challenge source

Here's the source for the challenge, stripped down to the important bits

pub struct ElGamal(G1Affine, G1Affine);

impl ElGamal {
    pub fn hash_to_curve(&self) -> G2Affine {
        let mut data = Vec::new();
        self.serialize_uncompressed(&mut data).unwrap();

        hasher().hash(&data).unwrap()
    }
}

The `hash_to_curve` method on the Elgamal struct hashes the two G1 points in an Elgamal Ciphertext to a point on the G2 curve. It's important to note that the hash function used does not reveal the discrete log of the resulting point.

struct Sender {
    pub sk: Fr,
    pub pk: G1Affine,
}

impl Sender {
    pub fn send(&self, m: Message, r: &Receiver) -> ElGamal {
        let c_2: G1Affine = (r.pk.mul(&self.sk) + m.0).into_affine();
        ElGamal(self.pk, c_2)
    }

    pub fn authenticate(&self, c: &ElGamal) -> G2Affine {
        let hash_c = c.hash_to_curve();
        hash_c.mul(&self.sk).into_affine()
    }
}

The Sender structs implements the encryption and authentication scheme.

**Encryption**
$Enc_{skA, pkB}(m_0) = [skA]pkB + m_0$

**Authentication**
$Sig_{skA}(pkB, c = Enc_{skA, pkB}(m_0)) = [skA]hash(pkB, c)$

pub struct Auditor {}


impl Auditor {
    pub fn check_auth(sender_pk: G1Affine, c: &ElGamal, s: G2Affine) -> bool {
        let lhs = { Bls12_381::pairing(G1Projective::generator(), s) };

        let hash_c = c.hash_to_curve();
        let rhs = { Bls12_381::pairing(sender_pk, hash_c) };

        lhs == rhs
    }
}

The Auditor struct implements signature verification

**Verification**:
$e(G, Sig_{skA}(pkB, c)) == e(pkA, hash(pkB, c))$

Why this works can be deduced directly from the bilinearity pairings.

Let $hash(pkB, c) = [h]G_2$ where h is hidden due to the properties of the hash algorithm used.

Then the LHS computes to $e(G, [skA*h]G)$
While the RHS computes to $e(pkA, hash(pkB, c)) = e([skA]G, [h]G)$
Which by bilinearity reduces to $e(G, [skA*h]G)$

=== Alternative for last couple of lines:

**Verification**:
$e(G, Sig_{skA}(pkB, c)) == e(pkA, hash(pkB, c))$

Why this works can be deduced directly from the bilinearity pairings.
Concretely, we can rewrite the right hand side as
$$e(pkA, hash(pkB, c)) = e([skA]G, hash(pkB, c)) = e(G, [skA]hash(pkB, c)).$$
The equality $e(G, Sig_{skA}(pkB, c)) == e(pkA, hash(pkB, c))$ is thus equivalent to $e(G, Sig_{skA}(pkB, c)) == e(G, [skA]hash(pkB, c))$, which is in turn equivalent to $Sig_{skA}(pkB, c) == [skA]hash(pkB, c)$, which was the definition of the signature.

## The exploit

The vulnerability that allows us to deduce the plaintext here stems from two causes

1. The signature lacks a random nonce making it deterministic
2. The message space is small and brute forceable

The information given to us is as follows

pub struct Blob {
    pub sender_pk: G1Affine,
    pub c: ElGamal,
    pub s: G2Affine,
    pub rec_pk: G1Affine,
}

Additionally, we have a small list of possible plaintexts to test.

We are given
$s = [sender\_sk*h]G_2$
$c = [sender\_sk*rec\_pk]G_1 + m_0$
$sender\_pk = [sender\_sk]G_1$
$rec\_pk = [rec\_sk]G_1$

Consider the following two pairings

$E_1 = e(rec\_pk, s) = e([rec\_sk]G_1, [sender\_sk*h]G_2) = e(G_1, [rec\_sk*sender\_sk*h]G_2)$
$E_2 = e(c - m_0, hash(rec\_pk, s)) = e([sender\_sk*rec\_pk]G_1, [h]G_2) = e(G_1, [rec\_sk*sender\_sk*h]G_2)$

Hence, for the correct choice of $m_0, E_1 == E_2$

Therefore to deduce the plaintext, we perform the following

1. Loop through the message space
2. For each message M, compute the pairings $E_1$ and $E_2$
3. If the computations yield equal values, we have found the correct message

## Coding the exploit

    for (i, msg) in messages.iter().enumerate() {
        let shared = blob.c.1 - msg.0;

        // G1 * x * y * G2
        // G2 * x * hash_c * G1 * y
        // s == hash_c * x * G2

        let lhs = { Bls12_381::pairing(shared, blob.c.hash_to_curve()) };
        let rhs = { Bls12_381::pairing(blob.rec_pk, blob.s) };

        if lhs == rhs {
            println!("Msg {i} is correct");
        }
    }