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:
/* 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.