TSSHOCK: New Key Extraction Attacks on Threshold Signature Scheme (TSS)

Executive Summary

Oct 2022

Verichains started conducting a comprehensive security survey of a popular cryptographic protocol called Threshold Signature Scheme (TSS), widely used in Multi-Party Computation (MPC) wallets and digital asset custody solutions of major blockchains.

Nov 2022

Verichains developed new novel key extraction attacks against t-ECDSA protocol on several popular TSS implementations in Golang and Rust. Unfortunately, despite having undergone multiple security audits, most implementations of GG18, GG20, and CGGMP21, found to be vulnerable to our new key extraction attacks.
Upon successfully constructing working Proof-of-concept exploits, we named our finding TSSHOCK. The attacker could use TSSHOCK to steal potentially millions to billions of USD worth of cryptocurrency, while leaving no trace behind.

Dec 2022

Verichains initiated the process of reporting issues to our clients and later to the projects that were confirmed to be affected.
We also attempted to reach out to the MPC Alliance regarding our attacks, but unfortunately, we could not establish communication with the right contact until a much later time.

April 2023

Verichains started sharing TSSHOCK privately with sveral other proprietary MPC crypto wallets, asset custodians, bridges, and blockchain vendors to verify and address the issues (if applicable). The technical details and PoC exploits were protected under NDA when sharing with vendors to avoid any potential misuse of the attacks.

Aug 10, 2023

TSSHOCK has been released at BlackHat USA 2023 (paper, slides, proof-of-concept exploits).

Overview

At the core of modern Multi-Party Computation (MPC) wallets and digital asset custody solutions of major blockchains is a cryptographic protocol named Threshold Signature Scheme (TSS). Today, many institutions, including banks, exchanges, and wallets, rely on TSS to enable a group of parties to authorize transactions by generating signatures without revealing their individual secret keys. Consequently, the security of TSS is of utmost importance to many digital asset financial ecosystems.

TSS is a cryptographic scheme allowing multiple parties to jointly generate keys and sign messages. For signing a message, at least t (the threshold) out of n (the number of parties participating in the generation ceremony of the key in use) parties are required. There is no trusted dealer as the TSS private key is never constructed (each party only keeps a private key share).

In blockchains, the Elliptic Curve Digital Signature Algorithm (ECDSA) is commonly used to sign and verify transactions. A protocol for TSS using ECDSA, which relies on homomorphic encryption and zero-knowledge proofs, was introduced by Gennaro & Goldfeder in 2018 [GG18] and updated in [GG20, CGGMP21]. Since its initial publication, numerous implementations of the protocol have been developed and are currently being utilized by multiple products to distribute trust among their members. For the rest of this documentation, t-ECDSA term is referred to as the threshold ECDSA proposed by Gennaro and Goldfeder.

Unfortunately, despite having undergone multiple security audits, these implementations - including the de-facto open-source TSS frameworks in Golang and Rust - are still vulnerable to three new key extraction attacks that our team at Verichains has discovered, which we have named TSSHOCK.

We have discovered TSSHOCK after conducting audits over a wide range of open-source t-ECDSA implementations. Most implementations can be attacked with just one member to recover the ECDSA private key. TSSHOCK completely breaks the security of TSS, with proof of concept exploitation demonstrating a full private key extraction by a single malicious party after 1-2 signatures on various popular wallets, non-custodial key infrastructure, and cross-chain asset management protocols.

Attackers can exploit TSSHOCK to steal potentially millions to billions of dollars worth of cryptocurrency from both individual users and institutions, while leaving no trace and appearing innocent to the other parties.

The Vulnerabilities

After conducting a comprehensive security review over a wide range of open-source TSS implementations, we categorized issues into the following common mistakes:

#1: Weaknesses in using ambiguous encoding scheme

One of the most popular implementations of Threshold Signature Schemes is BNB Chain's tss-lib, written in go-lang. Many other projects, such as Multichain, THORChain, io.Finnet, Threshold Network (Keep Network) and Swingby, use their modified version of tss-lib library.

tss-lib uses an ambiguous encoding scheme, in which concat input values with delimiter '$', resulting two input byte array tuples ["a$", "b"] and ["a", "$b"] could output the same hash value.

This is considered a long-time known issue for tss-lib. The issue was reported first time to Binance 4 years ago (2019) by Kudelski Security in tss-lib's security audit report. We did not understand why the issue (KS-BTL-F-09: SHA512_256 interface prone to collisions) was marked as Low Severity in the audit report. This may be due to the auditor's perception that the issue is unlikely exploitable. However, our TSSHOCK attack has demonstrated that this is indeed a critical issue that could break TSS completely.

tss-lib's Security Audit Report, 2019

The issue was tracked and fixed following Kudelski's recommendation at [Audit] SHA512_256 interface prone to collisions #34 in Sept 2019. However, this fix in fact was not enough to mitigate the root cause ambiguous encoding scheme issue and tss-lib was still exploitable.

Last year, Kudelski Security was hired by io.Finnet to audit their modified version of BNB-Chain's tss-lib. Kudelski Security reported to io.Finnet the same hash collision issue again due to concatenating input values with delimiter '$'. The issue this time got mitigated by io.Finnet in a more elegant way and later publicly disclosed as CVE-2022-47931 on Mar 28, 2023.

Kudelski Security/io.Finnet's Security Advisory, 2023

Note: other CVEs disclosed in io.Finnet's disclosure, such as CVE-2023-26556, CVE-2023-26557 were also originally reported four years ago in tss-lib's Security Audit report. However, it was recommended at that time that they did not require fixing (#44, #37)

We classify this issue as ambiguous encoding scheme and exploit it to recover private key, not hash collision. When doing Fiat-shamir transformation, an encoding scheme is involved to serialize the to-be-hashed transcript to bytes. Hence, if the encoding scheme is ambiguous, we do it wrongly.

In Nov 2022, Verichains developed a novel key extraction attack, called $\alpha$-shuffle, that successfully exploited ambiguous encoding scheme issues to break TSS. We built Proof-of-concept key extraction exploits against tss-lib and its variant from Multichain, THORChain, Threshold Network (tBTC), Swingby projects. Note that each project has its own code modifications for different use cases so the actual exploitation is quite complex and different for each implementation.

Taurus's multi-party-sig, a Threshold-ECDSA implementation of CGGMP-21, was also vulnerable to $\alpha$-shuffle attack.

#2: Insecure TSS optimization

Due to the exponential complexity of MPC/TSS, many projects have been trying to optimize the scheme for improving performance and/or scaling MPC products without proving its soundness error. Common pitfalls are:

#2.1 Reduction of dlnproof iterations

Reduction of dlnproof iterations could make the MPC runs faster but it helps the attacker easily guess challenge bits for a small number of iterations

In Multichain's fastMPC implementation, the Iterations parameter was reduced from 128 to 1, thus making it easy to forge by trial-and-error. We developed the second key extraction attack, called c-guess, that could successfully exploit the issue to recover private keys from a malicious node.

#2.2 Use a larger challenge space (similar to Schnorr's Protocol - Proof of Knowledge of Discrete Log) and eliminate dlnproof iteration

Optimize the scheme without proving its soundness error is negligible. Some TSS libraries optimized the algorithm for $\texttt{dlnproof}$ by choosing the challenge to be 256 bits and running only one time. This is similar to discrete log proof for a group of prime order. But in GG, the group order, $phi(N)$, is not a prime number but a composite number. Hence making our third key extraction attack, c-split, possible.

Projects such as Axelar's tofn, ING Bank's threshold-signatures, ZenGo X's multi-party-ecdsa are vulnerable to c-split attack.

#3: Others

Specific languages (e.g., Golang, Rust) or distinct use cases can lead to side channel problems. However, obtaining precise timing data is generally challenging, resulting in relatively low potential for successfully exploiting these vulnerabilities. We decided to look into this later due to our time constraints.

Updated on August 10, 2023: there is a new cool range proof bypass attack recently reported by Fireblocks at BlackHat USA 2023 that likely affects most GG based TSS implementations as well.

The Attacks

We developed three new novel attacks as part of TSSHOCK. As previously mentioned, these attack methods leverage both known weaknesses and newly identified vulnerabilities unique to certain t-ECDSA implementations.

These attacks could completely break the security of TSS, with proof of concept exploitation demonstrating a full private key extraction by a single malicious party after 1-2 signatures on various popular libraries and products.

Our attacks require no abort so the protocol seamlessly continues, leaving no trace and appearing innocent to the other parties.

$\alpha$-shuffle

In $\alpha$-shuffle attack, ambiguous encoding of $\alpha$ values in each iteration of $\texttt{dlnproof}$ allows for more than 1 different values lists to be encoded equally. The idea to attack is chaining $\alpha$ values such that it can be interpreted in more than 2 ways, e.g., $\alpha||\alpha||\alpha$ can be interpreted as $\alpha||(\alpha||\alpha)$ or $(\alpha||\alpha)||\alpha$. Set $\alpha$ to be corresponding to challenge bit 0 and $\alpha||\alpha$ to be corresponding to challenge bit 1. $\alpha$-shuffle attack first guesses how many challenge bits that are 1 (or 0) and generates temporary $\alpha$ values. After the Fiat-Shamir heuristic is applied, the challenge bits are revealed, if the count of bit 1 (or 0) is correctly guessed, then alpha values are rearranged so that they are ordered correctly with each challenge bit. If the guess was wrong, then try again.

c-split

In c-split attack, the optimized algorithm for $\texttt{dlnproof}$ chooses the challenge to be 256 bits and runs one time. This is similar to discrete log proof for a group of prime order. But in GG, the group order, $phi(N)$, is not a prime number but a composite number. According to the formula, $\rho + c \cdot \log_{h_2}{h_1} \mod N$, $log_{h_2}{h_1}=\frac{1}{e}$ is non-existent if $gcd(e, \phi(N)) \neq 1$ (no inverse for $e$). If $e \mid c$, $c \cdot log_{h_2}{h_1}$ is computable and the proof is created despite $\frac{1}{e}$ not a valid number in $\mod N$. Bruting $c$ for a chosen small $e$ number can be done with success probability of $\frac{1}{e}$ and without risk because $c$ is calculated using Fiat-Shamir heuristic. The recovered secret values are incomplete as they are now in $\mod e$. To recover the secret, another signing phase(s) can be executed to collect other incomplete parts of the same secret and combine using lattice attack (similar to nonce leakage recovery attack in ECDSA).

c-guess

c-guess attack is done by guessing what challenge bits are when computing $\texttt{dlnproof}$. If the iterations (bits count) are small enough, this can be effectively guessed. The probability for a successful guess is $\frac{1}{2^\text{iterations}}$. Fiat-Shamir heuristic also makes the attack risk free.

TSSHOCK has been released at BlackHat USA 2023 (paper, slides, proof-of-concept exploits). We demonstrated how exploitation works and share the lessons we have learned from our research, which could benefit the MPC community.

Vendor Information

As part of our vulnerability disclosure process, starting from Dec 2022, Verichains initiated the process of reporting issues to our clients and later to the projects that were confirmed to be affected with PoC exploit.

Due to the large number of open-source MPC libraries and products implementing t-ECDSA that may be affected, we went to the second wave of disclosure, sharing privately TSSHOCK with many other proprietary MPC crypto wallets, asset custodians, bridges and blockchain vendors to verify and address the issues (if applicable) from Mar - Aug 2023.

The details of TSSHOCK and PoC exploits were protected under NDA when shared with vendors to avoid any potential misuse of the attack. Unfortunately, it appears that some attack information might be leaked earlier.

Axelar (tofn)

Tofn(t-of-n) is a threshold cryptography library in Rust implementing of the GG20 threshold-ECDSA protocol.

Previous audits: NCC Group (2021), Cure53 (2021), Adrian and Lucas (2021)
Status: Not yet fixed. Axelar responded that they do not make use of threshold ECDSA on Axelar Network. We strongly advise any projects using tofn for threshold ECDSA, should review its code.
Exploitation/PoC: to be released at https://github.com/verichains/tsshock

BNB Chain (tss-lib)

tss-lib is one of the most popular implementations of Threshold Signature Scheme from Binance/BNB-Chain.

Previous audits: Kudelski Security (2019)
Status: Fixed ambiguous encoding issue based on patches from io.Finnet. We strongly recommend that any projects built upon this library should use the latest version of tss-lib.
Exploitation/PoC: to be released at https://github.com/verichains/tsshock

ING Bank (threshold-signatures)

threshold-signature is a threshold cryptographic library in Rust implementing GG18 threshold-ECDSA protocol.

Previous audits: Kudelski Security (2021)
Status: Not yet fixed. We could not contact the project owner to fix the issues so the code is still vulnerable to TSSHOCK. We strongly advise that any projects based on this library should review their code and stop using this library.
Exploitation/PoC: to be released at https://github.com/verichains/tsshock

Multichain (Anyswap)

Multichain is a cross-chain bridge, utilizing a modified version of tss-lib.

Previous audits: Trail Of Bits (2022)
Status: Fixed. Multichain was vulnerable for both $\alpha$-shuffle and c-guess attacks.
For c-guess attack, it appears that only Multichain's fastMPC was vulnerable. The issue was fixed after being reported in December 2022. As a result, we have released an advisory VSA-2022-120 for that specific issue much earlier in March 2023.
Exploitation/PoC: to be released at https://github.com/verichains/tsshock

Swingby

Swingby is a staking-powered protocol for warp speed bridging of DeFi assets. Swingby uses a forked version of tss-lib to build Threshold Signature Scheme for Skybridge.

Previous audits: Red4Sec (2020)
Status: Not yet fixed

Taurus (multi-party-sig)

multi-party-sig provides a Threshold-ECDSA implementation of CGGMP-21. This library has ambiguous encoding issues and is vulnerable to $\alpha$-shuffle attack.

Previous audits: None. However, a forked version of this library from multisig-labs was audited by Kudelski Security in Oct 2022.
Status: Fixed. We strongly recommend any products using this library update the code to the latest version.
Exploitation/PoC: to be released at https://github.com/verichains/tsshock

THORChain

THORChain, is a decentralized cross-chain liquidity protocol that allows users to swap assets between blockchain networks. THORChain uses a modified version of tss-lib.

Previous audits: Kudelski Security (2020)
Status: Fixed.
Exploitation/PoC: to be released at https://github.com/verichains/tsshock

On March 28, THORChain mainnet was halted globally after we shared our attack paper and a full working PoC exploit that could steal assets from THORChain's mainnet vaults (US$180M TVL at at time) by a single malicious THORnode via the bug bounty program.

demo attack was done on a private testnet

After receiving our paper and full working $\alpha$-shuffle exploit, THORChain, running by an anonymous team, became highly unresponsive, with several weeks without any response to our inquiries about their progress in addressing the issue. Later, after more than 2 months, they replied with a reject for the bug bounty, because our attack exploited an already known hash collision vulnerability.

As discussed above, the new $\alpha$-shuffle technique exploits the ambiguous encoding scheme to recover private key, not hash collision. But whether $\alpha$-shuffle attacks a known issue (the 4-years old ambiguous encoding scheme in tss-lib) or new issue (Taurus's multi-party-sig), the important fact remains that THORChain mainnet was running vulnerable code and all customer funds was at risk at the time we shared $\alpha$-shuffle attack with them. Important questions to ask:

If THORChain was already aware of this attack and its critical impact much ealier as they said, why didn't they fix it ealier but still continue running the vulnerable mainnet and putting all customer funds (US$ 180M TVL) at significant risk?
Then why did they halt globally THORChain mainnet only after receiving our PoC exploit proof?

Our recommendation is for everyone to avoid using any bridge network that is built upon immature MPC/TSS complex cryptography protocols. These networks normally would allow a malicious node to join with enough of token stacking/bonding but are highly prone to be vulnerable to MPC/TSS attacks..

Threshold Network (tBTC)

Threshold Network, is a merger of Keep Network and NuCypher. tBTC is a decentralized Bitcoin to Ethereum bridge, built on top of the Threshold Network. It maintains a forked version of tss-lib.

Previous audits: Consensys (2020), Trail of Bits (2020), Sergi Delgado (2020)
Status: Fixed. Threshold Network follows upstream tss-lib for security patches.

Exploitation/PoC: to be released at https://github.com/verichains/tsshock

Exploitation demo on how a single malicious party could steal BTC assets from Threshold Network's TSS-based BTC wallets.

demo attack was done on a private testnet

Zengo-X (multi-party-ecdsa)

Zengo-X's multi-party-ecdsa is another implementation of GG20 in Rust.

Previous audits: Kudelski Security (2019)
Status: Won't fix. Last July, Zengo updated the repository and indicated that they do not use this code in production and the repository is no longer being maintained. We strongly advise any projects based on this library should review its code or use another implementation.
Exploitation/PoC: to be released at https://github.com/verichains/tsshock

Vendor	Status	PoC Exploit	Attack	Fix Status	Required number of ¹
Vendor	Status	PoC Exploit	Attack	Fix Status	malicious parties	(re)sharing ceremonies	signatures
Axelar (tofn)²	Affected	Yes	c-split	Not yet fixed	1	1	2
BNB Chain (tss-lib)³	Affected	Yes	$\alpha$-shuffle	Fixed	1	1	1
ING Bank (threshold-signatures)⁴	Affected	Yes	c-split	Not yet fixed	1	1	2
Multichain⁵	Affected	Yes	$\alpha$-shuffle	Fixed	1	1	1
Multichain⁵	Affected	Yes	c-guess	Fixed	1	1	1
Swingby (tss-lib)⁶	Affected	Yes	$\alpha$-shuffle	Fixed	1	1	1
Taurus (multi-party-sig)⁷	Affected	Yes	$\alpha$-shuffle	Fixed	1	1.5526	1
THORChain⁸	Affected	Yes	$\alpha$-shuffle	Fixed	1	1	1
Threshold Network(tBTC)⁹	Affected	Yes	$\alpha$-shuffle	Fixed	1	1	1
ZenGo X (multi-party-ecdsa)¹⁰	Affected	Yes	c-split	Won't fix¹⁰	2	1	1
…¹¹	-	-	-		-	-	-

Notes:

The table above was calculated based on the assumption that the attacker could practically break 64-bit security.

We shared privately our attacks with a number of proprietary vendors to verify and address the issues (if applicable). We are unable to confirm or disclose (due to NDA restrictions) regarding the vulnerability status of some vendors.

Acknowledgements

We would like to thank Binance Security Team, BNBChain developers, Multichain team for their swift response, JP Aumasson and few other researchers for valuable, insightful discussions.

The bug bounty reward from Multichain is also appreciated.

Q&A

Are TSSHOCK new attacks?

Yes, we have developed three new attacks under TSSHOCK called $\alpha$-shuffle, c-split and c-guess attacks. The new attack techniques can exploit both known flaws as well as new vulnerabilities that are specific to certain t-ECDSA implementations.

Most implementations of GG18, GG20, and CGGMP21 are vulnerable. The attacks require no abort so the protocol seamlessly continues, leaving no trace and appearing innocent to the other parties.

If your funds are protected by vulnerable products, you should assume the private keys are likely leaked. Patch the vulnerable software, re-generate keys and move your funds to the new wallets.

All TSS members are trustworthy, am I safe?

The goal of MPC/TSS is to minimize the trust between members. If members are all trustworthy, then using TSS is rather unnecessary. This concern applies to many decentralized projects based on MPC/TSS, such as Multichain or THORChain, where the MPC/TSS network is prone to being controlled by a specific group of individuals (as seen in the recent Multichain incident)

Even in scenarios where all members are considered trustworthy, there remains a vulnerability to internal employees or operators causing harm through malicious actions.

How do I know if a product is affected?

If you are a maintainer of a t-ECDSA library or a product that relies on such a library, it would be prudent to assume that the library may contain security vulnerabilities and take measures to mitigate the risks. We suggest conducting a security audit or reaching out to us for assistance in evaluating the security of both the library and your product.

If you are a user of a product that employs a t-ECDSA library, it is crucial to contact the product's owners and inquire about their approach to any potential security concerns regarding the library. This will allow you to assess the level of risk associated with utilizing the product and take necessary measures to safeguard your assets.

Do I need to rotate TSS key/share after patched?

After patching, it is important to generate new private keys and migrate assets for all wallets. This is because there is a possibility that a malicious party may have already exploited the flaw before it was fixed, and could have collected private keys of wallets. By rotating keys, you can prevent them from stealing assets later on.

What are the key takeaways from TSSHOCK?

Developing custom and complex cryptography protocols can be extremely challenging and dangerous. Such solutions are highly susceptible to errors in both technical design and implementation, which can result in severe security vulnerabilities.
Optimizations for cryptographic protocols are frequently implemented in-house without undergoing a thorough security evaluation, which can result in new security issues being introduced and wrongly perceived as low-risk.
New cryptographic tools and protocols must undergo a rigorous security evaluation before being used in production, especially in critical products such as blockchains.
To ensure the highest level of security, it is recommended to perform multiple security audits conducted by different vendors. Even if the code has undergone rigorous evaluation, it may still contain critical vulnerabilities.

Why did you decide to release this information?

Considering that MPC/TSS represents a relatively new protocol, the number of available implementations may be limited, with the possibility of some containing vulnerabilities. The widespread use of these libraries in various products, either directly or through forking, can increase the potential impact of an attack.

Stakeholders and users need to stay updated and assess the potential risks of using new protocols and technologies in order to make well-informed decisions.

About us

Verichains is a leading blockchain security firm specializing in code audits, cryptanalysis, perimeter security, and incident investigation. Founded in 2017 by world-class security researchers, the company leverages extensive expertise in security, cryptography, and core blockchain technology and has helped investigate and fix security issues in the largest crypto hacks, including the BNB Bridge and Ronin Bridge. For any inquiries or questions, please get in touch with us at [email protected].

Homepage: https://www.verichains.io
Twitter: https://twitter.com/Verichains
Linkedin: https://www.linkedin.com/company/verichains
Facebook: https://facebook.com/verichains
Telegram: https://t.me/+Y29xcaxJLJxjNDVl

Last updated on August 9th, 2023