August 9, 2023

GG18 and GG20 Paillier Key Vulnerability [CVE-2023-33241]: Technical Report

Daniel Evans

Marketing

9 min. read

This newfound vulnerability allows an attacker to extract a full private key from any wallet using the GG18 and GG20 protocols. More than 10 wallets and libraries have been found vulnerable, including Binance custody.

Executive Summary

Fireblocks’ research team has discovered a vulnerability in the specification of two popular multi-party computation (MPC) protocols: GG18 and GG20. These protocols are considered pioneering for the MPC wallet industry and have been widely adopted by companies in the space. The vulnerability was found at the pseudocode level, and all vendors implementing the protocol should be considered vulnerable. The vulnerability can be exploited to exfiltrate the key.

The vulnerability originates with parties not checking to see if the attacker’s Paillier modulus, denoted N, has small factors or that it is a biprime. If exploited, the vulnerability allows a threat actor interacting with the signatories in the MPC protocol to steal their secret shards and ultimately obtain the master secret key. The severity of the vulnerability depends on the implementation parameters, so different parameter choices give rise to different attacks with varying degrees of effort/resources required to extract the full key. Some implementations are vulnerable to key extraction in 16 signatures, while others could require as many as 1 billion signatures.

The exploit was validated on major open source implementations and a working POC was built on one of the open libraries.

We ran a responsible disclosure process with more than 10 wallet providers, blockchains and libraries in parallel and actively looked for impacted products, but given the popularity of the protocols we assume additional products might be impacted.

Vulnerability Risk Profile

The vulnerability is a full private key extraction vulnerability allowing the attacker to steal all funds that are kept in the crypto wallet. The main source of the vulnerability is that the signatories’ Paillier public keys are not checked for small prime factors, where a prime of size, sayß, 2**20 is considered small.

Since the severity of the vulnerability depends on the implementation parameters, different parameter choices give rise to different attacks with varying degrees of effort/resources required to extract the full key. Namely, the distinguishing parameter choices are as follows:

1. Beta Parameter in MTA ~ q^5 (where q is the size of the elliptic curve)

2. Beta Parameter in MTA ~ N (where N is the Paillier public key of the compromised party

a. N is not checked for small factors at all (not even 3,5,7,..)
b. N is checked manually for smallish factors (< 2**12)

Case 1. By using maliciously-crafted messages, the attacker obtains leakage of the private key shards of the parties by interacting with the signatories in the first round of the MPC protocol. To obtain the full private key, it is sufficient to iterate the attack sixteen times.

A specific sub-scenario of Case1 was identified in the Apache Milagro library which had an extremely low beta parameter (256 bits) allowing an attacker to extract the key without crafting any malicious messages and simply recovering the key from the transcript of the signature ceremony.

Case 2. In this case, the attacker actively controls one of the signatories (so it also needs to “know” the corresponding secret shard) and interacts with the signatories for the entire MPC protocol. By using maliciously-crafted messages, the attacker obtains leakage of the private key shards whenever the signature generation process terminates successfully. The total number of signature-generation attempts depends on the number of parties and the malicious Paillier modulus N. For two parties, the number of (failed) signatures ranges from 200K (for case 2.a) to 1B (for case 2.b).

Recommended mitigation for clients

Since GG18/20 is a widely used MPC protocol and the vulnerability affects all users of the protocol it’s important to understand what parameters are being used and act accordingly. If you are using an open source library please make sure that it was upgraded. Some of the commonly used libraries for GG18/20 are no longer actively maintained and using them can be risky.

To fix the issue, we recommend using a key-generation process that can detect maliciously formed Paillier modulus using a suitable ZK proof.

A short introduction to MPC and GG 18/20 protocol

Multi-party computation (MPC)offers an innovative way for several parties to collaboratively generate a shared public key and jointly sign transactions, thereby eliminating the risk of a single point of failure. Specifically, within a MPC-enabled wallet, an attacker must breach a sufficient number of parties possessing a key share. This contrasts with the traditional non-threshold paradigm, where compromising a single party suffices to gain control of the wallet.

The Elliptic Curve Digital Signature Algorithm (ECDSA) is the preferred signature scheme within the blockchain space. Even though ECDSA is a traditional non-threshold signature scheme, it can be transformed into a threshold variant through MPC.

GG18, along with the follow-up GG20, are among the most widely-used MPC protocols for threshold-ECDS. Both protocols make extensive use of advanced cryptographic techniques like homomorphic (Paillier) encryption and zero-knowledge proofs. At a high level, the parties in the protocol perform calculations and exchange messages in a predetermined way, and the protocol uses zero-knowledge proofs to validate that no party deviates from the protocol instructions.

Technical Attack Description

The attack differs depending on the beta parameter, so in this section we will be talking about two separate attacks.

Our first attack (case 1) exfiltrates the key in 16-bit chunks at a time and 16 signatures suffice to recover the key in full, regardless of the number of parties.

Our second attack (case 2) exfiltrates the key also 16 bits at a time but the success probability of the attacker (i.e. the probability that the attack will result in leakage) is somewhat small, and thus the attack needs to be iterated many times (as many as 1B in certain cases) in order to recover the key in full. Furthermore, our second attack deteriorates with the number of parties, so recovering the key in full when a single party is compromised against two honest parties is twice as expensive, in terms of the number of required signatures to extract the key, compared to a single honest party.

Both of our attacks target the so-called Multiplication-to-Addition phase which proceeds as follows (this phase of the protocol is executed between each pair of parties; for simplicity we only assume two parties, A and B).

1. A sends Enc(k) to B encrypted under A’s own Paillier pk N, where k is a random value.

A also sends a zero-knowledge proof (ZKP) that k is not-too-big a value

2. B sends Enc(k*x + \beta) to A by homomorphically evaluating the above, where \beta is a random value and x is B’s ECDSA private share.

B also sends a ZKP that calculates the above correctly.

3. A outputs \alpha = k*x + \beta % N by decrypting the above and B outputs \beta

Prep for both attacks. Party is malicious in both attacks and A picks a Paillier modulus composed of 16 small primes p1, … p16 of bit-length 16, and a single big prime q (to match the expected length of N). A sets N = p1p2…p16*q

Then, for both attacks,

1. A will choose a malicious k = N/pi (this choice is malicious because k is almost as big as N which the ZKP is supposed to detect)

The value of k is updated after each successful attack (k= N/p1, N/p2, N/p3…)

2. A cheats in the ZKP to pass the malicious k as benign.

We omit the details of the above which can be found in the technical research paper.

Case 1.

As soon as A obtains \alpha, it deduces x % pi = (\alpha – [\alpha % N/pi])/ (N/pi)

After 16 signature attempts in total, A recovers the x’s in full from all parties using Chinese Remainder Theorem (CRT).

Case 2.

The previous leakage is no longer relevant because the value of \alpha is implicitly reduced modulo N on B’s side, and, because beta is as big as N, \alpha perfectly hides x. To obtain leakage on x, compromised party A does the following: it guesses that x \mod pi = y (at random) and reassigns \alpha = \alpha – y * N/pi % N, and proceeds as the protocol prescribes until the end.

If the signature is valid at the end of the execution, then the guess was correct and A proceeds to the next attack. If the signature is invalid there is no leakage (it may be that x \mod pi = y and yet the signature is invalid because of other random choices in the attack).

After 16 successful leakages for each of the honest parties, A recovers the secret in full using the Chinese remainder theorem.

On the expected number of signatures to extract the key. We note that there is a tradeoff between the number of signatures, the number of honest, non-compromised, parties, and the size of the primes. For instance, in the presence of a single non-compromised party, when choosing the smallest possible primes {3,5,..,} our attack extracts the key with probability 2**(-40) after 200K signatures, or with probability 0.5 after approx 1M signatures.

For bigger primes, e.g. choosing p1, p2, … t be roughly 2**12, our attack extracts the key with probability 0.15 after 2B signatures (cf. research document).

Responsible Disclosure

We found and validated the vulnerability by May 5th, 2023 and started identifying affected parties. Thus initiating a multi company 90-day responsible disclosure process with more than 10 vendors and library publishers.

On August 9th, 2023 we published our findings publicly and attached a CVE for this issue: CVE-2023-33241.