Weak Cryptography Implementations: Fiat-Shamir Attacks On Modern Proofs

There is an art of implementing cryptography, and that is why you have libraries that are marked HAZMAT (Hazardous Material) [here]. Care…

Weak Cryptography Implementations: Fiat-Shamir Attacks On Modern Proofs

There is an art of implementing cryptography, and that is why you have libraries that are marked HAZMAT (Hazardous Material) [here]. Care should always be taken in understanding the methods used and careful implementation with formal proofs, if possible. A single slip could cause serious damage, including the possible hack of cryptocurrency.

Weak Fiat-Shamir

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 his password. 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 found 36 weak implementations for 12 different proof systems: Bulletproofs, Plonk, Spartan, and Wesolowski’s VDF (Figure 1).

Figure 1

In the middle diagram in Figure 2, 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 generates H(A), along with a random value for z. The public value that this will verify is:

X=(g^z/A)^{1/c}

A strong Fiat-Shamir method thus does not hash A, while a weak version uses it. Here is the Python code to implement [here]:

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"A.X^c={check}, g^z={gz}")

and a sample run shows that we generate a valid value of X [here]:

z=1713689002964348707, A=1089902863577689045
X=4709536396455092582
== Now checking ==
A.X^c=9660029624058852496, g^z=9660029624058852496

Non-interactive ZKP using Fiat-Shamir

Non-Interactive Zero Knowledge Proof (NI-ZKP) allows us to prove knowledge of a value, without giving away the value. This example uses the Fiat-Shamir transformation and where Alice has a secret value of x. Alice can then show a public value of xG, and which is a point on the elliptic curve. Bob can then prove that Alice knows the value of x with (NI-ZKP). In this case, Alice will generate a random value (v and then send Bob the values of vG, r and c, and where Bob can then tell that Alice knows the value of x.

We use a Fiat Shamir method to prove that Alice knows x. As we are using a non-interative method, Alice will create her own challenge with:

c=Hash((G)||(x)||(xG))

Alice then creates a random value (v) and computes:

V=v.G

and:

r=(v−cx)

She sends the value of V, r and c to Bob, and who computes:

Vcheck=rG+c(xG)

If V is equal to Vcheck, Alice has proven that she knows x. The following is the code [here]:

from secp256k1 import curve,scalar_mult, point_add
import random
import hashlib
import sys
secret="Hello"
if (len(sys.argv)>1):
  secret=sys.argv[1]
s=int(hashlib.md5(secret.encode()).hexdigest(),16)
# Alice generates
x = random.randint(0, curve.n-1)
# Alice generates
xG = scalar_mult(x, curve.g)
print ("Let's prove that Alice knows x_1 with Fiat Shamir\n")
chal=str(curve.g)+str(x)+str(xG)
h=hashlib.md5()
h.update(chal.encode())
v= random.randint(0, curve.n-1)
vG = scalar_mult(v, curve.g)
c=int(h.hexdigest(),16)
r=(v-c*x) % (curve.n)
Vcheck = point_add(scalar_mult(r,curve.g),scalar_mult(c,xG))
print (f"Value to prove is {x}")
print (f"\nxG= {xG}")
print (f"\nv= {v}, vG={vG}")
print (f"\nr= {r}, c={c}")

if (vG==Vcheck): print("\nIt has been proven!!!")
else: print("\nNot proven!!!")

And a sample run [here]:

Let's prove that Alice knows x with Fiat Shamir
Value to prove is 39453035061538730972132695346908823374110795235584446095883797470940865348994
xG= (52703639832503000505077557980078009970772547026601077545536339809954486869925, 12363048174182892782319863380403495488032363119655628220124431198942731243202)
v= 98396675227169707736279864870068519402460952354104047156332609011117300100943, vG=(14016909468776439795043314130921003740628054308305540209140154480453375930010, 67584014808474750334396552926202969762318607494050062127693077653569242017613)
r= 40712767959947310716586609772122992272926753311240994230761195540243256850243, c=295426976571940371371606051744349077967
Vcheck= (14016909468776439795043314130921003740628054308305540209140154480453375930010, 67584014808474750334396552926202969762318607494050062127693077653569242017613)
It has been proven!!!

Conclusions

With many zero-knowledge proof libraries open to this attack, we must worry about future hacks on cryptography. Remember … with cryptography, you are dealing with serious maths, and you need to understand your methods. One slip, and you could lose so much.

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.