Many blockchain based systems have rushed to use the Fiat-Shamir transformation as a public-coin verifier. Within this, Alice will generate a random oracle, and then take a hash of the secret value and its public value, and create a zero knowledge proof of the knowledge of x. But, a new paper [1] shows that there are weak implementations of these, and identifies an adaptive attack.
Weak Fiat-Shamir in ZKPs (adaptive attack) - using discrete log |
Theory
With Fiat–Shamir [2], we can prove that we know a value without actually revealing the original value. In this, Bob will prove to Alice that he still knows a secret \(x\). Bob generates a random number (\(v\)) and computers a challenge value (\(c\)), and sends the proof that he still knows \(x\):
And, so, many blockchain based systems have rushed to use the Fiat-Shamir transformation as a public-coin verifier. Within this, Alice will generate a random oracle, and then take a hash of the secret value and its public value, and create a zero knowledge proof of the knowledge of \(x\). But, a new paper shows that there are weak implementations of these, and which is identified in this paper:
In the paper, the research team surveyed open-source implementations using the Fiat-Shamir transformation and fund 36 weak implementations for 12 different proof systems: Bulletproofs, Plonk, Spartan, and Wesolowski’s VDF.
In the middle diagram in Figure 1, we see that the secret is x, and the public value is \(X\) (\(g^x\)). The prover (Peggy) then generates a random value of a and provides \(A\) (\(g^a\)). Next, Peggy computes \(c=H(g,X,A)\) and then computes \(z=a+c.x\), and sends \(A\) and \(z\). The verifier can then recompute \(c\), and prove that \(g^z\) is equal to \(A.X^c\). This is because:
\(A.X^c = g^a (g^x)^c = g^a . g ^{xc} = g^{a+xc} = g^z\)
Figure 1 [1]
The diagram on the right-hand side then shows an adaptive attack against this method, and where an adversary generates a random value of \(A\) and then generate \(H(A)\), along with a random value for \(z\). The public value that this will verify is:
\(X={(g^z/A)}^{1/c}\)
This works because we need to prove:
\( g^z = A.X^c = A. { {(g^z/A)}^{1/c} }^c = A.g^z/A = g^z\)
A strong Fiat-Shamir method thus does not hash \(A\), while a weak version uses it. Here is the Python code to implement:
The code is:
import sys import random import hashlib import math from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes primebits=64 if (len(sys.argv)>1): primebits=int(sys.argv[1]) p = getPrime(primebits, randfunc=get_random_bytes) g=3 while True: a = random.randint(0, p-1) A=pow(g,a,p) chal=str(A) h=hashlib.sha256() h.update(chal.encode()) c=int(h.hexdigest(),16)%p if (math.gcd(c,p-1)==1): break invc = pow(c,-1,p-1) invA = pow(A,-1,p) z= random.randint(0, p-1) num=(pow(g,z,p) * invA)%p X=pow(num,invc,p) print (f"z={z}, A={A}") print (f"X={X}") print("== Now checking ==") check=(A*pow(X,c,p)) %p gz=(pow(g,z,p)) %p print (f"\nA.X^c={check}, g^z={gz}")
A sample run for 64-bit prime numbers is:
z=7786275443024401878, A=11273461968944163189 X=7686911745997251288 == Now checking == A.X^c=14690508513569562617, g^z=14690508513569562617
A sample run for 256-bit prime numbers is:
z=40436999084821359657998157748250429154944912488620369228092826724002714224996, A=80187082563315753552045216485422957266825623877840365356062103019143544613144 X=3330997358840979588331215464481107125638569712850767143655281639934435759308 == Now checking == A.X^c=2357816499352430304670551950662983057724015081112597584822105116071367578295, g^z=2357816499352430304670551950662983057724015081112597584822105116071367578295
Reference
[1] Dao, Q., Miller, J., Wright, O., & Grubbs, P. (2023). Weak Fiat-Shamir Attacks on Modern Proof Systems. Cryptology ePrint Archive.
[2] Fiat, A., & Shamir, A. (1986, August). How to prove yourself: Practical solutions to identification and signature problems. In Conference on the theory and application of cryptographic techniques (pp. 186–194). Berlin, Heidelberg: Springer Berlin Heidelberg.