SlowMist: Exploring the Frozen Heart Vulnerability in the Fiat-Shamir Scheme
Background
The Frozen Heart vulnerability was first named by the Trail of Bits team. The term “Frozen” represents the Forging Of Zero Knowledge proofs, and “Heart” indicates that the Fiat-Shamir transformation is central to many proof systems. The vulnerability refers to the use of a “weak Fiat-Shamir” transformation. In this, only parts of the prover’s messages are hashed, excluding public information (like parameters, public inputs, etc.), leading to arising security issues.
In the following sections, we will provide a thorough analysis of this vulnerability, starting with a discussion about what the Fiat-Shamir transformation is.
Fiat-Shamir Transformation
The Fiat-Shamir Transformation, also known as the Fiat-Shamir Heuristic or Fiat-Shamir Paradigm, was introduced by Fiat and Shamir in 1986. It’s a transformation used to turn interactive zero-knowledge proof protocols into non-interactive ones. It accomplishes this by substituting the random challenges in the protocol with the output of a hash function. This substitution allows the prover to generate and send proofs to the verifier without the need for an interactive challenge and response.
Schnorr proofs are an example of an interactive zero-knowledge proof protocol. They allow the prover to prove to the verifier that a statement is true without revealing the details of the statement. The verifier can interactively verify this. Schnorr proofs are often used in situations where the provider needs to demonstrate knowledge of a secret value without revealing the secret value itself.
With the help of the Fiat-Shamir transformation, Schnorr’s interactive proof can be modified into a non-interactive one.
As previously noted, Schnorr can be implemented on finite fields or elliptic curves (EC), with the technical specifications remaining largely the same, just with different underlying cyclic groups. Below, we primarily describe these two processes in the context of finite fields.
Notations:
- Alice: Assumed identity of the prover in the protocol
- Bob: Assumed identity of the verifier in the protocol
- a | b: a divides b
- a || b: Concatenation of a and b
- [a, b]: Integer interval, including a and b
- t: The bit length of the challenge selected by Bob
- H: A secure cryptographic hash function
- p: A large prime number
- q: A large prime factor of p-1, meaning q | p-1
- Zp^*: The multiplicative group of integers modulo p
- Gq: A subgroup of Zp^* with prime order q
- g: A generator of Gq
- g^d: g to the power d
- a mod b: a modulo b
- Fp: A finite field with p elements, where p is a prime number
Implementation Based on Finite Fields
1. Interactive
Firstly, Alice calculates A = g^a mod p , where the private key a is chosen from the interval [0, q-1] . Then, she publicly releases the public key A .
Next, without disclosing a , Alice proves to Bob that she knows the private key a corresponding to A :
If the check returns true, it can be confirmed that Alice knows a. The underlying principle is as follows:
Here, the need for Bob to generate a random c is because if an attacker knows this value before A is disclosed, they can forge a proof without knowing the actual a . The attacker’s method of forging (A, V, r) is as follows:
1) Generate a random value r
2) The calculation method for V remains unchanged, set
Upon receiving these three parameters, the Verifier substitutes them into the verification formula, and the verification will still pass. However, upon closely observing the generation process of these parameters, they have no connection whatsoever with the secret value a that needs to be proven.
2. Non-Interactive
Modifying for non-interactive is also straightforward. On the interactive basis, change Bob’s process of randomly generating c to the hash of the parameters:
Implementation Based on Elliptic Curves
Firstly, Alice computes A = G * [a] , where the private key a is selected from the interval ( [0, n-1] . Then, she publicly reveals the public key A
Following this, without revealing a , Alice proves to Bob that she knows the private key a corresponding to A:
If the check is true, then it can be proven that Alice knows a . The principle is as follows:
The non-interactive implementation method is the same as the implementation based on finite fields mentioned above, so there is no need to elaborate further.
Weak Fiat-Shamir Transformation
In the non-interactive implementation process described above, the random number:
is a proper and secure way of generation. Unfortunately, in some early papers, this process was not rigorously described and was simply mentioned as:
This poses a security issue, termed as the weak Fiat-Shamir transformation, which can be exploited to forge proofs by precomputing A, thereby misleading the verifier.
This presents a security issue, known as the weak Fiat-Shamir transformation. It can be exploited to forge proofs by precomputing A , thus deceiving the verifier.
To reconstruct the parameters (A, r) , use the following method:
1. Generate a random value r.
2. Calculate a=(v-r)/c, with the calculation method unchanged.
3. Calculate
We can see that this A has now become a parameter unrelated to a . Substituting into the verification equation:
Let it equal V .
In other words, an attacker can pass the protocol verification without knowing the secret value.
Some other papers [3] describe the process as follows:
Frozen Heart Vulnerability
The Trail of Bits team has published an article [2] pointing out that vulnerabilities exist in the Fiat-Shamir implementation in ZKP systems like Bulletproofs and Plonk, allowing malicious users to forge proofs for random statements.
For example, in Plonk, the Fiat-Shamir algorithm is used to generate random numbers in rounds 2, 3, 4, and 5 of the proof generation.
The paper [3] investigated many open-source implementations of modern zero-knowledge proof systems and found that 36 of them utilized the weak Fiat-Shamir transformation, including Bulletproofs, Plonk, Spartan, and Wesolowski’s VDF. Attackers can generate proofs that pass verification without needing to know the effective proof secrets.
Vulnerability Example
1. Gnark
Here, fs is an instance of a Fiat-Shamir calculation. In the Round2proof computation for the z(X) parameter, due to not binding the public input to the challenge, it results in the possibility of forging proof information.
2. Snarkjs
Similarly, not including publicSignals results in the possibility of forging proof information.
Conclusion
From the disclosed content, it is evident that this vulnerability is both generic and widespread. It poses serious threats to zero-knowledge proofs. In practical applications, it is crucial to carefully review the correctness of the Fiat-Shamir implementation and include public witness data in the random number generation to prevent attackers from forging proofs.
Lastly, a special thanks to Safeheron, the leading one-stop digital asset self-custody service provider, for their professional technical advice.
References:
1. https://datatracker.ietf.org/doc/html/rfc8235
3. https://eprint.iacr.org/2023/691.pdf
About SlowMist
SlowMist is a blockchain security firm established in January 2018. The firm was started by a team with over ten years of network security experience to become a global force. Our goal is to make the blockchain ecosystem as secure as possible for everyone. We are now a renowned international blockchain security firm that has worked on various well-known projects such as Huobi, OKX, Binance, imToken, Crypto.com, Amber Group, Klaytn, EOS, 1inch, PancakeSwap, TUSD, Alpaca Finance, MultiChain, Cheers UP, etc.
SlowMist offers a variety of services that include by are not limited to security audits, threat information, defense deployment, security consultants, and other security-related services. We also offer AML (Anti-money laundering) software, Vulpush (Vulnerability monitoring) , SlowMist Hacked (Crypto hack archives), FireWall.x (Smart contract firewall) , Safe Staking and other SaaS products. We have partnerships with domestic and international firms such as Akamai, BitDefender, FireEye, RC², TianJi Partners, IPIP, etc.
By delivering a comprehensive security solution customized to individual projects, we can identify risks and prevent them from occurring. Our team was able to find and publish several high-risk blockchain security flaws. By doing so, we could spread awareness and raise the security standards in the blockchain ecosystem.
Website：
https://www.slowmist.com
Twitter：
https://twitter.com/SlowMist_Team
Github：
https://github.com/slowmist/
