Attacks on Fiat-Shamir

Vac
1

This is based on March’s IFT ZK Call. Visit the IFT ZK Meeting Notes for additional resources, and the video of this meeting.

The strong Fiat-Shamir transformation is a method to convert an interactive proof to a non-interactive proof. Essentially, each of the Verifier’s challenges are replaced with hashes.

Weak Fiat-Shamir attack

Weak Fiat-Shamir attacks have been a popular topic of conversation over the last few years. The omission of the statement from the hash allows a malicious party to construct a statement and proof that can convince any verifier. However, this is blocked by the inclusion of the public parameters and statement.

We can illustrate the insecurity of weak Fiat-Shamir with the Schnorr protocol. The Schnorr protocol enables the Prover to convince the Verifier that she knows the discrete logarithm of \gamma with respect to x; \gamma = g^x. The Schnorr protocol proceeds as follows:

\mathcal{P}(g, \gamma; x) \mathcal{V}(g,\gamma)
t \in \mathbb{Z}_p, \; \alpha := g^t \xrightarrow{\hspace{0.5cm} \alpha \hspace{0.5cm}}
\xleftarrow{\hspace{0.5cm} c \hspace{0.5cm}} c \in_R \mathbb{Z}_p
z := t + x c \bmod p \xrightarrow{\hspace{0.5cm} z \hspace{0.5cm}}
output \mathsf{acc} iff g^z = \alpha \gamma^c.

In weak Fiat-Shamir the Prover computes the challenge c = H(\alpha). Notice that \gamma is not fixed by c.

A malicious Prover can define her claim \gamma after c. By taking any z \in_R \mathbb{Z}_p, \gamma := g^{z/c} \alpha^{-1/c}. Hence, a malicious Prover has forged a non-interactive proof that any verifying party will accept.

Using strong Fiat-Shamir, the challenge c is computed as c = H(g,\gamma,\alpha). Assuming that H is collision-resistant, this fixes g and \gamma. Thus, preventing a malicious Prover from changing the values later.

Strong Fiat-Shamir attack

Recent work by Khovratovich, Rothblum and Soukhanov provide an attack on non-interactive ZKPs (with GKR) despite using strong Fiat-Shamir. This attack is interesting as it only requires the Prover to be malicious at the beginning of the attack.

This attack is made possible by:

  • Modern use of zkp for general purpose computations
  • GKR does not require commitment to computational trace.
  • The witness is large enough to contain either a commitment or hash value.

The paper provides three attacks, increasing in complexity. In the presentation (link pending), we provide an overview of the first attack. The severity of this attack on potentially other systems remains an open question, but the fact that such an attack exists does raise some concerns.

1 Like
2

Thanks for the presentation Marvin!

I had a question - for both Weak and Strong Fiat-Shamir attacks, it is mentioned that the Prover is the malicious “party”, did I understand correctly that the only difference is that with the Strong attack, the maliciousness only needs to happen at the beginning? Does that mean that there is a scenario where a Prover is malicious at the beginning and non-malicious later? Just trying to imagine that situtation.

3

The crucial difference between weak and strong Fiat-Shamir attacks is how the verifier’s challenges are generated by the Prover. The weak variant omits the public parameters and the statement which allows for reverse engineering in producing a statement that the guarantees any verifier accepts.

In the example given in the talk, we considered the Schnorr protocol. The statement-witness was (\gamma;x). Specifically, we can think of the statement that the Prover is wanting to prove is “I know a value (witness) that is the discrete logarithm of \gamma with respect to g.” That is, \gamma = g^x for x which the Prover wants to keep private.

How the challenge c is computed has to be known so that any verifying party can compute. So, for weak Fiat-Shamir, this could be done either as c = \mathsf{hash}(\alpha) or c = \mathsf{hash}(g,\alpha). In both of these cases, \gamma is not fixed!

However, for strong Fiat-Shamir, the verifying parties know that c is computed using g, \gamma and c.

Now, to your actual question. :slight_smile:

In the attacks discovered against GKR using strong Fiat-Shamir, these were interesting as the Prover would only need to be malicious for a single step. This means that the round soundness guarantees that usually can protect sumcheck and GKR from a malicious Prover is useless against this attack. With this particular attack, the Prover can forge the desired proof in the first step.

In the case of traditional weak Fiat-Shamir attacks, the Prover can be malicious in any round. However, usually the issues can compound. OpenZeppelin explained the ‘last challenge attack’ on Plonk which consisted of the Prover being malicious in the final round of Plonk (using weak Fiat-Shamir).

Usually, a malicious Prover’s cheating should compound because they may need to adjust values in each consequent round. This makes the strong Fiat-Shamir attacks so intriguing.

2 Likes