Velas researchers are helping to develop state-of-the-art MPC protocols
Alpha-rays attack on the threshold ECDSA
Background
Multi-party computation (MPC) is a class of cryptographic protocols that allow multiple parties to perform computations without trusting a central authority or each other. An important example of an MPC protocol is the threshold ECDSA, which allows for the distribution of ECDSA signatures between different parties.
ECDSA (or elliptic curve digital signature algorithm) is used to sign transactions in many popular blockchains, such as Bitcoin, Ethereum, or BSC. This makes threshold ECDSA a cornerstone technology for blockchain interoperability, as well as for institutions seeking to add a layer of security to their wallets.
Velas researchers are at the epicenter of developing the state-of-the-art threshold ECDSA. We want to share a recent discovery that we made together with Omer Shlomovits, the VP for research at ZenGo. You can also read his blog post or see our paper for technical details.
The uniqueness of our discovery is in the source of bugs we’ve found: they originate not in engineering errors or misuse of cryptographic primitives but in the theory behind the threshold ECDSA protocol. Thus, our findings affected a range of implementations and sparked interest from researchers and engineers alike.
The discovery
While working with ZenGo’s implementation of the cutting-edge GG20paper, we carefully assessed risks and weighted the engineering decisions that were made. One such decision was suggested by GG20’s authors in their previous paper, GG18. One particularly computationally-heavy procedure in their protocol (called “range proofs”) might just be ignored, they argued. They could not prove the security of the protocol without these range proofs, but backed their proposal with some intuitions and ad-hoc computational assumptions.
Later, we found out that several researchers found the absence of range proofs questionable, but could not find a way to attack it. Pressed by the fact that ZenGo’s library followed the recommendations to ignore range proofs, we kept on trying to attack it.
Finally, after several failed attempts, we found an attack! The authors of GG18 missed a crucial oracle that their protocol provided if the range proofs were absent. We quickly assembled a proof-of-concept that demonstrated how the private keys of all parties could be stolen by 1 adversary in 16 signatures (or by 16 adversaries in just 1 signature). We notified ING Bank, and the authors of a different library that was susceptible to our attack.
Most implementations of GG18 and GG20, including the popular Binance’s tss-lib, did not ignore range proofs, and so weren’t at risk. However, we gained valuable insight into the problems that these libraries might face and found a different attack vector. The GG protocols require parties to choose a certain public encryption key, called a “Paillier key.”
We noticed that an adversary choosing a small Paillier key for herself might effectively disable range proofs. And because choosing your encryption key to be small intuitively seems to only harm yourself, the check for Paillier key size was not mentioned in the paper and is missing from most implementations.
However, this approach fell short of the ultimate goal of stealing everyone’s private keys, as the range proofs provided crucial protection. Finally, we realized that the specification of these proofs in the paper contained a simple typo, which, together with the choice of a small Paillier key, leaked the secrets to one adversary in just one signature! A proof-of-concept was assembled to validate our idea. This was becoming serious.
The war room
We mapped the impacted libraries. Most open-source threshold ECDSA libraries were potentially at risk. We started to reach out discreetly to maintainers, starting with Thorchain. They immediately opened a “war room”, a closed group where other maintainers were invited. Steven Goldfeder, one of the coauthors of the GG papers, joined too. Shortly after, Rosario Gennaro, the other G, was updated as well.
Eventually, the war-room contained Anyswap, Binance, Thorchain, Swingby, ZenGo, and Keep, as well as maintainers of non-threatened threshold ECDSA libraries such as Axelar.
The fix is simple: implementations should make range proofs mandatory, check the sizes of other parties’ Paillier keys, and fix the typo that migrated from the paper to libraries.
All the maintainers reacted instantly. PRs, reviews, and merges were done in a matter of days, if not hours. ING and ZenGo needed to enable range proofs, which took more time. ING also had to handle backward compatibility , or dealing with existing users, which made them the last open-source project to get the green light.
The broader ecosystem
We talked to the Fireblocks research team about the vulnerabilities. They worked independently from us and came close to discovering the attack on missing range proofs. As a follow-up, Michael Shaulov, Fireblocks CEO, called for a meeting to discuss details of the attacks and to better understand their scope.
Fireblocks requested to wait on the publication of the paper for one more month. Michael himself was involved in raising awareness among other custody providers. In the following days, we had talks with Shard-X and PayPal/Curv, which, as it turned out, were not affected by the attacks.
One final resource we had was the MPC Alliance network. We announced the vulnerability and were approached by 7 companies.
The authors of other threshold ECDSA constructions took interest in our paper and checked if the vulnerability was present in their protocols. To our knowledge, it was not found in any of them.
The conclusion
The attacks we found were critical, an attacker with access to one party would have been able to empty large pools of funds single-handedly by extracting the private key and signing a transaction with it, sending the funds to an attacker-controlled account.
The discovery was awarded 500k USD. The bug bounty reward is a contribution from several open-source projects, led by Thorchain.
We are grateful for the large bounty. It’s our pleasure to be working on this transformative technology alongside the best experts in the industry.
