ZK Hack Puzzle 5 Solution Writeup

zkhack5.md

Going to keep this solution precise and punchy. I'll explain my thought process and dead ends, in addition to the solution. Hopefully this illuminates the actual problem-solving process better. The core idea was to find a vulnerability related to the 'challenge' calculations in the proof, that would allow us to exploit the Fiat-Shamir calculation.

My first hunch was that we could hack the value of e; by setting it to 0, the verification would pass trivially since it wouldn't even verify the older commitments. Seeing that this would require us to rig the Blake2 output, I discarded this idea.

My second idea was to then hack the equations using e. Note that while $r + ea$ is being committed to in both checks, there is nothing enforcing that value to be calculated that way. "Selectively" (see puzzle title) choosing $r* + ea* = r + ea$, we can rig $r* and a*$ such that the value of s is consistent, but the calculation is not. We do this by partially rewinding the protocol; we begin with the usual $a$ commitments (one of which we'll discard later), and change one of the $r$'s to be a random $r*$ instead. Then, we calculate the corresponding e (that doesn't depend on a), and use that to compute the fake initial message $a* = a - (r* - r) / e$. We re-calculate that commitment, and bundle that in with the proofs for a full submission. The modified proving and rewinding code is below, with comments.

//Imports from the existing prove file
use ark_ec::{AffineCurve, ProjectiveCurve};
use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, SerializationError};
use ark_std::{UniformRand, io::{Read, Write}};
use rand::Rng;
pub use strong_adaptivity::msg_equality_arg::*;
pub use strong_adaptivity::msg_equality_arg::data_structures::*;
use strong_adaptivity::msg_equality_arg::utils::*;

// Our fake prover, with only 2 line diff
pub fn fake_prove<R: Rng>(ck: &CommitKey, instance: &Instance, witness: &Witness, rng: &mut R) -> (Proof, Fr) {
    let a = witness.a;

    // Following is our new variable -- we randomly define it as a but it could be any Fr
    let offset = witness.a;
    debug_assert_eq!(
        ck.commit_with_explicit_randomness(a, witness.r_1),
        instance.comm_1
    );
    debug_assert_eq!(
        ck.commit_with_explicit_randomness(a, witness.r_2),
        instance.comm_2
    );

    let r = Fr::rand(rng);
    let (comm_rho, rho) = ck.commit_with_rng(r, rng);

    // Following is the one line diff where we commit a different value
    let (comm_tau, tau) = ck.commit_with_rng(r + offset, rng);
    let commitment = ProofCommitment {
        comm_rho,
        comm_tau,
    };

    let challenge = b2s_hash_to_field(&(*ck, commitment));

    let s = r + challenge * a;
    let u = rho + challenge * witness.r_1;
    let t = tau + challenge * witness.r_2;
    let response = ProofResponse { s, u, t };

    (Proof{
            commitment,
            response,
        },
        challenge
    )
}


// Execute as usual
let rng = &mut rand::thread_rng();
let a = Fr::rand(rng);

let (comm_1, r_1) = ck.commit_with_rng(a, rng);
let (comm_2, r_2) = ck.commit_with_rng(a, rng);
let instance_old = Instance { comm_1, comm_2};
let witness = Witness { a, r_1, r_2 };

// Start the exploitation!
// This offset could be any Fr element, as long as it's consistent with the proof
let offset = a;

// Prove with an offsetted random value r_2
let (proof, challenge) = fake_prove(&ck, &instance_old, &witness, rng);

// Generate new fake a and commitment, with a consistent offset to the proof
let new_a = a - offset / challenge;
let comm_2_new = ck.commit_with_explicit_randomness(new_a, r_2);
let instance = Instance { comm_1, comm_2: comm_2_new };
(instance, (witness.a, witness.r_1, new_a, witness.r_2), proof)