# "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. ![](https://i.imgur.com/fp6RSUy.png) 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. ![](https://i.imgur.com/3CJZa2Z.png) 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
Last changed by  
 
Omer Shlomovits
7052

Read more

Hardware-friendliness of HyperPlonk

In this note we provide the hardware perspective on HyperPlonk. We focus on the main building block, the Multivariate SumCheck protocol and compare its computational and memory complexity to that of an NTT (Number Theoretic Transform). Background - HyperPlonk Plonk is one of the most widely adopted SNARKs in the industry. In vanilla Plonk after arithmetization, the resulting execution trace is interpolated into univariate polynomials and thus the resulting protocol relies heavily on NTTs. HyperPlonk is a new adaptation of Plonk, where the execution trace is interpolated on a boolean hypercube. Thus the polynomial representation of the trace is a multivariate polynomial with linear degree in each variable. This is known as an MLE (MultiLinear Extension). A good overview of Hyperplonk can be found in Benedikt Bunz ZKSummit8 talk. One key advantage of HyperPlonk is the elimination of large NTTs, a major computational bottleneck in Plonk over large-circuits. By moving to the boolean hypercube, we no longer need univariate polynomials. Instead, HyperPlonk relies on multivariate polynomial arithemetic. Section 3 in the Hyperplonk paper is devoted to developing the toolbox for working with multivariate polynomials. The figure below, taken from the paper, shows how HyperPlonk is built out of this toolbox. As can be seen, at the root of it all we have the classical SumCheck protocol, which is bound to become the main computational problem in HyperPlonk (polynomial commitments aside), replacing NTTs all together. Sumcheck in HyperPlonk A toy example Consider an execution trace unrolled in the form of a vector. We illustrate the general idea using a vector of length $8$, constituted of the polynomial evaluations $\left{ f_{i}\right} _{i=0}^{7}$, where $f_i\in \mathbb{F}$. We interpolate these values using a multivariate polynomial $F(X_3,X_2,X_1)$ as follows

12/28/2022
Identity is the Key

or: what I learned from working on decentralized identity and some future research directions Intro I have worked in ZenGo, a crypto wallet company, for several years. My role was to explore and expand the boundaries of key management for wallets, that is, the custody, safe usage, and applications of permissionless, ledger-based, crypto-currencies. Recently, I started looking at the design principles of a somewhat related kind of system for self-sovereign identity, or as I will refer to it in this blog - decentralized identity (DID). My initial instinct was to apply the familiar frameworks of crypto wallets, yet quickly I realized that there is much more to DID systems: despite similarities at the key management level, there are in addition many unique features to DID. In this write-up, I will try to account for my humble journey going from a crypto wallet to a DID system, while uncovering some new, at least for me, research questions in DID. The Rabbit Hole In September 2021 I was supposed to present my work on DID recovery using a timestamping service in the Future of Personal Identification workshop (FoPI). The paper was accepted after shepherding and later I withdrew it. Why?

12/23/2021
FS-DKR: One Round Distributed Key Rotation

Intro In this note we aim to re-purpose the Fouque-Stern Distributed Key Generation (DKG) to support a secure Distributed Key Refresh (DKR). As we claim, FS-DKR is well suited for rotation of threshold ECDSA keys. Background The FS-DKG protocol is a one round DKG based on Publicly Verifiable Secret Sharing (PVSS) and the Paillier cryptosystem. There are two major security shortcomings to FS-DKG: It introduces a factoring assumptions (DCRA) it is insecure against rushing adversary Rushing adversary is a common assumption in Multiparty Computation (MPC). In FS-DKG, an adversary waiting to receive messages from all other parties will be able to decide on the final public key. In the worst case it can lead to a rouge-key attack, giving full control of the secret key to the attacker. This is the main reason, in our opinion, why FS-DKG, altough with prominent features, was over-looked for the past 20 years.

8/29/2021
Read more from Omer Shlomovits
Published on HackMD