Introduction
io.finnet hired us to perform a code audit of their threshold ECDSA signature implementation called tss-lib based on the paper UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts of Canetti et al. written in Go language. After the audit, io.finnet decided to publicly release some of the highest severity issues we found in our audit to help other projects to secure their solutions. These issues have been assigned the following CVE numbers: CVE-2022-47930, CVE-2022-47931, CVE-2023-26556 and CVE-2023-26557.
Description of the security problems
CVE-2022-47930: Replay attacks involving proofs
Often MPC threshold schemes use zero-knowledge proofs to avoid participants cheating and to prove the validity of some parameters. As mentioned in RFC 8235, proofs must not be easily replayed. In the io.finnet implementation, the challenge of the Fiat-Shamir transformation (for instance, in a NIZK implementation) doesn’t include a combination of session id, context string, and a counter or random nonce thus, it allows replay attacks.
The vulnerability we identified arises from the fact that the parameter ssid for defining a session id that is typically included in the paper describing the construction is not used throughout the affected MPC implementation.
Consequently, this allows replaying and spoofing of messages under certain scenarios. In particular, the Schnorr proof of knowledge implemented does not use a session id, context or random nonce in the generation of the challenge. This could allow a malicious user or an eavesdropper to replay a valid proof sent in the past. For instance, in the NewProof function, the challenge is computed as:
// Fig 22.2 e
var e* big.Int {
eHash:= common.SHA512_256i(X.X(), X.Y(), g.X(), g.Y(), A.X(), A.Y())
e= common.RejectionSample(q, eHash)}
}
We also discovered that this problem affected other zero-knowledge proofs utilized in the scheme; these proofs are identified in the paper by the following names: dec, affg, enc, logstar and mul (See Section 6 and Appendix C in the paper).
CVE-2022-47931: Collision of hash values
The functions SHA512_256 and SHA512_256i are used to hash bytes or big integer tuples, respectively. They take as input a list of values and output a hash. According to the paper, those hash functions should behave like a random oracle, and thus it should not be easy to find collisions.
The issue we found arises when hashing multiple concatenated input values, for example, a list of bytes [“a”, “b”, “c”]. The two vulnerable functions concatenate the values by adding a separator “$” between each value to obtain the string “a$b$c”. Then this string is passed to the hash function SHA-512/256 to obtain the hash result. However, the character "$" may itself be part of the input values, so this construction is prone to collisions. As an example, the two input byte array tuples ["a$", "b"] and ["a", "$b"] output the same hash value.
Here is a test example:
func TestHashCollision(t *testing.T) {
b1 := []byte("a$")
b2 := []byte("b")
h1 := common.SHA512_256(b1, b2)
println(hex.EncodeToString(h1))
b1 = []byte("a")
b2 = []byte("$b")
h2 := common.SHA512_256(b1, b2)
println(hex.EncodeToString(h2))
assert.Equal(t, h1, h2)
}
This test should not pass, but we obtain the following result:
=== RUN TestHashCollision
eef0de06a51453040e2fa6c7111a9e84233296f51b0992ca2a18221d232a6568
eef0de06a51453040e2fa6c7111a9e84233296f51b0992ca2a18221d232a6568
--- PASS: TestHashCollision (0.00s)
PASS
ok command-line-arguments 0.003s
This issue not only invalidates the security guarantees given by the cryptographic proof of the paper (because the proof relies on the random oracle model), but it may allow practical attacks since the hash function has easy-to-find collisions. For example, the function SHA512_256i is used for the computation of a challenge in the Round 1 of the “Auxiliary Info & Key Refresh in Three Rounds”. A collision can thereby be created with some maliciously crafted parameters at this step.
CVE-2023-26556 and CVE-2023-26557: Non constant-time arithmetic is used in critical cryptographic implementations
Both issues (CVE-2023-26556 and CVE-2023-26557) are about the usage of non-constant-time operations during critical operations. Golang’s big.Int arithmetic implementation doesn’t provide constant-time methods for some arithmetic operations, which could contribute to the leaking of sensitive data. For instance, the modular Go exponentiation implementation mentions:
// Modular exponentiation of inputs of a particular size is not a cryptographically constant-time operation.
The first issue concerns the usage of Cmp, the comparison method, the Exp, modular exponentiation, and the modular inverse on sensitive values. One possible consequence is the usage of Exp could leak the value of lambda of the private key of the Paillier cryptosystem.
The second issue regarding the threshold cryptography implementation we audited is the usage of the secp256k1 curve in the Go crypto/elliptic package. This implementation does not provide a constant-time scalar multiplication method for operation on this curve as mentioned by the following comment:
// If there is a dedicated constant-time implementation for this curve operation, use that instead of the generic one.
This type of implementation could leak the involved secret scalars. An example is the computation of the public key share X which uses the secret key-share x during the second round of the scheme.
Concluding remarks
Our advice to people implementing Cryptographic protocols from academic papers, try to not deviate from the paper and try to implement time-tested solutions. The gap between an academic paper and its actual implementation can be tricky, and there are pitfalls. We hope that publishing these pitfalls and explaining them will allow for developing more secure solutions with higher resistance to attack.
Kudelski Security Research 