The Frozen Heart vulnerability in Girault’s proof of knowledge

By Jim Miller

 

In part 1 of this series, we disclosed critical vulnerabilities that break the soundness of multiple implementations of zero-knowledge proof systems. This class of vulnerability, which we dubbed Frozen Heart, is caused by insecure implementations of the Fiat-Shamir transformation that allow malicious users to forge proofs for random statements. The vulnerability is general and can be applied to any proof system that implements the Fiat-Shamir transformation insecurely. In this post, I will show how to exploit a Frozen Heart vulnerability in Girault’s proof of knowledge.

Zero-Knowledge Proofs and the Fiat-Shamir Transformation

This post assumes that you possess some familiarity with zero-knowledge proofs. If you would like to read more about them, there are several helpful blog posts and videos available to you, such as Matt Green’s primer. To learn more about the Fiat-Shamir transformation, check out the blog post I wrote explaining it in more detail. You can also check out ZKDocs for more information about both topics.

Girault’s Proof of Knowledge

In Girault’s proof of knowledge protocol, the prover proves that he knows the discrete log of a certain value over a composite modulus. In other words, a prover convinces a verifier that he knows some secret value, x, such that h = g-x mod N, where g is a high order generator and N is some composite modulus (e.g., N = p * q, where p and q are two primes). To learn more about the protocol, check out our description on ZKDocs. If you are familiar with Schnorr proofs, think of Girault’s proof of knowledge as Schnorr proofs over a composite modulus rather than a prime modulus.

The protocol is interactive by default, but it can be made non-interactive using the Fiat-Shamir transformation:

At a high level, the prover first computes the commitment, u, by generating a random value, r, and computing u = gr. The prover then obtains the random challenge value, e, (either from the verifier in the interactive version or from herself by using the Fiat-Shamir transformation in the non-interactive version) and calculates the final proof value, z = r + x * e. This protocol is proven to be secure as long as the discrete log can’t be computed over the group that is used and the Fiat-Shamir challenge is computed correctly.

The Frozen Heart Vulnerability in Girault’s Proof of Knowledge

But what happens if we don’t compute the Fiat-Shamir challenge correctly? Let’s look at an example. In ZenGo’s implementation of Girault’s proof of knowledge (before it was patched), e is computed by hashing g, N, and u, but not h (in this implementation, h is represented by statement.ni). In part 1 of this series, we introduced a rule of thumb for securely implementing the Fiat-Shamir transformation: the Fiat-Shamir hash computation must include all public values from the zero-knowledge proof statement and all public values computed in the proof (i.e., all random “commitment” values). Therefore, failure to include h in this computation introduces a Frozen Heart vulnerability, allowing malicious provers to forge proofs for random h values, even if they do not know its discrete log.

Let’s walk through how to exploit this Frozen Heart vulnerability. We first choose random values for both u and z. Since h is not included in the Fiat-Shamir implementation, we can now compute e = Hash(g,N,u). Next, we need to find an h value that will pass the verification check: u = gzhe mod N. We already know all of the values except for h: we generated u and z, we computed e, and g and N are both public. Therefore, we can solve for h:

<

p style=”text-align: center;”>u = gzhe mod N
he = ug-z mod N
einv = e-1 mod phi(N)
h = (ug-z)einv mod N

If we plug in this h value, we know the second verification check will pass because we chose h specifically to pass this check. The only other check performed is the check for the challenge value, e, but this check will pass as well because we’ve computed this value identically. Keep in mind that we simply picked a random u. This means that we don’t actually know the discrete log of u (i.e., it’s infeasible to find a value t such that gt = u mod N). Since we don’t know the discrete log of u, we don’t know the discrete log of h. However, we have tricked the verifier that this proof is valid, even without knowing this discrete log, which means we have successfully forged a proof.

Note: in order to compute e_inv, the malicious prover needs to be able to compute phi(N), which would require knowing the prime factors of N.

Frozen Heart’s Impact on Girault’s Proof of Knowledge

Frozen Heart vulnerabilities are critical in Girault’s proof of knowledge because they allow attackers to forge proofs. However, the impact of this vulnerability on an application using this proof system depends entirely on how the proof system is used. If Girault’s proof of knowledge is used simply for standalone public keys (i.e., keys that are not used as part of some larger protocol), then a Frozen Heart vulnerability may not be that severe.

The reason for this is that, for Girault’s scheme, a Frozen Heart vulnerability makes it possible to forge random h values. But that’s not any more powerful than generating a random x and computing h = g-x, which results in a random h that we can construct a proof for. However, if this proof system is used within a larger, more complex protocol—such as a threshold signature scheme, which requires that the proof be unforgeable—then a Frozen Heart vulnerability is likely very severe.

Even though Frozen Heart vulnerabilities might not be critical for Girault’s scheme (and Schnorr’s scheme, for the same reasons) in certain contexts, this is not true for more complex proof systems. To see this in more detail, check out the upcoming part 3 post of this series, in which we explore the Frozen Heart vulnerability on the Bulletproofs proof system.

*** This is a Security Bloggers Network syndicated blog from Trail of Bits Blog authored by James Miller. Read the original post at: https://blog.trailofbits.com/2022/04/14/the-frozen-heart-vulnerability-in-giraults-proof-of-knowledge/