Analysis of Security Vulnerabilities in GG18/GG20 Protocol

Author: Max, Safeheron

Background

Recently, the Fireblocks team disclosed a 0-day vulnerability in the GG18, GG20, and Lindel 17 MPC protocols, which allows attackers to extract the real keys behind a set of MPC private key shares.

Before disclosing the issue, the Fireblocks team contacted Safeheron and engaged in proactive communication. The open-source GG18/GG20 MPC protocol developed by Safeheron is implemented strictly according to the paper's content, and using this version of the open-source algorithm may be susceptible to similar attacks. Before the vulnerability was disclosed, Safeheron had already fixed the vulnerabilities present in the open-source project, and the Fireblocks team also assisted in confirming the effectiveness of the patches.

The Fireblocks team constructed a POC using Safeheron's C++ implementation of the open-source GG18/GG20 protocol to demonstrate and help the community understand the vulnerability.

The GG18/GG20 MPC protocol in Safeheron's commercial service additionally introduces relevant zero-knowledge proofs from CMP20/CGGMP21, thus being unaffected by this vulnerability.

Scope of the Vulnerability

This article focuses on the impact of the vulnerability on GG18 and GG20. For the GG18/GG20 protocol, the attacker can construct a special Paillier key, allowing them to complete the attack during the MPC signing phase. Through a limited number of signatures, the attacker can deduce the private key shares of other participants.

The impact of this vulnerability is quite extensive, as it affects the security assumptions of the MPC protocol, meaning that almost all mainstream open-source implementations of the GG18/GG20 protocol are affected.

Vulnerability Principle

How can the MPC protocol be attacked? Common MPC protocols are provably secure under certain security assumptions, so attacks on MPC protocols often focus on the security assumptions that the protocol relies on. Security assumptions are like the foundation of the MPC protocol building; if the security assumptions fail, the entire MPC protocol will be affected.

Taking GG18/GG20 as an example, this MPC protocol relies on the security of the Paillier homomorphic encryption algorithm. The Paillier homomorphic encryption algorithm is designed based on the difficulty of the composite residuosity problem and is a widely used homomorphic encryption algorithm that supports addition operations. The vulnerability targets the construction of the Paillier homomorphic key, progressively compromising the $$MtA$$ protocol and related zero-knowledge proof protocols, ultimately forming an effective attack.

The core logic of the entire attack is as follows:

(1) In the KeyGen sub-protocol phase, the attacker constructs an insecure homomorphic key.
(2) In the Sign sub-protocol phase:
(a) In the pairwise running $$MTA$$ protocols, such as $$MtA(k,x)$$ and $$MtA(k,\gamma)$$, the attacker constructs an illegal $$k$$ value based on their insecure homomorphic key;
(b) Utilizing the properties of the insecure homomorphic key, the attacker constructs malicious zero-knowledge proofs to deceive other participants through verification;
(c) The attacker and the attacked party complete the signing and record the $$\mu$$ during the process.
(3) Repeat the Sign sub-protocol several times to calculate the private key shares of the other party based on the Chinese Remainder Theorem.

Attack Method

In this section, we detail the specifics of the attack. In a general MPC threshold multi-signature scenario, there are multiple participants, and these participants can attack each other pairwise, using the same attack method.

To facilitate the introduction of the attack method, let’s assume the MPC wallet is created and used by three parties: Party A, Party B, and Party C, with each party managing their respective private key shares $$xA$$, $$xB$$, and $$xC$$. Using this vulnerability, Party A can attack Party B and Party C to obtain their private key shares. This section will use "Party A attempts to attack Party B" as an example to illustrate how to extract Party B's private key share $$xB$$. (Party A can similarly extract Party C's private key share $$x_C$$, which will not be elaborated here.)

4.1 Preparation Phase - Constructing Insecure Homomorphic Keys

The first attack occurs during the execution of the KeyGen sub-protocol, which we can refer to as the attack preparation phase. In this phase, the attacker Party A successfully constructs an insecure Paillier homomorphic key.

The normal process for constructing a homomorphic key is as follows:

• Randomly select secure primes $$p, q \in \{0,1\}\^{1024}$$
• Calculate
• $$ N_A = p * q$$
• $$\lambda_A = (p-1)*(q-1)$$

The process for the attacker Party A to construct the homomorphic key is as follows:

• Randomly select primes $$(p1, p2, …, p{16}, q)$$, where $$pi$$ are distinct small primes, and $$q$$ is a large prime
• Calculate
• $$ NA = \Pii{pi} * q$$, with $$NA$$ being 2048 bits long
• $$\lambdaA = \Pii(p_i-1)*(q-1)$$

We can see that the Paillier public key $$N_A$$ constructed by the attacker Party A contains many small factors. Can the illegal Paillier key constructed by Party A deceive Party B? After all, a zero-knowledge proof needs to be constructed for Party B to verify.

A close examination of the $$KeyGen$$ protocol in GG18/GG20 shows that it only requires providing a $$ Square-Free $$ zero-knowledge proof. Since the Paillier homomorphic public key $$N_A$$ constructed by the attacker only contains distinct prime factors, this construction method can clearly pass the $$ Square-Free $$ zero-knowledge proof.

4.2 Attack Phase: Sign Sub-protocol

Note that the attack requires successfully executing the Sign sub-protocol 16 times. Let’s assume we are currently executing the $i$-th Sign sub-protocol.
In the Sign sub-protocol, the first few rounds need to run the $$MtA$$ protocol, referring to GG18 (https://eprint.iacr.org/2019/114.pdf) Section 4.2.

• $$ MtA(kA, \gammaB) : \alphaA + \betaB \leftarrow kA * \gammaB$$
• $$ MtA(kA, xB) : \muA + \nuB \leftarrow kA * xB$$

The normal calculation process is as follows:

• Randomly select $$k_A \in Zq$$
• Calculate $$Enc(k_A)$$
• Execute the $$MtA$$ protocol
• $$ MtA(kA, \gammaB) : \alphaA + \betaB \leftarrow kA * \gammaB$$
• $$ MtA(kA, xB) : \muA + \nuB \leftarrow kA * xB$$
• Generate a zero-knowledge proof for the ciphertext $$Enc(kA)$$ regarding the random number $$kA$$. Refer to GG18 (https://eprint.iacr.org/2019/114.pdf) A.1 Section Range Proof
• Subsequently, normally complete the MPC Sign sub-protocol.

The attacker's calculation process is as follows:

• Construct a special $$k_A$$ value
• Use the specially constructed $$k_A$$ value to normally execute the $$MtA$$ protocol
• Construct malicious zero-knowledge proofs to implement deception
• Subsequently, normally complete the MPC Sign sub-protocol.

Next, we will introduce the specific operation method.

Constructing a Special $$k_A$$ Value

The attacker does not use a random value but constructs $$kA$$ in the $i$-th MPC Sign sub-protocol as follows: ​$$ kA = NA / pi $$
Note that this specially constructed $$k_A \gg q\^3$$, which normally cannot pass the expected zero-knowledge proof. Here, $$q$$ is the order of the elliptic curve.

Constructing Zero-Knowledge Proofs

The GG18 protocol requires the attacker to provide a valid zero-knowledge proof during the $$MtA$$ running phase, referring to GG18 (https://eprint.iacr.org/2019/114.pdf) A.1 Section Range Proof. This zero-knowledge proof can prove:

• Witness: $kA' = 0 \ne kA$, other random numbers
• Statement: $Enc{NA}(kA)$ is the ciphertext of $$kA'$$, and satisfies $$k_A \in (-q\^3, q\^3) $$

Note that the above is an illegal Statement because:

• $$Enc{NA}(kA)$$ is not the ciphertext of $$kA'=0$$
• $$k_A \gg q\^3$$

Under normal circumstances, the Range Proof in the GG18 protocol here is completely valid, making it difficult for the attacker to construct a zero-knowledge proof that allows this Statement to pass verification.

So, how does the attacker Party A break through this obstacle? This is where the insecure Paillier key $$N_A$$ constructed by Party A in the KeyGen protocol phase comes into play. With the insecure Paillier key, there is an opportunity to construct malicious zero-knowledge proofs.

The zero-knowledge proof protocol description in GG18/GG20 is as follows:

In the verifier's verification process, the most important thing is to satisfy the equality constraint on the ciphertext (the red box part):

$$ u = \Gamma\^s s\^N c\^{-e} \pmod {N\^2} $$
The attack technique is to construct a reasonable challenge value $$e = Hash(…, w, )$$, satisfying: $$e \pmod {pi} = 0$$ Since $$c = (1+NA)\^kA * \rho\^NA \mod (NA\^2)$$, $$kA = NA/pi$$
$$\begin{align*}
c\^e \&= ((1+NA)\^kA * \rho\^NA)\^e \&\mod (NA\^2) \\
\&= (1+NA)\^{ekA} * \rho\^{eNA} \&\mod (NA\^2) \\
\&= (1+NA)\^{bpi * NA/pi} * \rho\^{eNA} \&\mod (NA\^2) \\
\&= \rho\^{eAN} \&\mod (NA\^2) \\
\&= Enc{NA}(0)\^e \&\mod (N_A\^2) \\
\end{align*}$$

Here, $$c$$ is "transformed" into the ciphertext of $$k_A'=0$$, successfully constructing the zero-knowledge proof.

Note that this can be achieved by violently iterating $$\gamma$$ during the construction process, continuously adding 1 and updating $$w$$, thus satisfying $$e \pmod {pi} = 0$$. Since the modulus $$pi$$ is a small prime, it can be successfully iterated through brute force.

Calculating the Mod $$p_i$$ Remainder of Party B's Private Key Share

The attacker and the attacked party complete the Sign sub-protocol and additionally record the $$\muA$$ value in the $$MtA$$ protocol. $$ \muA = kA * xB + \nuB \pmod {NA}$$
Considering the latest version of the GG18 paper, it is known that $$\nuB \le q\^5$$, $$ \muA = Dec{NA}(Enc{NA}(kA * xB + vB))$$ $$\begin{align*} \muA - (\muA \mod (NA/pi)) =\& Dec{NA}(Enc{NA}(kA * xB + \nuB)) - (Dec{NA}(Enc{NA}(kA * xB + \nuB)) \mod (NA/pi))\\ =\& (xB \mod pi) * (NA/pi) + \nuB - \nuB \\ =\& (xB \mod pi) * (NA/p_i)
\end{align*}$$

It can be concluded that:

$$xB \pmod {pi} = (\muA - (\muA \mod (NA/pi)))/(NA/pi) $$
Let $$ai = (\muA - (\muA \mod (NA/pi)))/(NA/p_i) $$

Noticing that all parameters on the right side of the equation are known to the attacker, the attacker can calculate $$ai$$ Thus obtaining: $$xB = ai \pmod {pi}$$

4.3 Final Phase: Calculating the Attacked Party's Private Key Share

After running 16 successful MPC Sign sub-protocols, we obtain

$$ xB = a1 \pmod {p1}$$ $$ xB = a2 \pmod {p2}$$
$$ … $$
$$ xB = a{16} \pmod {p_{16}}$$

Since $$p1 * p2 *… * p{16} > q$$, based on the Chinese Remainder Theorem, the attacker Party A can calculate Party B's private key share $$xB$$. The attack is successful.

4.4 Attack Effects

The GG18 paper has two implementation versions, the revised version and the old version, and the attack effects differ for different versions.

• In the revised version of the paper, the $$\betaB \< q\^5$$ used in the $$MtA$$ protocol (corresponding to $$\nuB$$ in the previous text) requires 16 signatures using the above attack method for the attacker to deduce the attacked party's private key share.
• In the old version of the paper, the $$\betaB \< NA$$ used in the $$MtA$$ protocol (corresponding to $$\nuB$$ in the previous text) requires a variant of the above attack method to implement the attack, which will not be elaborated here. This requires a large number of guessing runs and a significant number of signatures, needing at least on the order of 10\^6 signature attempts for the attacker to possibly deduce the attacked party's private key share. More accurately, the number of signatures required to successfully extract the other party's private key share with probability $$\tau\^l$$ is: $$\sum{i=1}\^nf\tau(pi)$$ times.

Where $$f_{\tau} (p) = log(1-\tau) / log(1-1/p\^2)$$. There is a writing error in the corresponding formula in Fireblocks' paper, which has been corrected here.

Note: In the revised version of the GG18 paper, the authors provided many security modification suggestions, so the implementation of this MPC protocol should be based on the revised version.

Real-World Attack Example

The above sections describe the principles of the vulnerability and the algorithmic attack methods. So, in a real-world self-hosted wallet application scenario based on MPC, how should an attack be carried out if the MPC protocol used has this vulnerability?

This vulnerability affects t/n thresholds. For ease of understanding, let’s assume the participants in the MPC Wallet are two parties, Party A and Party B, with a signing threshold of 2/2, where Party A's private key share is held by the user and managed through a mobile app provided by the wallet provider; Party B's private key share is held by the wallet provider and stored and used in the cloud.

To carry out the attack, the attacker must possess the following capabilities:

(1) Understand the logic and mechanisms of the wallet provider in creating wallets and initiating transactions
(2) Be able to simulate the wallet provider's app using the MPC protocol to complete wallet creation and sign transactions

Then the attacker can initiate the attack:

(1) Simulate the app to create a wallet, during which (corresponding to the KeyGen sub-protocol), construct an insecure homomorphic key in the local Party A MPC protocol, then use this homomorphic key to complete wallet creation while obtaining the local Party A private key share $$xA$$ (2) Simulate the app to normally initiate transaction signing 16 times (corresponding to the Sign sub-protocol), and for each time construct malicious $$kA$$ and malicious zero-knowledge proofs in the MPC protocol, completing 16 signatures and collecting the $$\mu$$ from each signature.

After completing the above operations, the attacker can obtain the cloud-based Party B's private key share $$xB$$ corresponding to the created wallet. Since the signing threshold is 2/2, the attacker has obtained the private key share $$xA$$ locally and has also attacked the protocol to obtain the cloud private key share $$xB$$. Thus, the attacker can derive the real wallet private key $$x$$ from $$xA$$ and $$x_B$$.

In the above attack scenario, to attack the wallet, the attack must have been initiated at the time of wallet creation and must have signed multiple times using the wallet to complete the attack, ultimately obtaining the wallet's private key.

Vulnerability Fix

Throughout the entire attack process, we find that all attacks originate from the attack preparation phase, during which the attacker Party A constructed an insecure homomorphic key $$N_A$$ containing many small factors, which facilitated the subsequent attacks.

The vulnerability fix directly addresses this point. In the GG18/GG20 protocol, additional zero-knowledge proofs are added to prevent the appearance of small factors in the homomorphic public key $$N_A$$, fundamentally stopping the attack. After applying this patch, the security assumptions of the entire GG18/GG20 protocol no longer have security issues, and thus the protocol remains secure.

Fixing the vulnerability requires adding two zero-knowledge proofs:

• The first zero-knowledge proof is the Blum modulus proof for Paillier, which ensures that the homomorphic public key $$N_A$$ has at most two prime factors, and each prime factor meets specific characteristics.
• The second zero-knowledge proof is the no small factor proof, which ensures that there are no small prime factors in the homomorphic public key $$N_A$$.

These two zero-knowledge proof implementations can refer to CMP20 and CGGMP21 (Sections 6.3 and C.5), which can guarantee that the Paillier public key $$N$$ does not have factors smaller than $$2\^{256}$$.

Safeheron has already fixed this vulnerability in the open-source algorithm, and the specific fix can be referenced:

https://github.com/Safeheron/multi-party-ecdsa-cpp/pull/7/commits/ee78a86b53f341196623bd65a5ae1ee20bcc2853

https://github.com/Safeheron/multi-party-ecdsa-cpp/pull/10/commits/fbc3474f9b05b1a9e6cfd58647e6ebfc4d4fcbca

Detecting Attacks

After completing the security upgrade of the MPC protocol, for safety reasons, historical data can be checked to verify whether there has been an attack targeting this vulnerability. Since the exploitation of this vulnerability relies on constructing insecure Paillier keys, if such an attack has occurred, there must be small factors present in the attacker's Paillier public key $$N$$. Therefore, we can detect whether there has been an attack by analyzing whether there are small factors in the MPC participants' Paillier public key $$N$$.

The specific detection method can utilize mature large integer factorization algorithm tools to check whether the Paillier modulus $$N$$ has small factors. If small factors exist, there is a possibility of being attacked, and it is recommended to transfer assets as soon as possible and create a new MPC wallet.

Safeheron provides a large integer factorization tool (https://github.com/Safeheron/integer-factorization) that can quickly perform batch detection. For related algorithm principles of large integer factorization, refer to Large Integer Factorization Algorithms and Practices (https://mp.weixin.qq.com/s/5FcA0qGXDKFeb_nMatFeWQ).

Conclusion

After clarifying the principles and attack methods of this vulnerability, it is not difficult to see that the threshold for exploiting this vulnerability is relatively high. However, being in the security industry, facing the unknown and challenging black forest, we must always maintain a sense of reverence for security.

The responsible security disclosure by the Fireblocks team highlights that "security is never a solitary battle." Safeheron also insists on open-source transparency and a technology-driven approach, and we are honored to participate in this security disclosure. Safeheron will subsequently collaborate with security partners SlowMist to assist other vendors in the industry in fixing this vulnerability to ensure the safety of user assets.

Achieving industry security requires the attention and efforts of every vendor, every security practitioner, and every user. We hope to work together with the industry.

References
[1] Fireblocks: Practical Key-Extraction Attacks in Leading MPC Wallets (https://github.com/fireblocks-labs/mpc-ecdsa-attacks-23/blob/main/WhitePaper.pdf)
[2] GG18: Fast Multiparty Threshold ECDSA with Fast Trustless Setup (https://eprint.iacr.org/2019/114.pdf)
[3] GG20: One Round Threshold ECDSA with Identifiable Abort (https://eprint.iacr.org/2020/540.pdf)
[4] CGGMP21: UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts (https://eprint.iacr.org/2021/060.pdf)