zkhackiv-puzzle3-writeup

puzzle3.md

Solution to ZKHackIV - Puzzle 3

Puzzle 3 - Chaos Theory

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

Briefing

Puzzle 3 is about using encryption method to exchange message between two parties. Briefly, the scheme in Puzzle 3 can be described as following:

1. Receiver publishes his public key $pk_r$
2. The message is converted to an affine point on elliptic curve: $G_m = [m]G_1$
3. Sender use his secret key and Receiver's pulibc key to get an affine point on curve $G_{el} = [sk_s]pk_r = [sk_s * sk_r]G_1$, which is very unlikely to be breaked by a third party
4. Sender add message point with the secret point generated in step 3: $G_{c} = G_{el} + G_m$, then combining his public key with the aggregated point
5. Sender use a hash algorithm to hash the pair generated in step 4, then use his secret key to sign it: $G_{sign}' = [sk_s]G_{hash}'$, where the hash result $G_{hash}' = [H(pk_s, G_c)]G_2$ is an affine point on the pairing curve. Here we use $G'$ to represent a point on $G_2$.
6. Anyone can now use pairing to check the message exchange is valid: $e(G_1, G_{sign}') = e(pk_s, G_{hash}')$, since $e(G_1, G_{sign}') = e(G_1, [sk_s]G_{hash}') = e([sk_s]G1, G_{hash}') = e(pk_s, G_{hash}')$

Hack

We don't know the secret key of either Sender or Receiver. However, from the scheme we know their product can be mapped to a point on curve: $G_{el} = [sk_s * sk_r]G_1 = G_c - G_m$. We just don't know the result of $sk_s * sk_r$.

This doesn't bother us, because the product can be splitted into two parts of a pairing equation, e.g. $e([sk_s * sk_r]G_1, G_2) = e([sk_s]G_1, [sk_r]G_2) = e([sk_r]G_1, [sk_s]G_2)$.

We still do not know the result of $[sk_s]G_2$, but we have the point $G_{sign}'$, which equals $[sk_s]G_{hash}'=[sk_s * H(pk_s, G_c)]G_2$. Just multiply the $G_1$ point with $H(pk_s, G_c)$ and use pairing, we can make the equation valid:

$e(G_c - G_m, G_{hash}') = e([sk_s * sk_r]G_1, [H(pk_s, G_c)]G_2) = e([sk_r]G_1, [sk_s * H(pk_s, G_c)]G_2) = e(pk_r, G_{sign}')$

Since we have the full list of messages, we can go through all the messages to get $G_m$, then we check the validity of the above equation. If the equation holds, we know the corresponding message must be the secret message which got exchanged between Sender and Receiver.