Lindell17 Abort Vulnerability [CVE

This vulnerability allows an attacker to extract a full private key from a wallet implementing Lindell17 2PC protocol, by extracting a single bit in every signature attempt (256 in total). Coinbase WaaS, Zengo and other libraries have been patched.

Fireblocks’ research team found a vulnerability in real-world deployments of the Lindell17 threshold-ECDSA protocol. The vulnerability was found at the interface between the protocol and the wider security infrastructure, and all security products based on Lindell17 are potentially affected. We found multiple wallet-as-a-service providers, retail wallets, and open source libraries that were vulnerable to this attack to varying degrees of exploitability.

The exploit originates from Lindell17 implementations deviating from the specification of the academic paper and ignoring or mishandling aborts in case of failed signatures. Assuming privileged access on the part of the attacker, the vulnerability can be exploited to exfiltrate the key after approximately 200 signature requests. The vulnerability has been proven to be practical and validated on popular open source libraries and some real-world systems.

Practical implementations of the protocol for wallets often encounter a difficult dilemma: either halt operations after a failed signature, which could potentially result in locked funds, or continue with the signing process, thereby risking the exposure of additional key bits with each signature.

The vulnerability was initially discovered in ZenGo wallet and then verified in the Coinbase Wallet as a Service (WaaS) library, with additional wallet providers and libraries impacted. It was also validated with a working POC in a common open source implementation of the protocol (link below). Both Coinbase and ZenGo have mitigated the issue promptly as part of our responsible disclosure process and assured us that they checked and no wallets were exploited.

The vulnerability enables full private key extraction, allowing attackers to steal all funds from the crypto wallet. However, it is an asymmetric vulnerability, meaning the attacker must corrupt a specific party to mount the attack (i.e., the parties are not indistinguishable in terms of the attack).

To elaborate, the Lindell17 protocol is typically employed for wallets that involve a wallet provider and an end user, with the underlying secret key distributed between the two. Additionally, there are two possible configurations for the wallet: either the wallet provider (Service) finalizes the signature, or the end user (Client) does so at the end of the protocol. The party tasked with finalizing the signature is the one at risk, and an attacker can exploit this vulnerability by compromising the counterparty.

Case 1. Server finalizes the signature

In this case, the attacker may exfiltrate the key by compromising the Client and sending malicious messages on its behalf. Specifically, the attacker may initiate two hundred transactions such that, in each signature session, the attacker crafts a different malicious message which will result in a valid signature only if a targeted bit the Server’s secret share is equal to zero.

Thus, depending on whether the Server finalizes the signature or not (the attacker obtains this information either because the signature does or doesn’t appear on the Blockchain, or the Server itself notifies the attacker), the attacker obtains a bit of the Server’s share. It eventually can recover the key in full after 256 signatures.

We should note that the above attack could be expedited if signature requests can be “blitzed” (rapidly initiated one after another), which is typically possible as the server is usually automated and doesn’t significantly limit the number of signatures.

Case 2. Client finalizes the signature

In the second case, by compromising the Server and executing the above attack in reverse, the attacker may extract the key in an analogous way.

It’s worth noting that there may be additional safeguards in place to limit the attack’s exploitability. For example, the signing of transactions might require multi-factor authentication from the user. Consequently, frequent authentication requests could raise suspicion, diminishing the efficiency of a rapid “blitz” attack. However, if the server remains compromised over an extended period, the attacker might opt for a slower-paced attack, reducing its detectability by users that might be willing to do a “retry” and just assume the system is not very stable rather than that they are being attacked.

Note that the above attack can be identified by the server because of the failed signature. Namely, after the data-processing step, the server reconstructs a string that does not verify according to the ECDSA verification algorithm. This event should never happen unless the system is attacked (or it has a serious bug). We recommend tracking these events and distinguishing them from other abort events, e.g. time-outs.

If you are using the protocol as a self implementation or an open source of the protocol you should upgrade to a non vulnerable version or implement your own abort mitigation mechanism that would not allow an attacker to extract additional bits after the first failed transaction.

An alternative approach is to use a ZK proof for the client’s last message.

The Lindell17 protocol employs homomorphic encryption (specifically, Paillier encryption) for generating ECDSA signatures in the client-server model, where each party holds a share of the ECDSA secret key. For the purposes of this presentation, we’ll assume the server finalizes the signature. At its core, the protocol consists of the client computing a partial signature encrypted with the server’s Paillier public key and sending the resultant ciphertext to the server. In turn, the server finalizes the partial signature into a full signature by decrypting the ciphertext and performing some data processing.

When deployed for security-oriented applications, special care must be taken for so-called abort events, i.e. what should the honest server do if it fails to finalize the signature? The paper does not describe an abort-handling mechanism and it explicitly instructs the signatories to terminate signing operations in such an event.

We show that ignoring failed signatures leads to a vulnerable protocol which can be exploited as follows by a corrupted client. Using the notation from the picture, the client calculates C such that C is an encryption of sig* only if the least significant bit (lsb) of x is zero and otherwise C is an encryption of a random number (if the lsb of x is one). Thus, when the server obtains C, the signature-generation process will terminate successfully only if the lsb of x is zero, and this information is inadvertently leaked to the attacker. Then, if signing operations are not terminated, this attack can be iterated to obtain the higher-order bits. By combining with brute-force techniques, the key can be recovered in full after roughly 200 signature attempts.

We recall that (standard) ECDSA signatures are calculated as follows:

1. Sample ephemeral key k

(a random number between 1 and q, where q is an ECDSA constant)

2. Calculate the public nonce r which is a function of k and public parameters

3. Set s = (HASH(msg) + r x ) * k^(-1) % q where msg is the message for signing and x is the ECDSA private key.

4. Output (r,s)

In the Lindell17 protocol, the secret material (i.e. the k and the x) are split between the two parties such that k = k1*k2 and x = x1+x2 and each party holds the relevant secret (say the client holds k1, x1 and the server holds k2, x2)

Furthermore, after the parties calculate r, the client is instructed to send the server the following value encrypted under the the server’s Paillier key (the clients calculates this value by homomorphically operating on Enc(x2)) :

C = Enc(HASH(msg)+r* x1 * (k1^(-1) % q)+ x2 *r * (k1^(-1) % q))

Once the server receives C, it calculates s = k2^(-1)*dec(C) \mod q and outputs (r,s) if it’s a valid signature.

Obtaining the LSB (least significant bit)

To obtain the least significant bit, the client sets k1 = 2 and maliciously sets

C = Enc(HASH(msg) + r* x1 * (k1^(-1) % q)+ x2 * \rho * (k1^(-1) % N))

Where N is the public key of the encryption scheme and \rho = r if r is odd and \rho = r + q otherwise. In the end of the signature process, the validity of the signature leaks the lsb.

Iterating the attack to obtain the next bits

Suppose that the malicious client already knows the i-1 least significant bits (i.e. y = x2 % 2^{i-1}). To obtain the least significant bit, the client sets k1 = 2^i (the ith power of two) and maliciously sets

C = Enc(HASH(msg) + r* x1 * (k1^(-1) % q)+ x2 * \rho * (k1^(-1) % N) + offset))

Where N and \rho are as above and offset = y*rho*((k1^(-1) % q) – (k1^(-1) % N)). In the end of the signature process, the validity of the signature leaks the i-th bit.

We found the vulnerability in a single wallet provider in April 2023.

At the beginning of May 2023 we validated the vulnerability was affecting multiple wallets and libraries and initiated a 90-day responsible disclosure with multiple wallet providers that were found vulnerable.

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

POC: https://github.com/fireblocks-labs/zengo-lindell17-exploit-poc

CVE Link: https://www.cve.org/CVERecord?id=CVE-2023-33242

Academic paper (cryptography of the exploits): https://github.com/fireblocks-labs/mpc-ecdsa-attacks-23