by: Johan
background
The Frozen Heart vulnerability was named by the Trail of Bits team, where Frozen stands for Forging Of Zero kNowledge proofs and Heart refers to the Fiat-Shamir transformation, which is the core of many proof systems. The vulnerability refers to the application of the "weak Fiat-Shamir" transformation, which only hashes part of the prover's message without hashing public information (such as parameters, public inputs, etc.), thus causing security issues.
Below we will conduct a comprehensive analysis of this vulnerability. Let’s first talk about what is the Fiat-Shamir transform.
Fiat-Shamir transform
The Fiat-Shamir transformation, also known as the Fiat-Shamir Heuristic or the Fiat-Shamir Paradigm, is a transformation proposed by Fiat and Shamir in 1986 to transform an interactive zero-knowledge proof protocol into a non-interactive zero-knowledge proof protocol. It achieves this transformation by replacing the random challenge in the protocol with the output of a hash function. In this way, the prover can generate a proof and send it to the verifier without interactive challenges and responses.
Schnorr proof is an interactive zero-knowledge proof protocol that allows the prover to prove to the verifier that a statement is true without revealing the details of the statement, and the verifier can perform interactive verification. It is usually used when the prover knows a secret value without revealing it.
With the help of Fiat-Shamir transformation, Schnorr interactive proof can be transformed into non-interactive one.
Schnorr can be implemented on finite fields or elliptic curves (ECs). The technical specifications are basically the same, but the underlying cyclic groups are different. Below we mainly describe these two processes in the form of finite fields [1]:
* Symbol Description:
Alice: the assumed identity of the prover in the protocol
Bob: the assumed identity of the validator in the protocol
a | b: a can be divided b
a || b: the concatenation of a and b
[a, b]: integer interval, including a and b
t: the number of bits of the challenge chosen by Bob
H: secure cryptographic hash function
p: a large prime number
q: a large prime factor of p-1, i.e. q | p-1
Zp*: the multiplicative group of integers modulo p
Gq: a subgroup of Zp* with prime order q
g: generator of Gq
g^d: g raised to the power of d
a mod b: a modulo b
Fp: a finite field of p elements, where p is a prime number
Implementation based on finite fields
1. Interactive
First, Alice calculates A = g^a mod p, where the private key a takes the value [0, q-1], and then publishes the public key A;
Then, without revealing a, Alice proves to Bob that she knows the private key a corresponding to A:
If check is true, then we can prove that Alice knows a , as follows:
The reason why Bob needs to generate random c here is that if the attacker knows this value before publishing A, then he can forge the proof without knowing the real a. The attacker forges (A, V, r) as follows:
1) Generate a random value r
2) The calculation method of V remains unchanged, let
After receiving these three parameters, the Verifier substitutes them into the verification formula and can also pass the verification. However, we pay attention to the generation process of these parameters, which have nothing to do with the secret value a to be proved.
2. Non-interactive
The non-interactive transformation is also very easy. On the basis of the interactive one, the process of Bob randomly generating c is changed to the Hash form of the parameter:
Implementation based on elliptic curve
First, Alice calculates A = G x [a], where the private key a takes the value [0, n-1], and then publishes the public key A;
Then, Alice proves to Bob that she knows the private key a corresponding to A without revealing a:
If check is true, then we can prove that Alice knows a , as follows:
The non-interactive implementation is the same as the above-mentioned finite field-based implementation, and will not be described in detail.
Weak Fiat-Shamir transform
In the non-interactive implementation above, the random number:
This is a correct and safe way to generate, but unfortunately, in some early papers, this process was not rigorously described, but simply described as:
This presents a security issue, which we call the weak Fiat-Shamir transform, which can be used to forge proofs by pre-computing A and deceiving the verifier.
Reconstruct the parameters (A, r) using:
1. Generate a random value
2. Calculate a=(v-r)/c, the calculation method remains unchanged
3. Calculation
We can see that A becomes a parameter independent of a, and substitute it into the verification equation:
can be equal to V.
This means that an attacker can pass the protocol authentication without knowing the secret value.
There are also some papers [3] that describe this process as follows:
The content expressed is the same.
Bingxin Vulnerability
The Trail of Bits team published an article [2] pointing out that there are vulnerabilities in the Fiat-Sharmir implementation in ZKP systems such as Bulletproofs and Plonk, which allows malicious users to forge proofs for random statements.
Taking Plonk as an example, in Round 2, 3, 4, and 5 of proof generation, the Fiat-Shamir algorithm was used to generate random numbers.
In the paper [3], many open source implementations of modern zero-knowledge proof systems were surveyed and 36 were found to use weak Fiat-Shamir transformations, including Bulletproofs, Plonk, Spartan, and Wesolowski's VDF. An attacker can generate a proof that passes verification without knowing the valid proof secret.
Vulnerability Examples
1. gnark
Here, fs is an instance of Fiat-Shamir computation. When calculating the z(X) parameter in Round2 proof, the public input is not bound to the challenge, which makes it possible to forge the proof information.
2. snark
Also, since publicSignals are not included, the proof information can be forged.
Summarize
From the disclosed content, we can see the universality and widespread nature of this vulnerability. It will cause serious harm to zero-knowledge proofs. In practical applications, we need to pay attention to reviewing the correctness of the Fiat-Shamir implementation and adding public witness data to random number generation to prevent attackers from forging proofs.
Finally, we would like to thank Safeheron, a leading one-stop digital asset self-custody service provider, for providing professional technical advice.
Reference Documents:
[1]. https://datatracker.ietf.org/doc/html/rfc8235
[2]. https://blog.trailofbits.com/2022/04/13/part-1-coordinated-disclosure-of-vulnerabilities-affecting-girault-bulletproofs-and-plonk/
[3]. https://eprint.iacr.org/2023/691.pdf