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.

For example, suppose the expected outcome of the DKG protocol is $\{2, 3\}$, generating three shards in total, with any two parties capable of executing MPC signature or private key reconstruction. However, exploiting this vulnerability could result in $\{3, 3\}$ shards, where three shards are generated, but any two parties cannot execute MPC signature or private key reconstruction, requiring the participation of all three parties. In the worst case, if the DKG protocol implementation lacks comprehensive checks, it could even generate $\{3, 4\}$ shards. Since only three shards are actually saved, MPC signature or private key reconstruction can never be executed, leading directly to asset loss.

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:

Participants $P_1, P_2, \dots , P_n$ jointly generate a set of key shards under a $\{t, n\}$ threshold scheme, where any fewer thantparticipants have no knowledge of the actual private key.

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.

Given an elliptic curve group $\mathbb{G} = (g, q)$, each participant $(P_i)$ executes the following algorithm:

1. $P_i$ randomly generates a key $u_i \in Z_q$;
2. $P_i$ randomly selects a polynomial of degree $t-1$;

   • Choose $t-1$ random numbers $a_1 \in Z_q$;
   • Construct the polynomial $f_i(\nu) = u_i + a_1\nu + ... + a_{t-1}\nu^{t-1} \pmod q$, noting that $u_i$ is the secret value.
   • Calculate the commitment of VSSS (Verifiable Secret Sharing Scheme):

$c_i = (g^{u_i}, g^{a_1}, \dots, g^{a^{t-1}})$

1. $P_i$ distributes shards $f_i(1), f_i(2), ... , f_i(n)$ to participants $P_1, P_2, \dots , P_n$, and broadcasts $c_i$
2. $P_i$, upon receiving $f_j(i)$ from others,

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

$g^{f_j(i)} = \prod_k {c_{i, k}^{i^k}}$

• Calculates their own shard:

$x_i = \sum_{j \ne i} f_j(i) \pmod q.$

Taking $\{2, 3\}$ as an example, $P_1, P_2, P_3$ execute the DKG protocol and generate their respective shards $x_1, x_2, x_3$, as shown in the following diagram:

The private key $x$ (the actual private key) can be recovered with a threshold of 2, satisfying not only

$x \equiv x_1 \cdot \lambda_1 + x_2 \cdot \lambda_2 + x_3 \cdot \lambda_3 \pmod q$

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

$x \equiv x_1 \cdot \lambda_1' + x_2 \cdot \lambda_2' \pmod q$

$x \equiv x_1 \cdot \lambda_1'' + x_3 \cdot \lambda_3'' \pmod q$

$x \equiv x_2 \cdot \lambda_2'''+ x_3 \cdot \lambda_3''' \pmod q$

Here, each $\lambda$ denotes a Lagrange interpolation coefficient, which is public as it can be calculated from the publicly known index data, as follows:

$\lambda_i = \Pi_{j \in SubSet, j \ne i}{\frac{i}{i - j}} \pmod q$，$i \in SubSet$, $SubSet = \{1,2,3\}$

$\lambda_i' = \Pi_{j \in SubSet, j \ne i}{\frac{i}{i - j}} \pmod q$, $i \in SubSet$, $SubSet = \{1,2\}$

$\lambda_i'' = \Pi_{j \in SubSet, j \ne i}{\frac{i}{i - j}} \pmod q$, $i \in SubSet$, $SubSet = \{1,3\}$

$\lambda_i''' = \Pi_{j \in SubSet, j \ne i}{\frac{i}{i - j}} \pmod q$, $i \in SubSet$, $SubSet = \{2,3\}$

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:

A single malicious participant ($P_i$), to modify the final shard threshold from $t$ to $t'$, where $t' > t$, executes the following malicious protocol:

1. $P_i$ randomly generates a key $u_i \in Z_q$;
2. $P_i$ randomly selects a polynomial of degree $t'-1$, noting that this $t'$ is different from the expected $t$, $t' > t$;

   • Choose $t'-1$ random numbers $a_1 \in Z_q$;
   • Construct the polynomial $f_i(\nu) = u_i + a_1\nu + ... + a_{t-1}\nu^{t'-1}$, noting that u_i is the secret value.
   • Calculate the commitment of VSSS (Verifiable Secret Sharing Scheme):

$c_i = (g^{u_i}, g^{a_1}, \dots, g^{a^{t'-1}})$

1. $P_i$ distributes shards $f_i(1), f_i(2), ... , f_i(n)$ to participants $P_1, P_2, \dots , P_n$, and broadcasts $c_i$ to everyone.
2. $P_i$, upon receiving $f_j(i)$ from others,

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

$g^{f_j(i)} = \prod_k {c_{i, k}^{i^k}}$

• Calculates their own shard:

$x_i = \sum_{j \ne i} f_j(i) \pmod q$

As a result, when the DKG protocol ends, the final shards $x_1, x_2, \dots, x_3$ have the threshold modified to the malicious participant's $t'$, higher than the expected thresholdt. Taking $\{2, 3\}$ as an example, if $P_1$ is the malicious party, and $P_1, P_2, P_3$ execute the DKG protocol, they generate their respective shards $x_1, x_2, x_3$, as shown in the following diagram:

Note that the threshold of $x_1, x_2, x_3$ is maliciously modified to 3, not the expected 2. This means that $x$ cannot be reconstructed with a threshold of 2, and the attack is successful. The following equations do not hold:

$x \equiv x_1 \cdot \lambda_1' + x_2 \cdot \lambda_2' \pmod q$

$x \equiv x_1 \cdot \lambda_1'' + x_3 \cdot \lambda_3'' \pmod q$

$x \equiv x_2 \cdot \lambda_2''' + x_3 \cdot \lambda_3''' \pmod q$

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.

Specifically, if the DKG protocol's expected threshold is $(t, n)$, meaning any $t$ parties can recover the private key/signature, then a single malicious attacker can potentially modify the threshold to $(T, n)$.

The specific impact analysis is as follows:

Scenario 1: $n \ge T \gt t$. Simply elevate the threshold for recovering the private key/signature. For instance, if three shards $x_1, x_2, x_3$ are generated with an expected threshold of 2, and it's maliciously modified to 3, all three shards must participate to successfully recover the private key/MPC signature.

Scenario 2: $T \gt n$. There are 2 cases:

• 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.

Note: There is a special case where if $n == t$ (e.g., shard modes like $\{3,3\}$, $\{5,5\}$, $\{10,10\}$, etc.) and necessary private key recoverability checks are in place, this scenario is not affected by the vulnerability.

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.

Specifically: $P_i$, upon receiving $f_j(i)$ from others,

• Verifies the validity of the shard:

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

$g^{f_j(i)} = \prod_k {c_{i, k}^{i^k}}$

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

$len(c_i) == t$

• Calculate their own shard:

$x_i = \sum_{j \ne i} f_j(i) \pmod q$

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

For specific fixes, refer to:

• https://github.com/Safeheron/safeheron-crypto-suites-cpp/commit/5531ce457a6de958cd0a5281d0db233188feb6d6

• https://github.com/Safeheron/multi-party-sig-cpp/commit/71da5cd3b7bb91f1abcfe5dc251d788bdacdef89

Conclusion

After understanding the vulneribility and its exploitation method, it is clear that this is a vulnerability at the protocol implementation level. The damage caused by exploiting this vulnerability varies depending on the situation and can lead to extremely serious consequences in extreme cases. Safeheron's SaaS products, using a $\{3,3\}$ threshold scheme and having necessary recoverability checks (based on zero-knowledge proof), is not affected by this vulnerability.

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.

---

References

[1] Secret sharing

[2] Verifiable secret sharing

[3] How to share a secret

[4] A Practical Scheme for Non-interactive Verifiable Secret Sharing

[5] Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing

[6] GG18: Fast Multiparty Threshold ECDSA with Fast Trustless Setup

[7] GG20: One Round Threshold ECDSA with Identifiable Abort

[8] CMP: UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts

[9] DMZ21: Promise Sigma-protocol: How to Construct Efficient Threshold ECDSA from Encryptions Based on Class Groups

[10] FROST: Flexible Round-Optimized Schnorr Threshold Signatures

[11] Breaking the shared key in threshold signature schemes