# "Alpha-Rays" behind the scenes

In a recently published [paper](https://eprint.iacr.org/2021/1621), we describe two attacks on threshold ECDSA implementations. The uniqueness of the attacks is that they are rooted in issues found in the protocol itself. We hereby describe the events that surrounded the discovery, handling, and patching of the impacted code.

## Intro
**March 1, 2018**. Ariel Gabizon, a cryptographer employed by the Zcash Company at the time, [discovered](https://fortune.com/2019/02/05/zcash-vulnerability-cryptocurrency/) a subtle cryptographic flaw in the BCTV14 paper that describes the zk-SNARK construction used in the original launch of Zcash. This vulnerability is so subtle that it evaded years of analysis by expert cryptographers focused on zero-knowledge proving systems and zk-SNARK. The vulnerability could have allowed for infinite counterfeiting.

**October 1, 2021**. [GG18](https://eprint.iacr.org/2019/114.pdf), a paper published in CCS 2018, described a protocol for t out of n threshold ECDSA. This protocol, together with a follow-up work by the same authors, GG20, became a popular choice for implementation by many custody operators and protocols, securing equivalent of billions worth of USD. Moreover, cited more than 100 times and considered the first practical multiparty ECDSA protocol, GG18 is a cornerstone in the evolution of threshold ECDSA protocols. As a result, the paper has gone through intensive peer review and multiple independent audits, receiving the attention that only a select few papers, that ever crossed from academy to industry, get. While implementation bugs, some critical, had been [found in the wild](https://www.youtube.com/watch?v=0Okqvm4lBQI), GG18 construction remained flawless.

Until now.

## What we have found
Read the paper for a complete description. In short, our attacks allow an attacker, controlling a single party to extract the full private key. To pull off the attack, the attacker must participate in a small number of signatures. In some cases, one signature is enough.

Our attacks target the multiplicative to additive (MtA) subprotocol. There are two variants of it in the paper. The _fast_ option is done without range proofs, while the _full_ version includes range proofs.
We attack the first variant by using an oracle access not accounted for in the paper (in fact it was conjectured in the paper that such oracle does not exist).
We attack the _full_ version with range proofs by taking advantage of a missing Paillier size check and a mistake, probably a typo, in the bounds of one of the ZK proofs used.

I know this is vague. READ THE PAPER.

## How the attacks were discovered
The _fast_ version of the MtA has for a long time been considered risky. Without a good basis of course, but it always felt this way intuitively. The argument presented in the paper: if you sign only once an attacker can extract only one bit, is hard to swallow. While working on the ZenGo GG20 implementation for the _fast_ version as part of his work at Velas, Dmytro simply could not accept the one-bit-leakage-is-secure concept. At first, he spent some time exploring if the classical single key ECDSA extraction attacks from nonce leakage, apply in the multiparty case using the leakage in the MtA. To share credit - Fireblocks research team was looking at the same problem during the same time, achieving partial success. Eventually, we gave up.
I was the one making the engineering choice of going with the _fast_ variant for ZenGo library. I will admit to having tried and failed to find a flaw with this choice. That said, all other open-source implementations, except for ING which provided both variants, avoided the _fast_ variant and implemented the full variant with the range proofs.
Dmytro made up his mind to work on this for one more day, to be fully convinced there is no even theoretical way to extract the key. And there it was: the new oracle. No Lattices needed. It turns out that for the _fast_ variant, an extra equation is required to be verified. This equation contains a random element coming from the attacker and a secret fixed element (partial key) coming from the victim. Few consecutive signatures with different random elements are enough to efficiently recover the victim's key.

What about the _full_ variant? No oracle there for sure plus extra zero knowledge proofs. At first, we attempted to find another oracle with similar power that is enabled by the introduction of the ZK proofs. We showed that as their name suggests, ZK gives you zero knowledge :)
But then, Dmytro noticed that some uniformly sampled elements' bounds in the proof are simply wrong, basically eliminating most of the hiding we are guaranteed. ZK is no longer zero knowledge! Can we take advantage of this? Well, only if we can choose the size of the Paillier key. Common sense says that a party that uses a small key only harms itself. That is true until we use the Paillier cryptosystem in a ZK proof. We noticed that a check on Paillier size is missing from the paper and almost ALL implementations. Bounds were obviously taken _as is_ from the paper. There you have it. One signature and the attacker learns partial key from all co-signers leading to full extraction of the key.

## The War Room
We mapped impacted libraries. Almost all open-source threshold ECDSA libraries were potentially at risk. We started to reach out discreetly to maintainers. My first call was to Thorchain, they are good friends and have the highest level of security-operations discipline. They immediately opened a "war room": a closed group where we could invite other maintainers and coordinate fixing the issues. Steven Goldfeder, one of the G's in GG was invited too. Not long after, Rosario Gennaro, the other G, was updated as well. Our communication with the authors was done via email and its purpose was mostly to confirm our observation about how to fix the typos in the ZK bounds. The attacks themselves were demonstrated in a proof of concept manner.
The war-room was handled professionally: we had Anyswap, Binance, Thorchain, Swingby, ZenGo, Keep who were all impacted. In addition, we had maintainers of non-threatened threshold ECDSA libraries such as Axelar and finally, we let in some trustworthy individuals to help (thank you Zaki!). We communicated with ING Bank via email and updated the group on their progress.

The fix sounds simple: If you use the _fast_ variant - stop doing that and move to the _full_ variant. If you use the _full_ variant: check the size of the Paillier key and fix the bounds.
The response time of all maintainers was blazing fast. PRs, reviews, and merges were done in a matter of days if not hours. For ING and ZenGo that needed to remove the _fast_ variant - the fix took more time but was done quickly nonetheless. ING had to handle backward compatibility - dealing with existing users, which made them the last open-source project to give the green light.

## The broader eco-system (closed source)
We talked to Fireblocks research team to give an update on the vulnerability. As mentioned before, they were very close to discovering the _fast_ variant bug. As a follow-up, Michael Shaulov, Fireblocks CEO, called for a meeting to discuss details of the attacks and to better understand their scope. The request from Fireblocks was to wait with the publication of the technical paper for one more month. Michael himself was involved in raising awareness with other custody providers: In the days after our call with Fireblocks, we had talks with Shard-X and PayPal/Curv, both not affected as far as we know, as they do not implement GG.
One final resource we had was the [MPC Alliance](https://www.mpcalliance.org) network. We announced the vulnerability and were approached by 7 companies. 
We shared the report only with companies that were using one of the open-source libraries to make sure they updated the code. We also shared the details with companies that implemented threshold ECDSA from scratch.

## Bug Bounty
The attacks we found were critical - an attacker with access to one signer would have been able to empty large pools of funds single-handedly by extracting the full private key and signing a transaction sending the funds to an attacker-controlled account.
The discovery was awarded 500kUSD. The bug bounty reward is a contribution of several of the open-source projects, led by Thorchain.
We are grateful for the large bounty and proud to be working with teams of pros that hold the highest level of responsibility towards their users.

## Edits (post publication)
* Rosario Gennaro wrote a [twitter thread](https://twitter.com/rgennaro67/status/1471147996226150401?s=20) about the security of GG18 and the attacks
* Coinbase new cryptographic library, using GG20, was [patched](https://github.com/coinbase/kryptology/pull/16) against the attack