Counter-Strike: Threshold Attack

Potential attack on threshold ECDSA prevented, counter-terrorists win!

Velas Official
Oct 1 · 5 min read

Disclaimer

Introduction

Although the concept of TSS is not new, this is the first time that it is so widely used in practice by Binance, Thorchain, RenVM, and others.

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.

Background

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.

The Attack

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.

Small |h₂|

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.

Efficient dlogs

Another practical option is to pick N as a large smooth number. Then we can use the general Pohlig — Hellman algorithm.

Exploitation

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

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.

Velasblockchain

Virtual Official

Velasblockchain

Velas is Artificial Intuition-operated DPoS Blockchain and Ecosystem for secure, interoperable, extremely scalable transactions.

Velas Official

Written by

Velas is Artificial Intuition-operated DPoS Blockchain and Ecosystem for secure, interoperable, extremely scalable transactions. Visit: www.velas.com

Velasblockchain

Velas is Artificial Intuition-operated DPoS Blockchain and Ecosystem for secure, interoperable, extremely scalable transactions.