ZK Hack 4 Puzzle 3 Chaos Theory: write up

chaos-theory.md

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...

Overview

This puzzle uses the BLS12-381 elliptic curve, in particular the induced additive groups $\mathbb{G}_1,\mathbb{G}_2$ and multiplicative target group $\mathbb{G}_T$. We denote

$$e:\mathbb{G}_1\times\mathbb{G}_2\longrightarrow\mathbb{G}_T$$

for the pairing defined over those groups, and $g_1\in\mathbb{G}_1$ a fixed generator. If $k$ is an element of the scalar field $\mathbb{F}$ of the curve then $[k]\:g$ denotes scalar multiplication, where $g$ is an element of either of the additive groups.

We'll describe Bob's encrypt-then-sign scheme as presented in the code.

ElGamal encryption

The encryption part of the scheme is based on ElGamal encryption. Conventionally, this works over a single cyclic group, in this case $\mathbb{G}_1$, assumed to be publically known.

A "sender" $S$ wishes to transmit a confidential message to a "receiver" $R$. Assume the receiver has published a public key $\mathsf{pk}_R$

pub struct Receiver {
    pk: G1Affine,
}

(Conventionally, this is obtained by first selecting a secret key $\mathsf{sk}_R$ at random from $\mathbb{F}$ and then computing $[\mathsf{sk}_R]\:g_1$, but for the purposes of this puzzle, this is a detail that is not so important).

The sender follows a similar process, generating a key pair $(\mathsf{sk}_S,\mathsf{pk}_S)$

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

Again, following the ElGamal encryption scheme, the secret key $\mathsf{sk}_S\in\mathbb{F}$ should be chosen randomly, so that the public key is given by

$$\mathsf{pk}_S:=[\mathsf{sk}_S]\:g_1$$

To encrypt a message $m$ to $R$, the sender now multiplies their secret key with $R$'s public key (computing what's known as the shared secret for reasons that will become clearer), and adds $m$ (considered as a $\mathbb{G}_1$ element):

$$c_2:=[\mathsf{sk}_S]\:\mathsf{pk}_R+m$$

The ciphertext $(\mathsf{pk}_S,c_2)$ consists of the above data. The send method captures this encryption process:

pub struct ElGamal(G1Affine, G1Affine);
pub struct Message(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)
    }
}

The code does not contain the decryption logic for Receiver (since presumably, it is not relevant for the puzzle itself) but for completeness we'll describe it here. Given the ciphertext $(c_1,c_2)$, the receiver first multiplies $c_2$ by their secret key. Assuming the ciphertext has not been tampered with, notice this is

$$[\mathsf{sk}_R]\:c_1=[\mathsf{sk}_R]\:\mathsf{pk}_S=[\mathsf{sk}_R][\mathsf{sk}_S]\:g_1=[\mathsf{sk}_S]\:\mathsf{pk}_R$$

In other words, the receiver recovers the shared secret. Subtracting this from $c_2$ in turn recovers the plaintext:

$$c_2-[\mathsf{sk}_R]\:c_1=[\mathsf{sk}_S]\:\mathsf{pk}_R+m-[\mathsf{sk}_S]\:\mathsf{pk}_R=m$$

BLS authentication

The authentication part of Bob's scheme is based on BLS signatures. Once a ciphertext $c=(c_1,c_2)$ has been generated, the sender signs it to produce a signature, also called a message authentication code (MAC). The signing process is defined in the authenticate method and consists of hashing $c$ to a $\mathbb{G}_2$ element via a hash function $H$ given by the hasher() function in the code, before multiplying by $S$'s secret key, $[\mathsf{sk}_S]\:H(c)$

impl ElGamal {
    pub fn hash_to_curve(&self) -> G2Affine {
        let mut data = Vec::new();
        self.serialize_uncompressed(&mut data).unwrap();
        hasher().hash(&data).unwrap()
    }
}
impl Sender {
    pub fn authenticate(&self, c: &ElGamal) -> G2Affine {
        let hash_c = c.hash_to_curve();
        hash_c.mul(&self.sk).into_affine()
    }
}

The code for verifying a signature is given in the check_auth method of the Auditor struct. Given a claimed signature $\sigma$ of the ciphertext $c$ from $S$, the "auditor" checks that the following equation holds

$$e(g_1,\sigma)=e(\mathsf{pk}_S,H(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
    }
}

Indeed, if the arguments to the check are as claimed,

$$e(g_1,\sigma)=e(g_1,[\mathsf{sk}_S]\:H(c))=e([\mathsf{sk}_S]\:g_1,H(c))=e(\mathsf{pk}_S,H(c))$$

The challenge

We are given a "blob" of data deserialized from the supplied .bin file, presumably capturing an encrypted-then-signed message $(c,\sigma)$ sent from sender to receiver, along with their public keys

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

Furthermore, this blob is correct, in the sense that it passes the auditor's authentication check mentioned above

assert!(Auditor::check_auth(blob.sender_pk, &blob.c, blob.s));

We are also given the "message space" messages, an array of 10 distinct Messages. One of these is the plaintext giving rise to the ciphertext $c$ and the challenge is to find it.

Solution

An important general point about ElGamal encryption is that the shared secret established between the sender and receiver acts as a one-time pad. As such, it should only be used once. Otherwise, notice that if an attacker obtains both the ciphertext $(c_1,c_2)$ and plaintext $m$, they also learn the shared secret by subtraction $c_2-m$, hence they are able to decrypt further ciphertexts. Thus it is important that the secret key $\mathsf{sk}_S$ - used to derive the shared secret - is generated fresh for every message.

While the secret key $\mathsf{sk}_S$ used for encryption in the blob is unknown, we can at least use the above observation to obtain values

$$c_2-m_i,\;i=0\ldots 9$$

one for each of the 10 messages $m_i$. One of these values, say $c_2-m$, will be the shared secret where $m$ is the plaintext giving rise to $c$:

$$[\mathsf{sk}_S]\:\mathsf{pk}_R=c_2-m$$

For the other 9 choices of $m_i$, this equation will of course not hold. Can this equation be checked despite not having $\mathsf{sk}_S$? This turns out to be affirmative, with the help of the signature $\sigma$! Since we know that the data contained in blob passes the auditor's authentication check, the following must hold

$$e(c_2-m,H(c))=e([\mathsf{sk}_S]\:\mathsf{pk}_R,H(c))=e(\mathsf{pk}_R,[\mathsf{sk}_S]\:H(c))=e(\mathsf{pk}_R,\sigma)$$

Hence in order to recover the plaintext, we want the message $m_i$ such that the following pairing check holds

$$e(\mathsf{pk}_R,\sigma)=e(c_2-m_i,H(c))$$

let Blob { c, s, rec_pk, .. } = blob;
let hash_c = c.hash_to_curve();
let pos = messages.into_iter().position(|m| {
    let possible_ss = c.1 - m.0;
    let lhs = Bls12_381::pairing(rec_pk, s);
    let rhs = Bls12_381::pairing(possible_ss, hash_c);
    lhs == rhs
});
println!("index of plaintext message: {}", pos.unwrap());

Running this gives the desired index of the plaintext:

index of plaintext message: 3