Back

### Introduction

## See puzzle details on Github

Puzzle link
### Hidden in Plain Sight

### Fiat-Shamir

### Order Matters. Or does it?

### Exploiting Weak Fiat-Shamir

## Computing \(s\)

## Computing \(\alpha_2\)

### Reproducing the attack

### Fixing the protocol

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

Solution

by grjte

Selectivity can cause weaknesses.

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.

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

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.

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.

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

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\)

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

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

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.

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.

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.