ZK HACK IV puzzle 3 writeup

writeup.md

Write-up for ZK Hack IV puzzle: Chaos Theory

• Authors: Danai Balla, Marianna Spyrakou
• Date: February 2024
• Puzzle link: https://github.com/ZK-Hack/puzzle-chaos-theory

Puzzle Description

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

Solution methodology

We will follow the path code -> math -> analytical solution on paper -> code.

From code to math

The folder /scr contains only main.rs so this is the file we will focus on.

Bob's encrypt & sign method

We first have the following declaration of a struct (line 29)

pub struct ElGamal(G1Affine, G1Affine);

Let us denote by $\mathbb{G}_1$ the group G1Affine, then instantiations of the struct ElGamal will be composed of pairs $(g, h)$ where $g, h \in \mathbb{G}_1$.

We also see the following implementation (lines 31-38)

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

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

So hash_to_curve is hash function $h: \mathbb{G}_1 \times \mathbb{G}_1 \to \mathbb{G}_2$, where we denote by $\mathbb{G}_2$ the group G2Affine.

Furthermore, on lines 41-64 we have the following methods.

pub struct Message(G1Affine);

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

pub struct Receiver {
    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 function send calculates c_2 by multiplying the receiver's public key with the secret key of the sender and adding the message. It returns the sender's public key and c_2.

So in math/pseudocode notation, that would be

$\texttt{send}(sk_s, pk_s, m, pk_r)$: return $c = (pk_s, sk_s\cdot pk_r + m) \in \mathbb{G_1}\times \mathbb{G_1}$.

The function authenticate just hashes c and multiplies the result with the secret key of the sender.

$\texttt{authenticate}(sk_s, c)$: return $s = sk_s \cdot H(c) \in \mathbb{G}_2$.

For the verification of the authenticate method, the recipient will use the following function (lines 66-75)

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

Let us denote by $g_1$ the generator of $\mathbb{G_1}$ (G1Projective::generator()), by $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ the pairing used in BLS (Bls12_381::pairing), then the functon check_auth does the following:

$\texttt{checkAuth}(pk_s, c = (pk_s, c_2), s)$: return $1$ iff $e(g_1, s) = e(pk_s, H(c))$

Understanding the attack we have to perform

Let's check main() (lines 106-125).

We see that on line 110 we have

let messages = generate_message_space();

and generate_message_space() (lines 85-104) generates a list of 10 messages:

fn generate_message_space() -> [Message; 10] {
    let g1 = G1Projective::generator();
    let msgs = [
        390183091831u64,
        4987238947234982,
        84327489279482,
        8492374892742,
        5894274824234,
        4982748927426,
        48248927348927427,
        489274982749828,
        99084321987189371,
        8427489729843712893,
    ];
    msgs.iter()
        .map(|&msg_i| Message(g1.mul(Fr::from(msg_i)).into_affine()))
        .collect::<Vec<_>>()
        .try_into()
        .unwrap()
}

Let us denote by $m_i \in \mathbb{G}_1, i = 1, \dots, 10$ the messages.

We also see that on lines 112-115 we have

let mut file = File::open("blob.bin").unwrap();
let mut data = Vec::new();
file.read_to_end(&mut data).unwrap();
let blob = Blob::deserialize_uncompressed(data.as_slice()).unwrap();

and the struct Blob is defined as (lines 78-83)

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

This means we have access to:

• sender_pk: $pk_s \in \mathbb{G}_1$
• c: $c = (pk_s, c_2)\in \mathbb{G}_1 \times \mathbb{G}_1$
• s: $s \in \mathbb{G}_2$
• rec_pk: $pk_r \in \mathbb{G}_1$

Finally, on lines 117-125 we have the description of the attack we have to implement:

// ensure that blob is correct
assert!(Auditor::check_auth(blob.sender_pk, &blob.c, blob.s));

/* Implement your attack here, to find the index of the encrypted message */

unimplemented!();

/* End of attack */

So we have to find the index $i$ of the message $m_i$, such that $m=m_i$, where $c = \texttt{send}(sk_s, pk_s, m, pk_r)$, without knowledge of $sk_r$ in order to decrypt the message.

The solution

Problem recap

We know:

• $pk_s \in \mathbb{G}_1$
• $pk_r \in \mathbb{G}_1$
• $c = (pk_r, c_2) = sk_s\cdot pk_r + m \in \mathbb{G_1}\times \mathbb{G_1}$ (but we don't know $sk_s$ and $m$)
• $s = sk_s \cdot H(c) \in \mathbb{G}_2$ (but we don't know $sk_s$)
• A list of possible messages $m_i, i=1, \dots, 10$ that $m$ corresponds to

And we need to find the index $i$.

We observe that if we knew $sk_r$ we could decrypt $c$: We know that $sk_r, pk_r$ is an ElGamal keypair and $sk_s, pk_s$ is a BLS keypair. Let us denote by $g_1$ the generator of the group $\mathbb{G}_1$, we have that $pk_r = sk_r\cdot g_1$ and $pk_s = sk_s \cdot g_1$. This means that: $$c_2 = sk_s\cdot pk_r + m = sk_s (sk_r \cdot g_1) + m = sk_r (sk_s \cdot g_1) + m = sk_r \cdot pk_s + m.$$

If we knew $sk_r$ we could decrypt $c$ by setting $m = c_2 - sk_r\cdot pk_s$.

However, although we don't know $sk_r$, we don't need to decrypt the message, since we have a list of possible messages $m_i, i=1, \dots, 10$ that $c$ corresponds to.

We will take advantage of the fact that the system uses pairings for verification.

Preliminaries: Pairings

Let $(\mathbb{G}_1, +)$, $(\mathbb{G}_2, +)$, $(\mathbb{G}_T, +)$ be three cyclic groups of prime order $q$ where $g_1 \in \mathbb{G}_1$ and $g_2 \in \mathbb{G}_2$ are generators. A pairing is an efficiently computable function $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_2$ satisfying the following properties:

1. bilinear: for all $u, u' \in \mathbb{G}_1$ and $v,v' \in \mathbb{G}_2$ we have $e(u + u', v)=e(u,v)+ e(u',v)$ and $e(u, v+ v')=e(u,v)+ e(u,v')$
2. non-degenerate: $g_T := e(g_1,g_2)$ is a generator of $\mathbb{G}_T$.

Bilinearity implies that $\forall \alpha, \beta \in \mathbb{Z}_q$ we have that $e(\alpha \cdot u, \beta \cdot v)=\alpha \cdot \beta \cdot e(u, v) = e(\beta \cdot u, \alpha \cdot v)$.

The above property is the property we are going to use to exploit the system.

The attack

For each of the messages $m_i$ in the message list, we can calculate the following values, using only values we know!

• $v_1 = e\left( c_2 - m_i,, H(c) \right)$
• $v_2 = e\left( pk_r, s \right)$

From the properties of pairings, we have that

• $v_1 = e\left(sk_s \cdot pk_r+ m -m_i, , H(c)\right)$
• $v_2 = e\left( sk_r \cdot g_1, , sk_s \cdot H(c) \right) = sk_r\cdot sk_s \cdot e\left( g_1, , H(c) \right)$

Observe that if $m=m_i$, then $v_1=v_2$:

$v_1 = e\left( sk_s \cdot sk_r \cdot g_1, H(c) \right) = sk_r\cdot sk_s \cdot e\left( g_1, , H(c) \right) = v_2$,

and we can calculate $v_1$ and $v_2$ without knowledge of $m, sk_r, sk_s$.

Implementing the attack

Below is the implementation of the attack.

/* Implement your attack here, to find the index of the encrypted message */
let mut solution: i8 = -1;
let mut i = 0;
while i < 10 {
    let m = messages[i];
    let lhs = { Bls12_381::pairing(blob.c.1.sub(m.0), blob.c.hash_to_curve()) };
    let rhs = { Bls12_381::pairing(blob.rec_pk, blob.s) };
    if lhs == rhs {
        solution = i as i8;
    }
    i += 1;
}
println!("solution is {}", solution);

/* End of attack */

Final thoughts

Intution behind the attack

The intuition behind the attack is that since the set of possible messages is known then for the true encrypted message $m_i$ from the list of messages, we can learn the value $$ c_2 - m_i = sk_r\cdot pk_r = sk_r\cdot sk_s \cdot g_1$$ By using the bilinearity property of pairings we can compare $c_2 - m_i$ with $pk_r$ and $s$, which "contain" $sk_r$ and $sk_s$, respectively.

Semantic security

The attack presented was an attack on the semantic security property of public key encryption schemes. Semantic security is the property that captures the abilities of an eavesdropping adversary that even though they might know a set of possible messages that a ciphertext corresponds to, they cannot know to which of the message it actually corresponds to.

For a formal definition of semantic security, the reader can refer to the book "A graduate course on Applied Cryptography" of D. Boneh and V. Shoup.

Intuitively, semantic security can be described as follows:

The adversary can choose two messages, and another entity (the challenger) chooses randomly one of them and encrypts it. Then the adversary tries to guess which of the two messages was encrypted and outputs his guess. In order for a scheme to be scemantically secure, the probability that the adversary can guess correctly should be negligibly close to 1/2 (= the probability of the adversary guessing uniformely at random). Semantic security implies that an adversary that runs in polynomial time cannot do anything better than randomly guessing which message corresponds to which ciphertext.

Security of Bob's method

The attack performed to Bob's method shows that the method is not semantically secure, since we can always decide correctly which message was encrypted given a list of 10 possible messages.