The Frozen Heart vulnerability in Bulletproofs

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. In part 2, we demonstrated how to exploit a Frozen Heart vulnerability in a specific proof system: Girault’s proof of knowledge. In this post, we will demonstrate such an exploit against another proof system: Bulletproofs.

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.

Bulletproofs

Bulletproofs are complex and efficient zero-knowledge range proofs, in which a prover proves that a certain secret value lies within a predefined range without having to reveal the value itself.

Bulletproofs operate over a cryptographic primitive known as a Pedersen commitment, a specific type of commitment scheme. Using a commitment scheme, a party can create a commitment, which binds the party to a secret value but does not reveal any information about this value. Later, this party can decommit or reveal this commitment; if revealed, and if the scheme is secure, the other party can be sure that the revealed value is the same as the original committed value.

To create a Pedersen commitment for value x, you generate a random gamma and then compute the commitment using comm = (gx)(hgamma): g and h are different generators of your finite group, and the discrete log of h relative to g is unknown (i.e., it’s infeasible to find a such that ga = h). Since Pedersen commitments are secure, the commitment does not reveal any information about x, and it’s impossible to equivocate on the commitment; this means you cannot publish different x’ and gamma’ values that produce the same commitment (assuming the discrete log between g and h is unknown).

The fact that the Pedersen commitment does not reveal any information can be problematic for complex protocols, such as those that need to guarantee that the secret value falls within a predefined range (e.g., to restrict these values to prevent integer overflows). However, using Bulletproofs, we can prove that our commitment corresponds to a value within a predefined range, such as [0, 232), without revealing the specific input value.

Unfortunately, the Bulletproofs protocol is too complex to walk through in detail in this post. To describe the Frozen Heart vulnerability, I will present the Bulletproofs protocol step-by-step, but this will be difficult to follow if you have not seen it before. If you’d like to learn more about how Bulletproofs work, you can find a number of blogs and videos online, such as this write-up.

The Frozen Heart Vulnerability in Bulletproofs

Bulletproofs have several Fiat-Shamir transformations (the exact number depends on the parameters being used), which could be abused in different ways. In this section, I will walk through how to exploit one such vulnerability. In fact, this vulnerability is the result of an error made by the authors of the original Bulletproofs paper, in which they recommend using an insecure Fiat-Shamir implementation. ING Bank’s zkrp, SECBIT Labs’ ckb-zkp, and Adjoint, Inc.’s bulletproofs were all affected by this issue.

Bulletproofs operate over Pedersen commitments, which take the form V = (gv)(hgamma). As a reminder, the goal of Bulletproofs is to prove that the secret value, v, lies in a predefined range. For the purposes of this post, we will use [0, 232) as our predefined range. Here is the formal zero-knowledge proof statement for Bulletproofs:

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). So we want to ensure that all of the public values in this statement (g, h, V, n) are in the Fiat-Shamir calculation, along with the random commitments, which we haven’t covered yet.

As is the case in most cryptography papers, the Bulletproofs algorithm is presented in its interactive version. Here is the prover’s role, as presented in the paper:

(To be clear, this is not the full version of the protocol. There is a significant optimization to decrease the size of the proof sent in step (63) that is described later in the Bulletproofs paper, but this is irrelevant for the purposes of this exploit.)

Once the prover sends the final proof in step (63), the verifier will need to verify it by performing the following checks:

In steps (49)/(50) and (55)/(56) of the prover’s protocol, three different Fiat-Shamir challenge values need to be generated: x, y, and z. However, the authors recommend using an insecure computation for these values:

According to the authors, we should set y = Hash(A,S), z = Hash(A,S,y), and (following their description) x = Hash(A,S,y,z,T1,T2). This violates our rule of thumb: none of the public values from the statement—most importantly, V—are included. This is a Frozen Heart vulnerability! This vulnerability is critical; as you may have guessed, it allows malicious provers to forge proofs for values that actually lie outside of the predefined range.

Now, to actually exploit this, a malicious prover can do the following:

• Set v equal to any value in the range. So let’s just say v = 3.
• Pick a random gamma value.
• Generate aL, aR, A, and S as expected (according to steps (41), (42), (44), and (47), respectively) using these v and gamma values.
• Compute t1 and t2 as described in the Bulletproofs paper (this is not in the above figure but is described in text in the paper), and then compute values t1’ and t2’ by randomly generating numbers. When computing T1 and T2, replace t1 with t1’ and t2 with t2’. So, to be clear, we set Ti = (gt’_i)(htau_i) (as expected, but we switch ti with ti’).
• Compute the rest of the values (l, r, t_hat, tau_x, mu) according to the protocol.
• Finally, compute a new V using the same gamma but with a new v’ value. Specifically, set v’ = 3 + (t1 - t’1)(x/z2) + (t2 - t’2)(x2/z2) (You’ll see why this was chosen like this in a second). Here, 3 comes from setting v = 3 in step 1.

Now, recall all of the verification checks from above. The only values we computed differently than expected were T1, T2, and V. Since we computed the other values as expected, all of the checks will pass automatically, with the exception of check (65), which depends on T1, T2, and V. But because x, y, and z are computed independently of V, we can compute a malicious V value that depends on these values and will pass check (65). Let’s see how this works:

First, let’s simplify the left-hand side of check (65):

LHS = (gt_hat)(htau_x)
= (g[t0 + t1 * x + t2 * x2])(h[tau2 * x2 + tau1 * x + z2 * y])

Now, let’s simplify the right-hand side of check (65):

RHS = (Vz2)(gdelta(y,z))(T1x)(T2x2)
= (Vz2)(gdelta(y,z))[(gt’1)(htau1)]x[(gt’2)(htau2)]x2

Now, if you look at the v’ value that we picked for V, you’ll see that the T1 and T2 exponents in g will cancel out the exponents in g for V. So the right-hand side is simplified as follows:

= g[3z2 + t1 * x + t2 * x2 + delta(y,z)]h[gamma * z2 + tau1 * x + tau2 * x2]

We can see that the exponent in h is identical on both sides. All we have to do now is check that the exponents in g match.

In the g exponent on the left-hand side, we have t0 + t1 * x + t2 * x2.

In the g exponent on the right-hand side, we have 3z2 + delta(y,z) + t1 * x + t2 * x2.

And t0 is defined in the original paper to be:

This is exactly right, meaning we’ve successfully forged a proof.

To be clear, this is a forgery because we just submitted this proof for the newly computed V value, where v was set to be v’ = 3 + (t1 - t’1)(x / z2) + (t2 - t’2)(x2 / z2). Since x and z are random Fiat-Shamir challenges, v’ will end up being a random value in the interval [0, group order). Since the group order is usually much larger than the interval in question (here, 232), v’ will be a value outside of the range with overwhelming probability, but the proof will still pass. If, for whatever reason, v’ is not outside of this range, a malicious actor could simply start the same process over with new random values (e.g., new gamma, new t’1, etc.) until the desired v’ value is obtained.

Frozen Heart’s Impact on Bulletproofs

Frozen Heart vulnerabilities are critical because they allow attackers to forge proofs, but their impact on the surrounding application depends on how the application uses the proof system. As we saw for the Schnorr and Girault proof systems in part 2 of this series, there may be contexts in which these vulnerabilities are not critical. However, this is unlikely to be the case for Bulletproofs.

In our example, we were able to produce a forgery for a random value in the group order. In most applications, the predefined range for the range proof is typically much smaller than the size of the group order. This means that, although the specific value cannot be chosen, an attacker could easily produce a proof for values outside of the desired range. In the majority of contexts we’ve seen Bulletproofs being used, this is severe.

Watch out for the final part of this series, in which we will explore the Frozen Heart vulnerability in an even more complex proof system: PlonK.

*** 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/15/the-frozen-heart-vulnerability-in-bulletproofs/