ZK Hack IV - Chaos Theory

This is the solution of the challenge “Chaos Theory” from ZK Hack IV . Thanks to pairing bilinearity, it was possibile to identify a message encrypted with a variant of ElGamal encryption over bls12-381 curves.

Details

Author: Geometry research

Points: 991

Description

Sometimes they spontaneously reorganize themselves into an orderly structure.

Puzzle link

Solution

The implementation of the scheme uses the arkworks implementation of the bls12-381 curves with $G_1$ being the generator of the first curve $E_1$ and $G_2$ the generator of the second curve $E_2$.

We have two different public keys on $E_1$, one for the sender $Q_s$ and on for the receiver $Q_r$. Both are available in the Blob structure read from the blob.bin file. The sender has a private key $sk$ such that $Q_s = sk \cdot G_1$.

The encryption of a message $m$ is done by first mapping the message on the first curve: $M = m \cdot G_1$. Then the encryption is: $C = sk \cdot Q_r + M$. The sender gives the couple $(Q_s, C)$. This encryption is malleable regarding the addition like the initial ElGamal encryption since the encryption of $m + \alpha$ is $C_\alpha = sk \cdot Q_r + (m+\alpha) \cdot G_1 = sk \cdot Q_r + M + \alpha \cdot G_1 = C + \alpha \cdot G_1$.

To authenticate a ciphertext, the tag $S = sk \cdot H(Q_s, C)$ is sent. Where $H$ is a hash function mapping two points of $E_1$ to $E_2$. The authentication prevents the malleability since it is not possible to create a new tag from an existing one. Indeed, the two points will be serialized and then hased with SHA256 and finally mapped to a point on $E_2$. Thus, hashing $H(Q_s, C)$ and $H(Q_s, C_\alpha)$ leads to two different points with unknown discrete logarithm between each other.

To verify the authenticity of a ciphertext $(Q_s, C)$ from a tag $S$, the receiver check: $$e(G,S) \stackrel{?}{=} e(Q_s, H(Q_s, C))$$

This is valid for genuine ciphertexts and tags since: $$e(G,S) = e(G_1, sk \cdot H(Q, C)) = e(G_1, H(Q, C))^{sk} = e(Q_s, H(Q_s, C))$$

The problem of the previous scheme is that we have from a ciphertext $(Q_s, C)$, a tag $S$ and from the bilinearity of pairings: $$ e(C,H) = e(sk \cdot Q_r + M, H) = e(Q_r, H)^{sk} + e(M, H) = e(Q_r, S) + e(M, H)$$

Thus for each message $m_i$ we can compute $e(M_i, H)$ and check if the following equality holds: $$e(C,H) - e(M_i, H)\stackrel{?}{=} e(Q_r, S)$$

If yes then we have found the correct cleartext. The previous scheme does not provide indistinguishability under chosen plaintext attack (IND-CPA).

To recover the cleartext we have to loop over all the messages until the previous equation holds:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

/* Implement your attack here, to find the index of the encrypted message */
let hash_c = blob.c.hash_to_curve();
let lhs1 = { Bls12_381::pairing(&blob.c.1, hash_c) };
let rhs = { Bls12_381::pairing(blob.rec_pk, blob.s) };
for i in  0..messages.len(){
    let lhs2 = { Bls12_381::pairing(messages[i].0, hash_c) };
    let lhs = lhs1-lhs2;

    if lhs == rhs {
        println!("Found message: {i}");
    }
    
}
/* End of attack */

It turns out that message with index 3 was the correct plaintext.

Here is my repository solution. you can verify to run properly by running:

1

$ cargo run -r