English
Search
⌃K
Links

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
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=p∗qN_A = p * q
      ​
    • ​
      λA=(p−1)∗(q−1)\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 (p_i) is a distinct small prime, and (q) is a big prime.
  • Compute:
    • ​
      NA=Πipi∗qN_A = \Pi_i{p_i} * q
      where the length of
      NAN_A
      is 2048 bits.
    • ​
      λA=Πi(pi−1)∗(q−1)\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
Square−FreeSquare-Free
zero-knowledge proof. Given that the Paillier homomorphic public key
NAN_A
constructed by the attacker only contains distinct prime factors, this construction method evidently can be verified by the
Square−FreeSquare-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
MtAMtA
protocol as outlined in GG18 section 4.2.
  • ​
    MtA(kA,γB):αA+βB←kA∗γBMtA(k_A, \gamma_B) : \alpha_A + \beta_B \leftarrow k_A * \gamma_B
    ​
  • ​
    MtA(kA,xB):μA+νB←kA∗xBMtA(k_A, x_B) : \mu_A + \nu_B \leftarrow k_A * x_B
    ​
The standard calculation is:
  • Randomly select
    kA∈Zqk_A \in Zq
    .
  • Compute
    Enc(kA)Enc(k_A)
    .
  • Execute
    MtAMtA
    protocol:
    • ​
      MtA(kA,γB):αA+βB←kA∗γBMtA(k_A, \gamma_B) : \alpha_A + \beta_B \leftarrow k_A * \gamma_B
      ​
    • ​
      MtA(kA,xB):μA+νB←kA∗xBMtA(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
kA≫q3k_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
    .
  • ​
    kA≫q3k_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=ΓssNc−e(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)bpi∗NA/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=kA∗xB+νB(modNA)\mu_A = k_A * x_B + \nu_B \pmod {N_A}
​
考虑最新版的
GG18GG18
论文,已知
uB≤q5u_B \le q^5
,
​
μA=DecNA(EncNA(kA∗xB+vB))\mu_A = Dec_{N_A}(Enc_{N_A}(k_A * x_B + v_B))
​
μA−(μAmod  (NA/pi))=DecNA(EncNA(kA∗xB+νB))−(DecNA(EncNA(kA∗xB+νB))mod  (NA/pi))=(xBmod  pi)∗(NA/pi)+νB−νB=(xBmod  pi)∗(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
p1∗p2∗...∗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(1−1/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. 1.
    Comprehensive understanding of the wallet provider's mechanism for wallet creation and transaction initiation.
  2. 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. 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. 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.

References

​