Write-up for ZK Hack IV puzzle F3: Chaos Theory

zkhack2024_IV_puzzleF3_writeup.md

Write-up for ZK Hack IV puzzle F3: Chaos Theory

• Author: Nicolas IOOSS
• Date: 2024-01-30
• Puzzle: https://zkhack.dev/zkhackIV/puzzleF3.html, https://github.com/ZK-Hack/puzzle-chaos-theory

1. Subject

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

This puzzle is about an encryption scheme which provides authentication, using standard algorithm.

2. Authenticated Encryption

The repository https://github.com/ZK-Hack/puzzle-chaos-theory contains a Rust project implementing the encryption scheme. Let's take a look at src/main.rs.

use ark_bls12_381::{g2::Config, Bls12_381, Fr, G1Affine, G1Projective, G2Affine, G2Projective};

This imports types from crate ark_bls12_381 which implements the elliptic curve BLS12-381.

This document uses the same notation as the write-up for the previous puzzle:

• There are actually two curves in BLS12-381, named $G_1$ and $G_2$. They are generated by two points, $g_1 \in G_1$ and $g_2 \in G_2$, which share the same prime order $r$. The curves use the same scalar field $\mathbb{F}_r$.
• Points on these curves can use several coordinate systems. In Rust, the types G1Affine, G1Projective, G2Affine and G2Projective represent points on the curves using affine coordinates and projective coordinates.
• There exists a bilinear pairing function $e: G_1 \times G_2 \rightarrow G_T$ which combines points on $G_1$ and $G_2$ into an element of group $G_T$.
• As Arkworks is using the additive notation for groups, this write-up is also using them: the product of a point $P$ with a scalar $s$ is written $[s]P$ instead of $P^s$.

The Rust file contains on lines 54-64:

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

These functions implement the encryption and signing scheme. When a sender with private key $sk_s \in \mathbb{F}_r$ and public key $Pk_s = [sk_s]g_1 \in G_1$ sends a message $m \in G_1$ to a receiver with a public key $Pk_r \in G_1$:

• The sender computes $c_2 = [sk_s]Pk_r + msg \in G_1$.
• The ElGamal ciphertext is defined as $c = (Pk_s, c_2) \in G_1^2$.
• The sender computes the hash $h_c = H(c) \in G_2$ using a safe hash-to-curve function.
• The sender computes the signature $sig = [sk_s]h_c \in G_2$.

The sender can send $(c, sig)$ to the recipient. Anyone can verify the BLS signature of the ciphertext, by comparing two pairing computations:

$$e(g_1, sig) = e(Pk_s, H(c))$$

This is implemented in function Auditor::check_auth.

The receiver can verify the signature and decrypt with the private key $sk_r$ the message $msg = c_2 - [sk_r]Pk_s$

2. Fatal key reuse

This encrypt-then-sign scheme uses the same private key in the encryption and the signature. This seems fishy, but this is similar as what some other schemes are doing.

• Using the sender private key to sign a message is how asymmetric-key signature algorithms work.
• Using the sender private key in the ElGamal encryption is a way to authenticate the channel of an encrypted message (both the sender and the recipient know $[sk_s]Pk_r = [sk_r]Pk_s$ and nobody else).

However, encrypting with long-term (also known as static) keys enables an attacker to distinguish messages. The ciphertext of a message is always the same.

To prevent this issue, several protocols (such as Noise Protocol Framework and Signal's Extended Triple Diffie-Hellman) introduce a ephemeral keys. For example here, if the sender encrypted the message with a random private key $sk'$ and sent the verifier $(Pk', c_2)$ (with the associated public key $Pk' = [sk']g_1$), encrypting the same message twice would lead to different ciphertexts.

Back to the puzzle, how can the reuse of the private key be exploited?

From an encrypted message, an attacker can compute pairings with the ElGamal ciphertext.

First, let's rewrite the encryption equation by moving $msg$ to the other side:

$$c_2 - msg = [sk_s]Pk_r$$

Therefore:

$$e(c_2 - msg, h_c) = e\left([sk_s]Pk_r, h_c\right) = e\left(Pk_r, [sk_s]h_c\right) = e\left(Pk_r, sig\right)$$

This equation does not involve any private key, so the attacker can verify whether the ciphertext encrypted $msg$!

To make implementing this attack easier, let's rewrite the equation using $e\left(c_2 - msg, h_c\right) = e\left(c_2, h_c\right) - e\left(msg, h_c\right)$:

$$e\left(c_2, h_c\right) - e\left(Pk_r, sig\right) = e\left(msg, h_c\right)$$

The puzzle provided an encrypted message (loaded from file blob.bin) and 10 possible message (given by function generate_message_space). The attack can be implemented by computing the right-hand side for each message and comparing it with the left-hand side of the equation:

let h = blob.c.hash_to_curve();
let lhs = Bls12_381::pairing(blob.c.1, h) - Bls12_381::pairing(blob.rec_pk, blob.s);
for (i, msg) in messages.iter().enumerate() {
    let rhs = Bls12_381::pairing(msg.0, h);
    if rhs == lhs {
        println!("It was message {i}");
    }
}

This displays It was message 3, so the message encrypted in blob.bin is $[8492374892742]g_1$.

3. Conclusion

Combining encryption and signature is usual in messaging protocols involving asymmetric-key cryptography. However, doing so with BLS curves without ephemeral keys gives attackers the ability to guess which message was encrypted, without knowing any private key.