Security Analysis of DKG Threshold Raising Vulnerability

02/21/2024

By Max

Background

Trail of Bits recently disclosed a vulnerability in the MPC threshold signature scheme that affects the DKG (Distributed Key Generation) protocol. “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”, according to Trail of Bits [11]. In extreme cases, it may even result in the private key being unable to be reconstructed.

On January 3, 2024, Trail of Bits disclosed a security vulnerability to Safeheron via email. After analysis and research, Safeheron patched the vulnerability on January 4, 2024, and publicly released a fix patch (see the "Remediation" section of this article). With permission from Trail of Bits, Safeheron also promptly informed security partners and other vendors about this vulnerability.

Safeheron's SaaS product is not affected by this vulnerability.

DKG (Distributed Key Generation) Protocol

In Secure Multi-Party Computation, there is no trusted third-party dealer, and multiple parties jointly generate the secret. At no time and no place does the complete secret appear.

To achieve this goal, in 1991, a distributed key generation (DKG) protocol was proposed [5], an extension based on Shamir's secret sharing scheme [1] [2] [3] [4]. The protocol achieves the following objective:

Typical MPC multisignature protocols, such as GG18[6], GG20[7], CMP[8] based on threshold schemes, Frost[10], and DMZ21[9] all define the distributed key generation (DKG, Distributed Key Generation) sub-protocol. The shard generation principles of those protocols are similar. Now, let's introduce the core idea.

- Calculate the commitment of VSSS (Verifiable Secret Sharing Scheme):

- Verifies the validity of the shard; if the following equation holds, the shard is valid; otherwise, it is invalid:

Calculates their own shard:

but also the following equations, meaning any two key shards can reconstruct the private key:

Note that for typical MPC multisignature protocols, like GG18 and GG20, the threshold for MPC multi-signature and private key reconstruction is the same. For better understanding, only private key reconstruction is mentioned here.

Generally, MPC multisignature can be completed only if the private key can be reconstructed or vice versa. It's worth emphasizing again that the private key will never be reconstructed during MPC multisignature, nor will it reveal any information about each other's private key shard.

The Attack

In the specific implementation of the DKG protocol, and other MPC signature protocols, if the verification of the commitment for VSSS only verifies the correctness of the shard but not the degree of the random polynomial, the following attack method can be used:

- Calculate the commitment of VSSS (Verifiable Secret Sharing Scheme):

- Verifies the legitimacy of the shard; if the following equation holds, the shard is valid; otherwise, it is invalid:

Calculates their own shard:

Impact

Using the above attack method, a single malicious attacker can potentially raise the final threshold of shards. The DKG protocols in typical MPC multisignature protocols, such as GG18[6], GG20[7], CMP[8] based on threshold schemes, Frost[10], and DMZ21[9] are all affected.

The specific impact analysis is as follows:

If the DKG protocol includes comprehensive checks, such as private key recoverability verification (refer to Safeheron implementation), then the DKG protocol will not complete successfully, and no further problems will occur.
If there are no additional checks in the DKG protocol, then the DKG protocol will complete normally, but the final shards generated will never be able to recover the private key or signature, leading directly to asset loss. It's worth noting that some open-source algorithm libraries lack such checks, leading to serious consequences.

Remediation

To fix the vulnerability, it is necessary to check the length of the commitment in the Feldman VSSS algorithm to ensure it matches the threshold.

Verifies the validity of the shard:
- Validate the equation. If the following equation does not hold, the shard is invalid.

Validate the equation. If the following equation does not hold, the shard is invalid.

Calculate their own shard:

The essence of the remediation is to constrain the degree of the random polynomial to lock the shard threshold.

For specific fixes, refer to:

Conclusion

Achieving trustworthy security requires persistent meticulous refinement. "Rome wasn't built in a day." Stay humble, stay grounded, and let security truly serve the industry.

The responsible security disclosure by the Trail of Bits team demonstrates the openness and collaboration in the security industry. Safeheron also actively engages in communication with more security partners, and we are pleased to be part of this remediation and disclosure process.

Creating a secure industry environment requires dialogue with vendors, security practitioners, and users. Through collective dedication and effort from all sides, security can empower the industry.