Security Analysis of BitForge Vulnerability in GG18/GG20 Protocol

08/14/2023

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 $MtA$ 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 $MTA$ protocols, such as $MtA(k,x)$ and $MtA(k,\gamma)$ protocols, the attacker, based on the insecure homomorphic key, constructs the illegal $k$ ;
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 $x_A$ , $x_B$ and $x_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 $x_B$ . (Using the same method, Party A can also extract Party C's key shard $x_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 \in \{0,1\}^{1024}$ .
Compute:
- $N_A = p * q$
- $\lambda_A = (p-1)*(q-1)$

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

Randomly select primes $(p_1, p_2, ..., p_{16}, q)$ , where each $p_i$ is a distinct small prime, and $q$ is a big prime.
Compute:
- $N_A = \Pi_i{p_i} * q$ where the length of $N_A$ is 2048 bits.
- $\lambda_A = \Pi_i(p_i-1)*(q-1)$

Paillier public key $N_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 $KeyGen$ protocol of GG18/GG20 in the above picture, it only requires a $Square-Free$ zero-knowledge proof. Given that the Paillier homomorphic public key $N_A$ constructed by the attacker only contains distinct prime factors, this construction method evidently can be verified by the $Square-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 $i$ -th execution.

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

$MtA(k_A, \gamma_B) : \alpha_A + \beta_B \leftarrow k_A * \gamma_B$
$MtA(k_A, x_B) : \mu_A + \nu_B \leftarrow k_A * x_B$

The standard calculation is:

Randomly select $k_A \in Zq$ .
Compute $Enc(k_A)$ .
Execute $MtA$ protocol:
- $MtA(k_A, \gamma_B) : \alpha_A + \beta_B \leftarrow k_A * \gamma_B$
- $MtA(k_A, x_B) : \mu_A + \nu_B \leftarrow k_A * x_B$
Generate a zero-knowledge proof concerning the ciphertext $Enc(k_A)$ of the random number $k_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 $k_A$ .
Use this specially-constructed $k_A$ to execute the $MtA$ 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 $k_A$

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

$k_A = N_A / p_i$

Here, this specially-constructed $k_A \gg q^3$ . Under common circumstances, it cannot be verified by the expected zero-knowledge proof. Note, $q$ 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 $MtA$ 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 $k_A \in (-q^3, q^3)$

Please note the above is an illegal statement:

$Enc_{N_A}(k_A)$ is not the ciphertext of $k_A'=0$ .
$k_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 $N_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 = \Gamma^s s^N c^{-e} \pmod {N^2}$

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

As $c = (1+N_A)^k_A * \rho^N_A \mod (N_A^2)$ , $k_A = N_A/p_i$

\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, $c$ "transformed" into the ciphertext of $k_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 $w$ , thus satisfying the condition $e \pmod {p_i} = 0$ . Since the modulus $p_i$ is a small prime, a brute-force iteration can be successful.

Compute the Residue of Party B's Key Shard Modulo $p_i$

The attacker and the victim successfully execute the Sign subprotocol together, additionally recording the $\mu_A$ from the $MtA$ protocol.

$\mu_A = k_A * x_B + \nu_B \pmod {N_A}$

According to the latest $GG18$ , as $u_B \le q^5$ ,

$\mu_A = Dec_{N_A}(Enc_{N_A}(k_A * x_B + v_B))$

\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:

$x_B \pmod {p_i} = (\mu_A - (\mu_A \mod (N_A/p_i)))/(N_A/p_i)$

Record $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 $a_i$ .

So, the result is $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:

$x_B = a_1 \pmod {p_1}$

$x_B = a_2 \pmod {p_2}$

$...$

$x_B = a_{16} \pmod {p_{16}}$

Given that $p_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 $MtA$ protocol constrains $\beta_B < q^5$ (equivalent to $u_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 $MtA$ protocol constrains $\beta_B < N_A$ (equivalent to $u_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 $\tau^l$ , it necessitates $\sum_{i=1}^nf_\tau(p_i)$ signatures.

Please note, $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:

Comprehensive understanding of the wallet provider's mechanism for wallet creation and transaction initiation.
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):

Simulate the mobile App to create a wallet. When creating it (equivalent to $KeyGen$ 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 $x_A$ of Party A.
Simulate the App to initiate transaction signing 16 times (corresponding to the Sign subprotocol). During each signing, the attacker crafts a malicious $k_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 $x_B$ associated with Party B for the created wallet. Given the 2-of-2 signing threshold, the attacker already possesses the key shard $x_A$ and, through the exploitation, has now obtained $x_B$ . Consequently, the attacker can use $x_A$ and $x_B$ to extract the full private key $x$ .

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 $N_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 $N_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 $N_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 $N_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 $N$ does not contain factors smaller than $2^{256}$ .

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

Import no small factor proof into GG18/GG20 by sword03 · Pull Request #7 · Safeheron/multi-party-ecdsa-cppGitHub

nsf proof and paillier blum modulus proof by sword03 · Pull Request #10 · Safeheron/multi-party-ecdsa-cppGitHub

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 $N$ would indicate that a prior attack had occurred. Thus, by checking if there are any small factors within the Paillier public key $N$ 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 $N$ 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.