description for zkhack IV puzzle 3 solution

zkhackIVpuzzle3.md

Write-up for ZK Hack IV puzzle 3

1. Authenticated Encryption

Suppose we have two chimpanzees: Flint and Goliath. Flint wants to send Goliath a message $m$ on a public channel with the following desiderata:

• No ape other than Goliath should be able to figure out what $m$ is; and
• Goliath should be sure that it was indeed Flint who sent him the message.

There is a well-accepted solution to this type of problem: combining public key encryption schemes and digital signature schemes. More precisely: Goliath has a public encryption key $pk_{G,enc}$ and a secret decryption key $sk_{G,dec}$, while Flint has a secret signing key $sk_{F,sign}$ and a public verification key $pk_{F,ver}$. The protocol works as follows: Flint first encrypts $m$ with respect to Goliath's public encryption key and then signs the resulting encrypted message with his private signing key.

Flint->Goliath: $x:=Enc(m, pk_{G,enc})$
Flint->Goliath: $\sigma:=Sign(x, sk_{F,sign})$

Goliath simply performs the following two algorithms: $\text{Dec}(x,sk_{G,dec})$ (for decryption) and $\text{Verify}(\sigma,pk_{F, ver})$ (for verification).

2. Setup of the puzzle

Unfortunately, Bob is not as careful as his great ape cousins, and does not implement the "encrypt and then sign" protocol correctly.

Suppose we have a non-degenerate bilinear pairing $e\colon \mathbb G_1\times \mathbb G_2\rightarrow \boldsymbol{\mu}$ satisfying all of the usual cryptographic assumptions, and denote by $r$ the common prime order of the groups. Let $g_1$ be a generator of $\mathbb G_1$.

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

pub struct Receiver {
    pk: G1Affine,
}

pub struct Auditor {}

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

Here, the ElGamal data type is: pub struct ElGamal(G1Affine, G1Affine);, and the struct Message is a wrapper for G1Affine. Furthermore, we assume that we have a hash function: $$H\colon \mathbb G_1\times \mathbb G_1\rightarrow \mathbb G_2,$$ which in the above formulation takes an element of type ElGamal and outputs an element of type G2Affine.

In other words, we assume that

• Bob has a private signing key $sk_{sign,B}\in \mathbb F_r$ and a public verification key $pk_{ver, B}:=g_1^{sk_{sign,B}}\in \mathbb G_1$; and
• Alice has a private decryption key $sk_{dec,A}\in \mathbb F_r$ and a public encryption key $pk_{enc,A}:=g_1^{sk_{dec,A}}\in \mathbb G_1$.

Given a message $m\in \mathbb G_1$, Bob sends the following pieces of data to Alice:

• $pk_{ver,B}\in \mathbb G_1$
• $\text{Enc}(pk_{enc,A},m):={(pk_{enc,A})^{sk_{sign,B}}}m=g_1^{sk_{dec,A}sk_{sign,B}}m\in \mathbb G_1$; and
• $\sigma:=\text{Sign}(sk_{sign,B},\text{Enc}(pk_{enc,A},m))$ $$=H(pk_{ver,B},\text{Enc}(pk_{enc,A},m))^{sk_{sign,B}}\in \mathbb G_2$$

(The first two are packaged together in type ElGamal.)

Verification works as follows:

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
    }

In other words, the verifier computes the following two pairings and checks they are equal: $$e(g_1,\sigma) = e(pk_{ver,B},H(c)),$$ where $c=(\text{Enc}(pk_{enc,A},m),\sigma)\in \mathbb G_1\times \mathbb G_1$ is of type ElGamal.

The Attack

We claim that given $c$, Bob's public verification key together with the encrypted message, along with Bob's signature $\sigma$, we can test if a given message $m'\in \mathbb G_1$ was the message Bob sent.

Indeed, let $c_2$ denote the encrypted message. We first compute: $$e(c_2,H(c)) = e(g_1^{sk_{dec,A}sk_{sign,B}}m, H(c))\in \boldsymbol{\mu}.$$ We then compute the following product of pairings: $$e(pk_{dec,A},\sigma)e(m', H(c)) = e(g_1^{sk_{enc,A}},\sigma)e(m',H(c))\in \boldsymbol{\mu}.$$ We claim that if these two elements of $\boldsymbol{\mu}$ are equal, then $m'=m$. Indeed, the RHS is $e(g_1^{sk_{enc,A}},H(c)^{sk_{sign,B}})e(m',H(c))$; using bilinearity once, this is $e(g_1^{sk_{enc,A}sk_{sign,B}},H(c))e(m',H(c))$. A second application of bilinearity shows that this is $e(g_1^{sk_{enc,A}sk_{sign,B}}m',H(c))$. Finally, non-degeneracy of the pairing implies that if $$e(g_1^{sk_{dec,A}sk_{sign,B}}m, H(c))=e(g_1^{sk_{enc,A}sk_{sign,B}}m',H(c)),$$ then $m=m'$.