zkhack2021_puzzle5_writeup.md

Write-up for zkHack puzzle #5: To be Adaptive is to be Strong

• Author: Nicolas IOOSS
• Date: 2021-11-25
• Puzzle: https://www.zkhack.dev/puzzle5.html

1. Subject

Shallan recently found a proof system (see below) that enables proving that two Pedersen commitments commit to the same message (but with potentially different randomness). She employes this in her private cryptocurrency to show that two committed coins have the same value. However, soon after deployment, she receives a message from a self-proclaimed hacker. The message contains two Pedersen commitments and their openings, and a proof of message equality for these commitments. The proof is valid, but there's a twist: the openings contain different messages! How can this be? Reproduce the attack and help Shallan diagnose the problem in her system.

The Proof of message equality is obtained by applying the Fiat--Shamir transform to the following sigma protocol:

        Prover                                           Verifier
=================================================================================================
Offline phase:
1. Prover computes
    C_1 := PedersenCOMM(a; r1) = a * G + r1 * H
    C_2 := PedersenCOMM(a; r2) = a * G + r2 * H

    where G and H are generators of the group, and r1 and r2 are random field elements.
                            ------- C_1, C_2 ------->

Online phase:

1. Prover samples random elements r, ρ, τ.
2. Prover computes
    C_ρ := PedersenCOMM(r; ρ)
    C_τ := PedersenCOMM(r; τ)
                            ------- C_ρ, C_τ ------->
                            <- random challenge e ---
3. Prover computes
    s := r + e * a
    u := ρ + e * r1
    t := τ + e * r2
                            -------- s, u, t ------->
                                                Check PedersenCOMM(s; u) = C_ρ + eC_1
                                                Check PedersenCOMM(s; t) = C_τ + eC_2
==================================================================================================

This system has been implemented in Rust on https://github.com/kobigurk/zkhack-strong-adaptivity. The puzzle uses a twisted Edwards curve for the elliptic curve operations, described on https://docs.rs/ark-ed-on-bls12-381/0.3.0/ark_ed_on_bls12_381/.

2. Puzzle

The puzzle defines two points, G and H, which are used to compute Pedersen Commitments: the commitment of a number a with another number r consists in the point C:

C = a*G + r*H

G is called the message generator and H the hiding generator (as it is used to hide the message a in the commitment C).

Such a construction enables implementing zero-knowledge proof systems, using linear operations on commitments.

Here, the system uses two commitments of the same message a. The entity willing to prove their knowledge of a, Prover, performs some computations and interacts with a Verifier in order to make them believe that the commitments are valid. Instead of describing a second time what Prover does, let's detail what Verifier sees:

• Verifier receives two points C_ρ and C_τ.

• Verifier computes a challenge e. With Fiat--Shamir transform, the challenge e is in fact computed by Prover, to avoid an interaction. Here, the challenge consists in the BLAKE2s digest of (G, H, C_ρ, C_τ), converted into an integer.

• Verifier receives three integers s, u and t.

• Verifier checks that the the received data is a valid proof. More precisely, Verifier checks that:

  s*G + u*H = C_ρ + e*C_1
  s*G + t*H = C_τ + e*C_2
  

If Prover followed the proof system, these equations are correct because:

s*G + u*H = (r + e*a)*G + (ρ + e*r1)*H = (r*G + ρ*H) + e*(a*G + r1*H) = C_ρ + e*C_1
s*G + t*H = (r + e*a)*G + (τ + e*r2)*H = (r*G + τ*H) + e*(a*G + r2*H) = C_τ + e*C_2

This puzzles consists in crafting a proof (s, u, t) from two commitments C_1 and C_2 of two different values.

3. Attack

A key part of the robustness of proof systems using the Fiat--Shamir transform is that the challenge e cannot be manipulated by a rogue Prover. Here the challenge computation uses a robust hash function to ensure this property. However the input of this hash function does not include the commitments C_1 and C_2. This means that an attacker can compute these commitments after having computed e.

Let's craft a rogue proof!

First, we can choose to use r = 0, ρ = 0 and τ = 0. These values greatly simplify the equations, as the commitments become C_ρ = 0*G + 0*H = O (this point is called "point at infinity") and C_τ = O. Then, we can compute e from C_ρ and C_τ.

We now need to find seven numbers a1, a2, r1, r2, s, u and t such that:

s*G + u*H = C_ρ + e*C_1
s*G + t*H = C_τ + e*C_2
a1 != a2

with:

• C_1 = a1*G + r1*H
• C_2 = a2*G + r2*H
• C_ρ = C_τ = O

Therefore the equations become:

s*G + u*H = e*a1*G + e*r1*H
s*G + t*H = e*a2*G + e*r2*H
a1 != a2

Using the fact that the Discrete Logarithm Problem is hard on the largest prime subgroup of the elliptic curve which is used, and that G and H were generated in this subgroup, the first two equations can be split as:

s = e*a1 and u = e*r1
s = e*a2 and t = e*r2

So e*a1 = e*a2, and as the challenge value e is very very very unlikely to be zero, a1 = a2. Great! We have just proved that the proof system works as expected... not that we wanted to. What did we miss to make the attack succeed?

Taking a step back, it seems that the proof system relies on C_ρ and C_τ committing the same value r too. What if we break this assumption? Let's try again with two values for r:

r_for_ρ = 0
r_for_τ = 1
ρ = 0
τ = 0

These values lead to C_ρ = 0*G + 0*H = O and C_τ = 1*G + 0*H = G. After computing e, we need to find again seven numbers such that:

s*G + u*H = e*a1*G + e*r1*H
s*G + t*H = (1 + e*a2)*G + e*r2*H

This time, the equations simplify to e*a1 = 1 + e*a2, which can be solved with a1 and a2 being different! Let's choose:

a1 = 1/e
a2 = 0
r1 = 0
r2 = 0

Then we can compute:

C_1 = a1*G + r1*H = (1/e)*G
C_2 = a2*G + r2*H = O
s = e*a1 = 1
u = e*r1 = 0
t = e*r2 = 0

Giving these last values with C_ρ = O and C_τ = G leads to Verifier checking:

s*G + u*H = G = O + e*(1/e)*G = C_ρ + e*C_1
s*G + t*H = G = G + e*O = C_τ + e*C_2

So we have just crafted a rogue proof for two messages a1 = 1/e and a2 = 0, which is accepted by Verifier!

4. Rust attack

Here is an implementation of the attack described before, in Rust:

let rho = Fr::from(0);
let tau = Fr::from(0);
let r_for_comm_rho = Fr::from(0);
let r_for_comm_tau = Fr::from(1);
let comm_rho = ck.commit_with_explicit_randomness(r_for_comm_rho, rho);
let comm_tau = ck.commit_with_explicit_randomness(r_for_comm_tau, tau);
let e = b2s_hash_to_field(&(ck, ProofCommitment { comm_rho, comm_tau }));
let a_1 = Fr::from(1) / e;
let a_2 = Fr::from(0);
let r_1 = Fr::from(0);
let r_2 = Fr::from(0);
let s = Fr::from(1);
let u = Fr::from(0);
let t = Fr::from(0);

let instance = Instance {
    comm_1: ck.commit_with_explicit_randomness(a_1, r_1),
    comm_2: ck.commit_with_explicit_randomness(a_2, r_2),
};
let proof = Proof {
    commitment: ProofCommitment { comm_rho, comm_tau },
    response: ProofResponse {
        s: Fr::from(1),
        u: Fr::from(0),
        t: Fr::from(0),
    },
};

assert!(verify(&ck, &instance, &proof));
// Check that commitments are correct
assert_eq!(
    ck.commit_with_explicit_randomness(a_1, r_1),
    instance.comm_1
);
assert_eq!(
    ck.commit_with_explicit_randomness(a_2, r_2),
    instance.comm_2
);
// Check that messages are unequal
assert_ne!(a_1, a_2);

Conclusion

The main weakness of the proof system is that the computation of the proof challenge does not include the first commitments C_1 and C_2. Because of this, it is possible to choose them according to the value of the challenge and to craft a rogue proof.