Security Analysis of BitForge Vulnerability in GG18/GG20 Protocol


By Max

I. Background

Recently, the Fireblocks cryptography research team has uncovered BitForge vulnerability in the GG18, GG20, and Lindel 17 protocols. This vulnerability allows attackers to extract the full private key from a set of MPC key shards.

Before this disclosure, the Fireblocks team had connected with Safeheron and engaged in proactive communication. Safeheron's open-source GG18/GG20 MPC protocol was implemented strictly according to the content of their papers, meaning those using this version of the open-source algorithm might be vulnerable to similar attacks. Prior to the vulnerability disclosure, Safeheron had already fixed the issues in the open-source project, with the Fireblocks team assisting in verifying the effectiveness of the patch.

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

In Safeheron's commercial version, we’ve additionally incorporated the zero-knowledge proofs from CMP20/CGGMP21 into GG18 and GG20 protocols, hence they are not affected by this vulnerability.

II. Scope of Vulnerability

This article focuses on the impact of the vulnerability on GG18 and GG20. With respect to the GG18 and GG20 protocols, an attack can be stricken during the MPC signing by crafting the specific Paillier key. With several times of signing, the attacker can extract the key shards of other participants.

The impact of this vulnerability is quite extensive. Since it challenges the security assumptions of the MPC protocol, almost all popular open-source implementations of the GG18 and GG20 protocols are affected by this vulnerability.

III. Vulnerability Mechanism

How does one attack the MPC protocol? Common MPC protocols are provably secure under certain security assumptions. Therefore, attacks on MPC protocols often focus on the security assumptions they rely on. These security assumptions are like the foundation of a skyscraper. If the assumptions fail, the entire MPC protocol will be affected.

Taking GG18/GG20 as an example, these MPC protocols depend on the security of the Paillier homomorphic encryption algorithm which is designed based on the hard computational problems of composite residuosity and is a widely used homomorphic encryption algorithm that supports addition.

This vulnerability specifically targets the construction of the Paillier homomorphic key, incrementally compromising the MtAMtA protocol and related zero-knowledge proof protocols, and then culminating in an effective attack.

The core logic of the entire attack is as follows:

(1)In the KeyGen Subprotocol phase, the attacker constructs an insecure homomorphic key.

(2)During the Sign Subprotocol phase:

  • In the pairwise-run MTAMTA protocols, such as MtA(k,x)MtA(k,x) and MtA(k,γ)MtA(k,\gamma) protocols, the attacker, based on the insecure homomorphic key, constructs the illegal kk;

  • Using the properties of the insecure homomorphic key, the attacker constructs malicious zero-knowledge proofs, deceiving other participants to get verified;

  • The attacker completes the signature with the attacked participant and records the μ\mu in the process according to the MPC protocol.

(3)After iterating the Sign subprotocol multiple times, the attacker calculates the other participant's key shard using the Chinese Remainder Theorem.

IV. Attack Method

In this chapter, we delve into the details of the attack. In a common MPC threshold signature scheme, there are multiple participants who can attack each other using identical attack methods.

To better explain the methods behind it, let's assume an MPC wallet is co-created and co-managed by three parties: Party A, Party B, and Party C. Each party manages their respective key shards xAx_A, xBx_B and xCx_C. By exploiting this vulnerability, Party A can attack Party B and Party C to obtain their key shards.

In this section, taking Party A attempts to attack Party B as an example, we will illustrate how to extract Party B's key shard xBx_B. (Using the same method, Party A can also extract Party C's key shard xCx_C.)

4.1 Preparation Phase: Construct an Insecure Homomorphic Key

The first attack occurs during the execution of the KeyGen subprotocol, which can be termed the "attack preparation phase". During this phase, the attacker, Party A, successfully constructs an insecure Paillier homomorphic key.

The standard process for constructing a homomorphic key is:

  • Randomly select secure primes p,q{0,1}1024p, q \in \{0,1\}^{1024}.

  • Compute:

    • NA=pqN_A = p * q

    • λA=(p1)(q1)\lambda_A = (p-1)*(q-1)

The process used by Party A (attacker) to construct the homomorphic key is:

  • Randomly select primes (p1,p2,...,p16,q)(p_1, p_2, ..., p_{16}, q), where each pip_i is a distinct small prime, and qq is a big prime.

  • Compute:

    • NA=ΠipiqN_A = \Pi_i{p_i} * q where the length of NAN_A is 2048 bits.

    • λA=Πi(pi1)(q1)\lambda_A = \Pi_i(p_i-1)*(q-1)

Paillier public key NAN_A constructed by Party A contains a significant number of small factors. Then, can Party A's illegal Paillier key deceive Party B? Especially since a zero-knowledge proof needs to be constructed for Party B to verify.

From the KeyGenKeyGen protocol of GG18/GG20 in the above picture, it only requires a SquareFreeSquare-Free zero-knowledge proof. Given that the Paillier homomorphic public keyNAN_A constructed by the attacker only contains distinct prime factors, this construction method evidently can be verified by the SquareFreeSquare-Free zero-knowledge proof.

4.2 Attack Phase: Sign Subprotocol

The attack needs to execute the Sign subprotocol 16 times. Let's assume we're discussing the ii-th execution.

In the Sign subprotocol, the initial rounds will execute the MtAMtA protocol as outlined in GG18 section 4.2.

  • MtA(kA,γB):αA+βBkAγBMtA(k_A, \gamma_B) : \alpha_A + \beta_B \leftarrow k_A * \gamma_B

  • MtA(kA,xB):μA+νBkAxBMtA(k_A, x_B) : \mu_A + \nu_B \leftarrow k_A * x_B

The standard calculation is:

  • Randomly select kAZqk_A \in Zq.

  • Compute Enc(kA)Enc(k_A).

  • Execute MtAMtA protocol:

    • MtA(kA,γB):αA+βBkAγBMtA(k_A, \gamma_B) : \alpha_A + \beta_B \leftarrow k_A * \gamma_B

    • MtA(kA,xB):μA+νBkAxBMtA(k_A, x_B) : \mu_A + \nu_B \leftarrow k_A * x_B

  • Generate a zero-knowledge proof concerning the ciphertext Enc(kA)Enc(k_A) of the random number kAk_A. Refer to section A.1 - Range Proof in GG18.

  • Execute the MPC Sign subprotocol as usual.

The attacker's computation process is:

  • Construct a special kAk_A.

  • Use this specially-constructed kAk_A to execute the MtAMtA protocol.

  • Create a malicious zero-knowledge proof to deceive the other party.

  • Execute the MPC Sign subprotocol as usual.

Here are its specific operations:

Construct a Special kAk_A

The attacker does not use random values. Instead, during the (i^{th}) execution of MPC Sign subprotocol, the attacker constructs a kAk_A by:

kA=NA/pik_A = N_A / p_i

Here, this specially-constructed kAq3k_A \gg q^3. Under common circumstances, it cannot be verified by the expected zero-knowledge proof. Note, qq is the order of the elliptic curve.

Craft a Zero-Knowledge Proof

The GG18 protocol requires the attacker to provide a valid zero-knowledge proof during the execution of MtAMtA protocol, referring to section A.1 - Range Proof in GG18. This proof must verify:

  • Witness:$k_A' = 0 \ne k_A$, other random numbers.

  • Statement: The ciphertext of $Enc_{N_A}(k_A)$ for $k_A'$ which satisfy kA(q3,q3)k_A \in (-q^3, q^3)

Please note the above is an illegal statement:

  • EncNA(kA)Enc_{N_A}(k_A) is not the ciphertext of kA=0k_A'=0.

  • kAq3k_A \gg q^3

Normally, the range proof of the GG18 protocol here is fully valid, making it difficult for the attacker to construct a zero-knowledge proof that allows the statement to get verified.

So, if Party A (attacker) want to successfully exploit the vulnerability, the attacker needs to use the insecure Paillier key NAN_A constructed by Party A during the KeyGen subprotocol phase. It is the presence of this insecure Paillier key that provides the opportunity to craft malicious a zero-knowledge proof.

According to the description of zero-knowledge proof in GG18 and GG20 protocols:

In the Verifier's verification process, the most crucial aspect is ensuring the satisfaction of the equation for ciphertext constraints (highlighted in the red box):

u=ΓssNce(modN2)u = \Gamma^s s^N c^{-e} \pmod {N^2}

The attack technique is to craft a plausible challenge value e=Hash(...,w,)e = Hash(..., w, ) that satisfies the condition e(modpi)=0e \pmod {p_i} = 0.

As c=(1+NA)AkρANmod(NA2)c = (1+N_A)^k_A * \rho^N_A \mod (N_A^2), kA=NA/pik_A = N_A/p_i

ce=((1+NA)AkρAN)emod(NA2)=(1+NA)ekAρeNAmod(NA2)=(1+NA)bpiNA/piρeNAmod(NA2)=ρeANmod(NA2)=EncNA(0)emod(NA2)\begin{align*} c^e &= ((1+N_A)^k_A * \rho^N_A)^e &\mod (N_A^2) \\ &= (1+N_A)^{ek_A} * \rho^{eN_A} &\mod (N_A^2) \\ &= (1+N_A)^{bp_i * N_A/p_i} * \rho^{eN_A} &\mod (N_A^2) \\ &= \rho^{e_AN} &\mod (N_A^2) \\ &= Enc_{N_A}(0)^e &\mod (N_A^2) \\ \end{align*}

Here, cc "transformed" into the ciphertext of kA=0k_A'=0, thereby successfully constructing the zero-knowledge proof.

Please note that here, it is possible to iteratively brute-force γ\gamma during the construction process by continuously incrementing it by 1 and updating ww, thus satisfying the condition e(modpi)=0e \pmod {p_i} = 0. Since the modulus pip_i is a small prime, a brute-force iteration can be successful.

Compute the Residue of Party B's Key Shard Modulo pip_i

The attacker and the victim successfully execute the Sign subprotocol together, additionally recording the μA\mu_A from the MtAMtA protocol.

μA=kAxB+νB(modNA)\mu_A = k_A * x_B + \nu_B \pmod {N_A}

According to the latest GG18GG18, as uBq5u_B \le q^5,

μA=DecNA(EncNA(kAxB+vB))\mu_A = Dec_{N_A}(Enc_{N_A}(k_A * x_B + v_B))

μA(μAmod(NA/pi))=DecNA(EncNA(kAxB+νB))(DecNA(EncNA(kAxB+νB))mod(NA/pi))=(xBmodpi)(NA/pi)+νBνB=(xBmodpi)(NA/pi)\begin{align*} \mu_A - (\mu_A \mod (N_A/p_i)) =& Dec_{N_A}(Enc_{N_A}(k_A * x_B + \nu_B)) - (Dec_{N_A}(Enc_{N_A}(k_A * x_B + \nu_B)) \mod (N_A/p_i))\\ =& (x_B \mod p_i) * (N_A/p_i) + \nu_B - \nu_B \\ =& (x_B \mod p_i) * (N_A/p_i) \end{align*}

As known:

xB(modpi)=(μA(μAmod(NA/pi)))/(NA/pi)x_B \pmod {p_i} = (\mu_A - (\mu_A \mod (N_A/p_i)))/(N_A/p_i)

Record ai=(μA(μAmod(NA/pi)))/(NA/pi)a_i = (\mu_A - (\mu_A \mod (N_A/p_i)))/(N_A/p_i)

Notably, all on the right of the equation are parameters known to the attacker; hence, the attacker can compute aia_i.

So, the result is xB=ai(modpi)x_B = a_i \pmod {p_i}.

4.3 Final Phase: Compute the Victim's Key Shard

Upon successfully executing the MPC Sign subprotocol 16 times, the attacker will obtain:

xB=a1(modp1)x_B = a_1 \pmod {p_1}

xB=a2(modp2)x_B = a_2 \pmod {p_2}


xB=a16(modp16)x_B = a_{16} \pmod {p_{16}}

Given that p1p2...p16>qp_1 * p_2 *... * p_{16} > q, and according to the Chinese Remainder Theorem (CRT), Party A can effectively compute Party B's key shard, thus, completing the attack.

4.4 Attack Implications

The ramifications of the attack depend on the specific implementation version of the GG18 paper. Let's analyze based on the different versions:

  • In the revised version of GG18, the MtAMtA protocol constrains βB<q5\beta_B < q^5 (equivalent to uBu_B as mentioned previously). By using the attack method described above, an attacker would only need 16 signatures to successfully decipher the key shard of the victim.

  • In the original version of GG18, the MtAMtA protocol constrains βB<NA\beta_B < N_A (equivalent to uBu_B as mentioned previously). To mount an attack against this version, a slightly-altered method is required (not further elaborated herein) which would require a substantial amount of trial operations and signing, at least 10^6 attempts, to potentially extract the target's key shard. To be precise, with a success probability of τl\tau^l, it necessitates i=1nfτ(pi)\sum_{i=1}^nf_\tau(p_i) signatures.

Please note, fτ(p)=log(1τ)/log(11/p2)f_{\tau} (p) = log(1-\tau) / log(1-1/p^2). (There was a typo in this formula in the Fireblocks paper; the correct formula is presented here.)

The revised paper of GG18 offers numerous security enhancement recommendations, thus it is advisable to implement this MPC protocol based on the revised version.

V. Example Attack in Self-Custodial MPC Wallet

While the previous sections elaborated on the vulnerability’s theoretical underpinnings and algorithmic exploit method, how it plays out in a self-custodial MPC wallet? If the MPC protocol employed contains this vulnerability, how an attack exploit it?

The vulnerability impacts a t-of-n threshold, let’s take a simple example, 2 parties manage an MPC wallet, Party A and Party B. The signing threshold for this wallet is 2-of-2. The key shard for Party A is held by the user and is managed via a mobile App provided by the wallet service. Meanwhile, Party B's key shard is stored and utilized in the cloud by the wallet provider.

For a successful attack, the attacker would need:

  1. Comprehensive understanding of the wallet provider's mechanism for wallet creation and transaction initiation.

  2. The capability to simulate the provider's App to execute the MPC protocol for wallet creation and transaction signing.

Attack Execution (with the above capabilities):

  1. Simulate the mobile App to create a wallet. When creating it (equivalent to KeyGenKeyGen subprotocol), crafts an insecure homomorphic key of the local Party A MPC protocol. Using this key, the attacker completes the wallet setup and consequently obtains the local key shard xAx_A of Party A.

  2. Simulate the App to initiate transaction signing 16 times (corresponding to the Sign subprotocol). During each signing, the attacker crafts a malicious kAk_A and its corresponding malicious zero-knowledge proof for the MPC protocol. The attacker will then successfully execute the signing process 16 times, gathering the μ\mu value each time.

Upon executing the above steps, the attacker can acquire the cloud-stored key shard xBx_B associated with Party B for the created wallet. Given the 2-of-2 signing threshold, the attacker already possesses the key shard xAx_A and, through the exploitation, has now obtained xBx_B. Consequently, the attacker can use xAx_A and xBx_B to extract the full private key xx.

In the described scenario, an attacker must initiate their attack right at the wallet creation phase. Subsequently, by conducting multiple signings using the wallet, the attacker can finally extract its private key.

VI. Vulnerability Remediation

Upon analyzing the entire attack, it becomes evident that the crux of the vulnerability stems from the preparation phase. In this stage, the malicious Party A crafts an insecure homomorphic key NAN_A, which comprises a significant number of small prime factors. These factors play a pivotal role in enabling the subsequent attack.

The remedial approach is to nip the issue in the bud. In the GG18 and GG20 protocols, additional zero-knowledge proofs are introduced to deter the presence of small factors in the homomorphic public key NAN_A, thereby thwarting the attack from the root. When the patch for this vulnerability is applied, the security assumptions underpinning the GG18 and GG20 protocols are intact, ensuring the protocol's security.

Add two zero-knowledge proofs to fix:

  • Blum Modulus Proof for Paillier: Ensure that the homomorphic public key NAN_A consists of at most two prime factors that adhere to specific characteristics.

  • No Small Prime Factors Proof: Ensure that there are no small prime factors in the homomorphic public key NAN_A.

For implementations of these zero-knowledge proofs, you can refer to CMP20 and CGGMP21 (specifically sections 6.3 and C.5). These proofs guarantee that the Paillier public key NN does not contain factors smaller than 22562^{256}.

Safeheron has already patched this vulnerability in our open-source algorithm. For details, you can refer to:

VII. Attack Detection

After upgrading the security of the MPC protocol, we also suggest analyzing historical data to determine if there has been any exploitation of the said vulnerability. Given that the exploit hinges on creating an insecure Paillier key, the presence of small factors within the attacker's Paillier public key NN would indicate that a prior attack had occurred. Thus, by checking if there are any small factors within the Paillier public key NN of the MPC participants, you can infer potential past attacks.

A robust method to detect this is by utilizing an established integer factorization algorithm tool to check if the Paillier modulus NN has any small factors. If any small factors are detected, it points towards a probable attack. In such cases, it's recommended to promptly transfer assets and set up a new MPC wallet.

Safeheron offers an integer factorization tool, which facilitates swift batch testing. And, for the algorithm of integer factorization, please refer to Large Integer Factorization Algorithm and Its Practice.

VIII. Conclusion

Having delved deep into the intricacies of this vulnerability and its exploitation method, it's evident that exploiting this loophole requires a significant level of expertise. Nonetheless, in the security industry, as we traverse the challenging dark forest filled with unknowns, we must always maintain profound respect for security.

The responsible disclosure by the Fireblocks team epitomizes that "security is never a solo endeavor." At Safeheron, we're deeply committed to the principles of open-source, transparency, and prioritizing solid technical expertise. It's indeed an honor for us to be part of this disclosure process. In the future, Safeheron will aid other industry players in patching this vulnerability with our security partner SlowMist, ensuring the safety of user assets.

Achieving industry-wide security necessitates the dedication and efforts of every tech provider, every security professional, and every user.


[1] Fireblocks: Practical Key-Extraction Attacks in Leading MPC Wallets

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

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

[4] CGGMP21: UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts

Last updated