By Fredrik Dahlgren

Today we are disclosing a denial-of-service vulnerability that affects the Pedersen distributed key generation (DKG) phase of a number of threshold signature scheme implementations based on the Frost, DMZ21, GG20, and GG18 protocols. The vulnerability allows a single malicious participant to surreptitiously raise the threshold required to reconstruct the shared key, which could cause signatures generated using the shared key to be invalid.

We first became aware of this vulnerability on a client engagement with Chainflip last year. When we reviewed Chainflip’s implementation of the Frost threshold signature scheme, we noticed it was doing something unusual—something that we had never seen before. Usually, these kinds of observations are an indication that there is a weakness or vulnerability in the codebase, but in this case, Chainflip’s defensive coding practices actually ended up protecting its implementation from a vulnerability. By being extra cautious, Chainflip also avoided introducing a vulnerability into the codebase that could be used by a single party to break the shared key created during the key-generation phase of the protocol. When we realized this, we became curious if other implementations were vulnerable to this issue. This started a long investigation that resulted in ten separate vulnerability disclosures.

What is the Pedersen DKG protocol?

The vulnerability is actually very easy to understand, but to be able to explain it we need to go through some of the mathy details behind the Pedersen DKG protocol. Don’t worry—if you understand what a polynomial is, you should be fine, and if you’ve heard about Shamir’s secret sharing before, you’re most of the way there already.

The Pedersen DKG protocol is based on Feldman’s verifiable secret sharing (VSS) scheme, which is an extension of Shamir’s secret sharing scheme. Shamir’s scheme allows n parties to share a key that can then be reconstructed by t + 1 parties. (Here, we assume that the group has somehow agreed on the threshold t and group size n in advance.) Shamir’s scheme assumes a trusted dealer and is not suitable for multi-party computation schemes where participants may be compromised and act maliciously. This is where Feldman’s VSS scheme comes in. Building on Shamir’s scheme, it allows participants to verify that shares are generated honestly.

Let G be a commutative group where the discrete logarithm problem is hard, and let g be a generator of G. In a (t, n)-Feldman VSS context, the dealer generates a random degree t polynomial p(x) = a₀ + a₁ x + … + a_t x^t, where a₀ represents the original secret to be shared. She then computes the individual secret shares as s₁ = p(1), s₂ = p(2), …, s_n = p(n). This part is exactly identical to Shamir’s scheme. To allow other participants to verify their secret shares, the dealer publishes the values A₀ = g^a₀, A₁ = g^a₁, …, A_t = g^a_t. Participants can then use the coefficient commitments (A₀, A_i, …, A_t) to verify their secret share s_i by recomputing p(i) “in the exponent” as follows:

• Compute V = g^p(i) = g ^{s _i}.
• Compute V’ = g^p(i) = g^{a₀ + a₁ i + … + a_t i t} = ∏_k (g^a_k) ^{i k} = ∏_k A_k^{i k}.
• Check that V = V’.

As in Shamir’s secret sharing, the secret s = a₀ can be recovered with t + 1 shares using Lagrange interpolation.

In Feldman’s VSS scheme, the shared secret is known to the dealer. To generate a shared key that is unknown to all participants of the protocol, the Pedersen DKG protocol essentially runs n instances of Feldman’s VSS schemes in parallel. The result is a (t, n)-Shamir’s secret sharing of a value that is unknown to all participants: each participant P_i starts by generating a random polynomial p_i(x) = a_i,0 + a_i,1 x + … + a_i,t x^t of degree t. She publishes the coefficient commitments (A_i,0 = g^a_i,0, A_i,1 = g^a_i,1, …, A_i,t = g^a_i,t) and then sends the secret share s_{i, j} = p_i(j) to P_j. (Note that the index j must start at 1, otherwise P_i ends up revealing her secret value a_i,0 = p_i (0).) P_j can check that the secret share s_{i, j} was computed correctly by computing V and V’ as above and checking that they agree. To obtain their secret share s_j, each participant P_j simply sums the secret shares obtained from the other participants. That is, they compute their secret share as

s_j = s_{1, j} + s_{2, j} + … + s_{n, j} = p₁(j) + p₂(j) + … + p_n(j)

Notice that if we define p(x) as the polynomial p(x) = p₁(x) + p₂(x) + … + p_n(x), it is easy to see that what we obtain in the end is a Shamir’s secret sharing of the constant term of p(x), s = p(0) = a_{1, 0} + a_{2, 0} + … + a_{n, 0}. Since the degree of each polynomial p_i(x) is t, the degree of p(x) is also t, and we can recover the secret s with t + 1 shares using Lagrange interpolation as before.

(There are a few more considerations that need to be made when implementing the Pedersen DKG protocol, but they are not relevant here. For more detail, refer to any of the papers linked in the introduction section.)

Moving the goalposts in the Pedersen DKG

Now, we are ready to come back to the engagement with Chainflip that started all of this. While reviewing Chainflip’s implementation of the Frost signature scheme, we noticed that the implementation was summing the commitments for the highest coefficient A_1,t + A_1,t + … + A_n,t and checking if the result was equal to the identity element in G, which would mean that the highest coefficients of the resulting polynomial p(x) was 0. This is clearly undesirable since it would allow fewer than t + 1 participants to recover the shared key, but the probability of this happening is cryptographically negligible (even with actively malicious participants). By checking, Chainflip reduced this probability to 0.

This made us wonder, what would happen if a participant used a polynomial p_i(x) of a different degree than t in the Pedersen DKG protocol? In particular, what would happen if a participant used a polynomial p_i(x) of degree T greater than t? Since p(x) is equal to the sum p₁(x) + p₂(x) + … + p_n(x), the degree of p(x) would then be T rather than t, meaning that the signing protocol would require T + 1 rather than t + 1 participants to complete successfully. If this change were not detected by other participants, it would allow any of the participants to surreptitiously render the shared key unusable by choosing a threshold that was strictly greater than the total number of participants. If the DKG protocol were used to generate a shared key as part of a threshold signature scheme (like one of the schemes referenced in the introduction), any attempt to sign a message with t + 1 participants would fail. Depending on the implementation, this could also cause the system to misattribute malicious behavior to honest participants when the failure is detected. More seriously, this attack could also be used to render the shared key unusable and unrecoverable in most key-resharing schemes based on Feldman’s VSS. This includes the key resharing schemes described in CGGMP21 and earlier versions of Lindell22. In this case, the shared key may already control large sums of money or tokens, which would then be irrevocably lost.

Clearly, this type of malicious behavior could be prevented by simply checking the length of the coefficient commitment vector (A_i,0, A_i,1, …, A_i,T) published by each participant and aborting if any of the lengths is found to be different from t + 1. It turned out that Chainflip already checked for this, but we were curious if other implementations did as well. All in all, we found ten implementations that were vulnerable to this attack in the sense that they allowed a single participant to raise the threshold of the shared key generated using the Pedersen DKG without detection. (We did not find any vulnerable implementations of key-resharing schemes.)

Disclosure process

We reached out to the maintainers of the following vulnerable codebases on January 3, 2024:

• The reference implementation of Frost, maintained by Chelsea Komlo
• The ZCash Foundation’s implementation of Frost
• Penumbra’s implementation of Frost over decaf377
• Frost-Dalek, maintained by Isis Lovecruft
• Toposware’s implementation of ICE-FROST
• Trust Machines’ implementation of WSTS based on Frost
• FROST-BIP340, maintained by Jesse Possner
• ZenGo-X’s implementations of GG18 and GG20
• Safeheron’s implementation of GG20
• LatticeX’s Open TSS implementation of GG20

Seven of the maintainers responded to acknowledge that they had received the disclosure. Four of those maintainers (Chelsea Komlo, Jesse Possner, Safeheron, and the ZCash Foundation) also reported that they either already have, or are planning to resolve the issue.

We reached out again to the three unresponsive maintainers (Toposware, Trust Machines, and LatticeX) on February 7, 2024. Following this, Toposware also responded to acknowledge that they had received our disclosure.

*** This is a Security Bloggers Network syndicated blog from Trail of Bits Blog authored by Lauren Miorcec. Read the original post at: https://blog.trailofbits.com/2024/02/20/breaking-the-shared-key-in-threshold-signature-schemes/