Security disclosure for ECDSA and EdDSA threshold signature schemes
At io.finnet, we’re committed to elevating the finance industry by equipping institutions with advanced tools and systems.
With applied multi-party computation (MPC), enterprise blockchain, and innovative APIs, we’re driving progress in finance. Discover the potential of our offerings, io.vault and io.network, launching in Q1 2023.
We are immensely proud to announce our collaboration with Kudelski Security and the MPC Alliance, two leading organizations in the field of MPC and cybersecurity. Together, we are actively researching security vulnerabilities in the research and code libraries that we use.
In this post, we will provide details on a number of security vulnerabilities that were discovered in several threshold signature schemes for ECDSA and EdDSA, of which there are popular implementations in Go, Rust, and others, used by many projects and companies in the space.
But before we dive into the details, let us introduce you to some of the key concepts and players involved in this finding.
What is a threshold signature scheme (TSS)?
Threshold signature schemes (TSS) are cryptographic protocols that allow a group of parties to generate and verify digital signatures without revealing their private keys to each other or to a third party. TSS can enhance the security and scalability of blockchain and digital asset applications, such as decentralized exchanges, wallets, custody solutions, and more.
A TSS has many applications in the blockchain and digital asset space, for instance:
- Secure key management and backup: split a private key into multiple shares, such that only a subset of the shares is needed to sign a transaction. This reduces the risk of losing or compromising the key, and enables distributed custody and recovery schemes;
- Decentralized governance and consensus: enable a group of nodes to sign blocks or transactions collectively, without relying on a single leader or coordinator. This enhances the scalability and resilience of the network, and prevents censorship or corruption;
- Privacy-preserving transactions: allow a group of parties to sign a transaction without revealing their identities or the details of the transaction. This enables confidential and anonymous transactions, and protects the privacy of the users and the data.
ECDSA and EdDSA are two widely used variants of digital signature schemes based on elliptic curve cryptography. While achieving similar goals, these schemes differ in several ways: ECDSA employs elliptic curve cryptography over prime fields, while EdDSA utilizes twisted Edwards curves, providing a more efficient, deterministic, and secure signing process.
How, and where, are these schemes used?
There are several implementations of these schemes, both public and private, being used today.
The most widely used implementation of the ECDSA and EdDSA threshold signature schemes is known as TSS-Lib, and the vulnerabilities apply to both of these schemes within it.
TSS-Lib is an implementation of the paper “Fast multiparty threshold ECDSA with fast trustless setup” by Goldfeder et al. (ref). Some versions of this library implement newer papers such as “UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts” (ref), or are custom variants.
The original upstream version of TSS-Lib is written in Go and was released on GitHub in 2019. Other variants have appeared online since then, with many known crypto projects making use of that code.
While TSS-Lib is the main implementation that we have identified, there are other forms of the code in other programming languages such as Rust and for alternative runtime environments such as web browsers.
Overview of the Vulnerabilities
The security vulnerabilities were uncovered during an audit of one of our projects by Kudelski Security. We decided to go public with the findings of the audit to raise awareness and help users of threshold signature scheme libraries to mitigate the risks.
After the audit, io.finnet decided to release four high severity issues publicly, CVE-2022–47930, CVE-2022–47931, CVE-2023–26556, and CVE-2023–26557, to help other projects secure their solutions. We will explore each of the disclosures below.
There are four vulnerabilities that we are disclosing, which affect both the ECDSA and EdDSA variants of the TSS implementations. In summary, these vulnerabilities are:
- Replay Attacks Involving Proofs
This vulnerability allows an attacker to exploit the Fiat-Shamir transformation’s challenge generation, thereby enabling replay and spoofing of messages. The impact includes the potential for malicious users or eavesdroppers to undermine the integrity of the zero-knowledge proof system and compromise the security of the protocol.
This issue was assigned the CVE number CVE-2022–47930. - Collision of Hash Values
The SHA256 hash function (known as SHA512_256 in our implementation) and its variants concatenate input values with a “$” separator, which can also appear in the input values, resulting in hash collisions. This issue may compromise the security of the system, as the hash functions should behave like random oracles, making it difficult to find collisions. An example of this vulnerability can be seen in the computation of V_i in Round 1 of the “Auxiliary Info & Key Refresh in Three Rounds”.
This issue was assigned the CVE number CVE-2022–47931.
This issue has been fixed in the upstream bnb-chain/tss-lib as of pull request #233. - Non Constant-Time Arithmetic
The Go language’s big.Int arithmetic is not constant-time, which leaves the implementation vulnerable to timing attacks. This issue can be exploited by an attacker to obtain sensitive information, such as secret keys, by analyzing the execution time of cryptographic operations.
This issue was assigned the CVE number CVE-2023–26556. - Non-Constant Time Scalar Multiplication
Scalar multiplication for the secp256k1 curve is not constant-time, which increases the risk of timing attacks. Similar to the issue in CVE-2023–26556, this vulnerability can be exploited by an attacker to obtain sensitive information by analyzing the execution time of cryptographic operations involving scalar multiplication on the secp256k1 curve.
This issue was assigned the CVE number CVE-2023–26557.
We will explore each of the vulnerabilities and the solutions in detail in the next sections.
CVE-2022–47930: Replay Attacks Involving Proofs
The Fiat-Shamir transformation’s challenge generation is susceptible to replay attacks. A challenge is computed as:
c = H(X.X() || X.Y() || g.X() || g.Y() || A.X() || A.Y())This challenge lacks a unique session identifier (SSID), context string, or random nonce. As a result, a malicious user or eavesdropper can replay a valid proof sent previously, compromising the security of the system.
An attacker could potentially perform man-in-the-middle attacks by replaying valid proofs from past communication sessions. This could lead to unauthorized signing of transactions or manipulation of critical data, causing financial or reputational damage to the affected parties.
To address the issue of replay attacks, the challenge generation in the Fiat-Shamir transformation must be enhanced. The following steps outline the proposed modifications:
- Generate a unique session ID (SSID).
- Compute the challenge using a hash function that takes the SSID, public values, and the prover’s commitment as inputs.
- Use rejection sampling with the computed challenge.
Remediation pseudo-code:
ssid = generate_ssid()
c = H(ssid || X.X() || X.Y() || g.X() || g.Y() || A.X() || A.Y())
c = rejectionSample(c)The same modification should be applied to other zero-knowledge proofs identified in the paper, including dec, affg, enc, logstar, and mul.
CVE-2022–47931: Collision of Hash Values
The SHA256 hash function (known as SHA512_256 in our implementation) and its variants are prone to collisions due to the use of the “$” separator when concatenating input values. The current hash may be expressed as:
h = SHA256(b1 || “$” || b2 || “$” || …)With such a function, an adversary could exploit hash collisions to craft malicious parameters that affect key computation, leading to the potential compromise of shared secrets. This could allow the attacker to gain unauthorized access to sensitive data or manipulate transactions, ultimately disrupting the integrity and trustworthiness of the system.
To address the issue of hash collisions, the function must be modified. Replace the “$” separator with a unique and non-conflicting delimiter. Additionally, use a more robust method to concatenate input values, such as length-prefixed encoding or a Merkle tree.
A fixed version of the function call above could look like this:
h = SHA256(b1 || len(b1) || “$” || b2 || len(b2) || “$” || …)Where len(x) returns a fixed-size (e.g. 64-bit) integer representing the byte length of the data passed as its x argument.
Remediation pseudo-code:
function SHA256(inputs):
if len(inputs) == 0:
return None
serialized_inputs = serialize(inputs)
return SHA256.sum(serialized_inputs)
function serialize(input_list):
result = bytearray()
for input in input_list:
result.extend(input)
result.extend(uint64_to_bytes(len(input)))
result.extend("$")
return resultCVE-2023–26556: Golang’s big.Int Arithmetic Not Constant-Time
Golang’s big.Int arithmetic operations are not constant time, which could lead to timing attacks.
By exploiting timing attacks, an adversary could gather sufficient information to reconstruct private key data. This could lead to a total compromise of the system’s confidentiality and enable the attacker to forge signatures, manipulate transactions, or steal sensitive information, causing significant financial or operational harm.
To address this issue, the code must implement constant-time arithmetic operations or use a third-party library that provides constant-time arithmetic for big integers. Any non-constant time operations in the code should be replaced with constant-time alternatives.
In our fix, we made use of cronokirby/saferith, a Go library that implements constant-time versions of some big.Int methods.
Please note that in the Go 1.20 release, significant changes have been made to Go’s standard library. The math/big package, which is a general-purpose big integer library, is no longer recommended for cryptography due to its lack of constant-time operation guarantees. Instead, the crypto/internal/bigmod package has been introduced, specifically designed for operations modulo a prime number with constant-time behavior.
Moving forward, it is essential to use the constant-time crypto/internal/bigmod for Go apps that involve cryptography. If you’re currently using the math/big package for cryptography code, it is highly recommended to refactor your implementation to use the new crypto/internal/bigmod package.
CVE-2023–26557: Non-Constant Time Scalar Multiplication For secp256k1
Scalar multiplication for the secp256k1 curve is not constant time, which could lead to timing side-channel attacks.
Similar to the impact of CVE-2023–26556, the non-constant time scalar multiplication for secp256k1 could be exploited by an attacker to perform timing attacks and deduce private key data. This could lead to the forgery of signatures, unauthorized manipulation of transactions, and the loss of sensitive information.
To address this issue, replacement of non-constant time arithmetic with an alternative constant-time version is essential. We used a constant-time scalar multiplication function based on Montgomery Ladder Point Multiplication by Prof. Bill Buchanan of Edinburgh Napier University, available here.
Montgomery Ladder Point Multiplication is an efficient algorithm used for constant-time scalar multiplication in elliptic curve cryptography. The algorithm works by computing two intermediate points, R₀ and R₁, and updating them in each step of the “ladder”.
The main idea is to avoid conditional statements that could lead to variable execution times. The Montgomery Ladder performs point addition and point doubling operations simultaneously in a way that does not reveal information about the scalar being used.
Remediation Process
By addressing these vulnerabilities and implementing the proposed modifications, the security of the threshold signature scheme (TSS) library can be significantly improved, making it more robust against potential attacks.
We have notified known users of the TSS-Lib library about these vulnerabilities and provided them with recommendations on how to fix them. We have also published a detailed technical report in the form of CVEs that describe the vulnerabilities, their impact, and their root causes.
We urge users of the TSS-Lib library to review the report and take the necessary actions to secure their applications. We also recommend users to contact us or Kudelski Security for further assistance or guidance.
We are collaborating with Kudelski Security and the MPC Alliance on this disclosure article release, as we share a common vision of advancing the security and privacy of data and digital assets through the application of MPC technology.
About the MPC Alliance
The MPC Alliance is a group of nearly 40 companies of all sizes, from highly innovative startups to global players like Salesforce or Alibaba Group, with the shared mission to accelerate the adoption of multi-party computing (MPC) technology.
The alliance was originally co-founded by Sepior, Unbound Tech, and ZenGo in 2019 and has since grown to include more than 20 members from various industries and regions.
The MPC Alliance aims to increase market awareness, acceptance, and adoption of MPC-based technologies, products, and services, as well as to foster collaboration and innovation among its members.
Visit their website at MPC Alliance.
About Kudelski Security
Kudelski Security is the premier advisor and cybersecurity innovator for today’s most security-conscious organizations. Their long-term approach to client partnerships enables them to continuously evaluate their security posture to recommend solutions that reduce business risk, maintain compliance and increase overall security effectiveness.
With clients that include Fortune 500 enterprises and government organizations in Europe and across the United States, they address the most complex environments through an unparalleled set of solution capabilities including consulting, technology, managed security services and custom innovation.
You may reach Kudelski Security at info@kudelskisecurity.com or visit their website at Kudelski Security.
Closing Remarks
We are honored to work with these two organizations and we hope that this disclosure will contribute to the improvement of the security and reliability of the TSS technology and its applications. We also invite other users and developers of TSS technology to join us in this effort and to contact us or the MPC Alliance for more information.
You can reach us at security@iofinnet.com or visit our website at io.finnet.
This article was authored by Luke Plaster, io.finnet Chief Crypto Architect.
