Counter-Strike: Threshold Attack
Potential attack on threshold ECDSA prevented, counter-terrorists win!
The code discussed in this note is a work in progress at the time of writing and has not been audited yet. Please always take care when using unaudited code.
Threshold wallets leverage threshold signature schemes (TSS) to distribute signing rights across multiple parties when issuing blockchain transactions. They are often seen as a way to eliminate insider fraud and improve security guarantees in a decentralized setting.
Such a popularity boom prompts academia to invent better TSS, so it should be no surprise that a lot of research has been going on in the field recently: see Lin17, GG18, CCLST19, GG20. The latter is considered to be the best multi-party ECDSA TSS due to its threshold- and round-optimality, as well as the presence of identifiable aborts.
In theory, all of the above TSS are secure under practically reasonable assumptions, as proved in corresponding papers. In practice, however, specific implementations may suffer from vulnerabilities introduced by the TSS software.
The most widely known Rust implementation of the GG20 is that by industry leaders ZenGo-X. In fact, it was so good that we used it as a starting point for our TSS-based solution. However, after reading this paper, suggested to us by Omer Shlomovits, we found a subtle issue in their code. It lead us to a critical attack described in this note.
As true decentralized security enthusiasts, we quickly got in touch with ZenGo and fixed the discovered security breach in a pull request. It was soon approved and merged into their TSS library. The researcher who found the attack was granted a bug bounty, the biggest in ZenGo’s history.
In the remainder of this note, we will use notation from GG18. We also denote a cyclic subgroup generated by an element g as ⟨g⟩, and its order as |g|.
First, during the distributed key generation, each party generates values h₁, h₂, N, and proves in zero-knowledge that
discrete logs of h₁ and h₂ with respect to each other modulo N exist (i.e. that h₁ and h₂ generate the same subgroup: ⟨h₁⟩ = ⟨h₂⟩).
These values are later used by other parties during the signing to compute z = h₁ᵏ h₂ʳ (mod N), where k is their secret value, and r is a random value used to “hide” k.
Note that k is directly linked to the share of the secret key sk, meaning that we can restore sk if we know k and a corresponding signature.
If h₁ and h₂ generate the same subgroup of a large order, then we get no special information about their powers h₁ᵏ and h₂ʳ that we can use to learn something about k. Formally, this property is called statistical zero-knowledge.
However, during the key generation stage, the implementation by ZenGoonly proved that a discrete log of h₂ with respect to h₁ exists, i.e. that ⟨h₂⟩ is a subgroup of ⟨h₁⟩ (and not vice versa). In particular, it imposes no constraints on |h₂| and how it relates to |h₁|.
The main idea behind the attack is that we want the following three properties to hold simultaneously:
- |h₂| must be small enough so we can brute-force over all possible values of h₂ʳ;
- |h₁| must be large for ⟨h₁⟩ to contain enough elements to uniquely map from h₁ᵏ to k;
- the mapping from h₁ᵏ to k must be efficiently computable, i.e. we must be able to quickly find discrete logarithms modulo N.
One easy way to achieve the first property in the absence of the second dlog proof is to set h₂ = 1, then h₂ʳ = 1 regardless of the choice of r, and z = h₁ᵏ (mod N).
A natural reaction is to explicitly prohibit h₂ = 1, but this does not help much. A more sophisticated (but completely practical) approach for an adversary is to pick h₂ as a random root of unity of small order. Such h₂ can be generated efficiently because we know the factorization of N.
There are multiple ways to pick N in a way that allows us to take dlogs efficiently. One possible choice is to set N = ²²⁵⁶ > q, and use a bit-by-bit algorithm described here.
Another practical option is to pick N as a large smooth number. Then we can use the general Pohlig — Hellman algorithm.
The absence of the second dlog proof (h₁ w.r.t. h₂) makes it very easy for a malicious party to satisfy all three properties described above.
They can then learn the secret share of each party and easily restore the shared secret. As a result, they gain the power to single-handedly sign transactions. This lets them empty the organization’s wallet by transferring all assets to themselves.
To see the attack in action up to the point of private keys exposure, take a look at our repository.
It is worth noting that practical TSS-based solutions usually have multiple levels of defense, and such exploits could be stopped further up the road.
At the same time, it is by no means the desired situation. Indeed, the shared secret may be not a wallet key, but instead, some sensitive information, which our users want to securely store on the blockchain — a use case that our TSS implementation will support upon its release.
A Closing Note
Actually, GG20 requires a third proof — that N is a product of two safe primes and it is also absent in ZenGo’s library. But if h₁ and h₂ do generate the same group, the absence of this proof cannot lead to any information leak — the protocol is statistical zero-knowledge regardless of N.
The original reasoning behind the N assumption was that we do not want other parties to be able to quickly factor in this number. However, as Rivest and Silverman explain in their 1999 article, such factoring-related concerns are no longer relevant, as the current state of the art factoring methods work against safe primes as well.