Selectivity can cause weaknesses.

Introduction

The winner of the solution write up for the fifth puzzle, To be Adaptive is to be strong, created by Aleo, was from grjte.
The background materials for this puzzle are linked below.

Hidden in Plain Sight

This week’s puzzle went straight to the core of non-interactive proof constructions with a focus on the Fiat-Shamir heuristic , the most efficient and most common way of transforming interactive proofs into non-interactive ones.

The puzzle description is below:

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

Fiat-Shamir

The idea behind Fiat-Shamir is that instead of getting a random challenge \(e\) interactively from the verifier, we’ll get one from a “random oracle”, which we can do non-interactively (without interacting with the verifier). This oracle will be a theoretical black-box that responds to our queries with:

1. a truly random response for each unique query
2. the same response each time we repeat a query

In practice, we can use a secure, publicly agreed-upon hash function as our random oracle and give it public values from our proof protocol as inputs. This will allow the prover and any future verifiers to compute it, while also making it unique to the instance of the proof. The key to cracking the puzzle lay in the specific application of the Fiat-Shamir heuristic which was used to convert the sigma protocol from interactive to non-interactive. The implementation of Fiat-Shamir used in the code to create the challenge is the following:

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

These are the types of the inputs to the challenge hash function:

pub struct CommitKey {
    pub message_generator: GAffine,
    pub hiding_generator: GAffine,
}
pub struct ProofCommitment {
    pub comm_rho: GAffine,
    pub comm_tau: GAffine,
}

In other words, the challenge is a hash of:

* \(ck\) of type \(CommitKey\), which is the commit key containing G and H (from the sigma protocol)
* \(commitment\), of type \(ProofCommitment\), which holds the 2 commitments \(C_\rho\) and \(C_\tau\)

The important thing to notice is that neither of the message commitments \(C_1\) and \(C_2\) are inputs to the hash function used to generate the challenge.
Excluding the message commitments like this means that we’re working with a version of the Fiat-Shamir Heuristic referred to as “weak Fiat-Shamir”. You can read more about weak Fiat-Shamir and its implications in this paper.

Order Matters. Or does it?

Since \(C_1\) and \(C_2\) are not used in the hash function that generates the challenge, the first time they’re needed is for the verification at the very end of the protocol. What if we reorder the protocol to defer as much of the message commitment computation as we can to the last possible moment before we need it? The reordered protocol looks like this:

  Prover                                           Verifier
=================================================================================================

=== CHANGE: DEFER OFFLINE PHASE ===

Online phase:

1. Prover samples random elements r, ρ, τ.
2. Prover computes
   C_ρ := PedersenCOMM(r; ρ)
   C_τ := PedersenCOMM(r; τ)
                           ------- C_ρ, C_τ ------->
                           - random challenge e ---

=== BEGIN REORDERED OFFLINE PHASE PART 1 ===
We need  a, r1, r2 in the next step, so get them now.
Select message a and sample random elements r1, r2
=== END REORDERED OFFLINE PHASE PART 1 ===

3. Prover computes
   s := r + e * a,
   u := ρ + e * r1
   t := τ + e * r2
                           -------- s, u, t ------->

=== BEGIN REORDERED OFFLINE PHASE PART 2 ===
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 ------->
=== END REORDERED OFFLINE PHASE PART 2 ===

                                   Check PedersenCOMM(s; u) = C_ρ + eC_1
                                   Check PedersenCOMM(s; t) = C_τ + eC_2
==================================================================================================

In terms of the implementation of the protocol in the puzzle’s code, our newly reordered protocol is equivalent. We’ve moved a few things, but we haven’t actually affected any dependencies or executions, so everything is going to run just like it did before (as long as we continue to perform each step honestly…).
However, looking at our new protocol, it’s now pretty clear that something funny is going on. The prover is committing to their messages at a point in the protocol when they have complete information. Since the prover also has full control over message selection, this means it’s possible for the prover to select the message as a function of the challenge.
As malicious provers, we can now see how to exploit this weak Fiat-Shamir transformation.

Exploiting Weak Fiat-Shamir

Since our goal is for \(C_1\) and \(C_2\) to commit different messages, we’ll start referring to the messages as \(\alpha_1\) and \(\alpha_2\) and redefine our commitments:

\(C_1 = a_1*G + r_1*H\)
\(C_2 = a_2*G + r_2*H\)

Now let’s work backwards from the verifier’s checks:

\(PedersenCOMM(s; u) = C_ρ + eC_1\)
\(PedersenCOMM(s; t) = C_τ + eC_2\)

\(C_ρ\) and \(C_τ\) are both used to generate the challenge, so we can’t do anything to them. Similarly, \(u\) and \(t\) depend on \(\rho\) and \(\tau\) (used in \(C_\rho\) and \(C_\tau\), so we’re stuck with them too. This means that in order to cheat with \(C_1\) and \(C_2\) while still passing the verification, we’ll need to do something with \(s\).

Computing \(s\)

Recall that \(s = r + e*a\) where \(e\) is the challenge, \(a\) is our message, and \(r\) is randomness used in the proof commitments \(C_\rho\) and \(C_\tau\). However, we’re no longer working with \(a\). Now we have \(\alpha_1\) and \(\alpha_2\). That gives us the following:

\(s = r + e*a_1\)
\(s = r + e*a_2\)

This challenge value \(e\) is set in stone by the hash function, so the only way to preserve our inequality \(a_1 \ne a_2\) and commit different messages, would be to use a different value for \(r\) in each equation. Looking back at our protocol, \(r\) is used for the two proof commitments which are hashed into the challenge:

C_ρ := PedersenCOMM(r; ρ)
C_τ := PedersenCOMM(r; τ)

With these new random \(r\) values in hand, we compute \(s\) in the following way:

\(s = r_ρ + e*a_1\)
\(s = r_τ + e*a_2\)

Computing \(\alpha_2\)

A few quick manipulations and we have \(\alpha_2\)

\(a_2 = a_1 - (r_\tau - r_\rho) / e\)

Reproducing the attack

That’s everything we needed! Now we’ll just put it all together using our reordered protocol to reproduce the attack.
Instead of explicitly generating each random value, we’ll use the convenient helper function commit_with_rng which takes a “lazily-initialized thread-local random number generator, seeded by the system” and returns a commitment along with the randomness value that was used for it. This causes a few more minor adjustments to our reordered protocol, as noted in the code comments.

    let (instance, witness, proof): (Instance, (Fr, Fr, Fr, Fr), Proof) = {
    let rng = &mut rand::thread_rng();

    // === CHANGE: DEFER OFFLINE PHASE ===

    // === ONLINE PHASE ===
    // Step 1: Prover samples random elements r, ρ, τ.
    // CHEAT: generate 2 random r values instead of 1
    let r_rho = Fr::rand(rng);
    let r_tau = Fr::rand(rng);
    // generate random values rho and tau below using commit_with_rng

    // Step 2: Prover computes C_ρ, C_τ
    // create the proof commitment with randomly generated rho and tau
    let (comm_rho, rho) = ck.commit_with_rng(r_rho, rng);
    let (comm_tau, tau) = ck.commit_with_rng(r_tau, rng);
    let commitment = ProofCommitment { comm_rho, comm_tau };

    // compute verifier's challenge via Fiat-Shamir: e = H(G, H, comm_rho, comm_tau)
    let challenge = b2s_hash_to_field(&(ck, commitment));

    // === BEGIN REORDERED OFFLINE PHASE PART 1: a_1, r_1, r_2, comm_1 ===
    let a_1 = Fr::rand(rng);

    // compute comm_1 and generate r_1
    let (comm_1, r_1) = ck.commit_with_rng(a_1, rng);

    // generate random r_2
    let r_2 = Fr::rand(rng);
    // === END REORDERED OFFLINE PHASE PART 1 ===

    // Step 3: Prover computes s, u, t
    // CHEAT: compute s with r_rho and a_1
    let s = r_rho + challenge * a_1;

    // compute u, t honestly
    let u = rho + challenge * r_1;
    let t = tau + challenge * r_2;
    // create the proof response
    let response = ProofResponse { s, u, t };


    // === BEGIN REORDERED OFFLINE PHASE PART 2: a_2, comm_2 ===
    // CHEAT: compute a_2 from a_1, r_rho, r_tau
    let r_diff = r_tau - r_rho;
    let a_2 = a_1 - r_diff / challenge;
    let comm_2 = ck.commit_with_explicit_randomness(a_2, r_2);
    // === END REORDERED OFFLINE PHASE PART 2 ===


    // PREPARE STRUCTS FOR SOLUTION VALIDATION
    let instance = Instance { comm_1, comm_2 };
    let witness = (a_1, r_1, a_2, r_2);
    let proof = Proof {
        commitment,
        response,
    };

    // return
    (instance, witness, proof)
};

Run it… and it works! We’ve reproduced the attack and can successfully pass validation with commitments of two different messages.

Fixing the protocol

We’ve broken it - now let’s fix it. We can secure this protocol by taking away the prover’s ability to compute \(\alpha_2\) adaptively.
To do that, all we need to do is include \(C_1\) and \(C_2\) as inputs to the hash function that generates the verifier’s challenge, switching our Fiat-Shamir transformation from “weak Fiat-Shamir” to “strong Fiat-Shamir”. (Again, see this paper for more details on both.)
In other words, change this:

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

to this:

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

where \(instance\) is of type \(Instance\), containing the two message commitments:

      pub struct Instance {
    pub comm_1: GAffine,
    pub comm_2: GAffine,
}

Once this is done, the prover can no longer reorder the protocol as we did above, which means that our exploit will no longer be possible.

Weak Fiat-Shamir is sometimes good enough (just not this time)

As a final interesting note, the lesson here is not that using the weak Fiat-Shamir transformation is always insecure.
We said above:
We can secure this protocol by taking away the prover’s ability to compute \(\alpha_2\) adaptively.
In theory, there are two ways to do this:

1. Include the message commitments as inputs to the challenge hash function so the message can’t be computed as a function of the challenge (our solution from above, using strong Fiat-Shamir)
2.Take the power to choose the message commitments away from the prover. For example, by making them fixed inputs to the protocol
Although option doesn’t make particular sense in this protocol and would require a redesign, the point is that the security flaw is not caused solely by the use of weak Fiat-Shamir, but by the combination of weak Fiat-Shamir with the prover’s ability to choose the messages adaptively.