rwc2022 : Threshold ECDSA with additive key derivation and presignatures : an attack, and a solution

2022-05-11 by Rebekah

During rwc2022, Victor Shoup presented joint work with Jens Groth on the security of additive key derivation and pre-signatures for ECDSA. Additive key derivation (AKD) is used widely throughout the cryptocurrency space as it’s specified in BIP32, the de facto cryptocurrency standard for a heirarchical and deterministic key derivation process. BIP32 is used to derive keys in both Ledger and Trezor hardware wallets, and a large number of software wallets that have adopted BIP32 – a search on github reveals 203,000 mentions.

Before digging into the security proof and attacks identified, we’ll define both AKD and presignatures and recap what ECDSA itself looks like.

Keypairs for ECDSA look like k, K = kG, where G is a generator of an elliptic curve group, and k is a randomly selected element from the scalar field.

The signing algorithm for signing a message m with key k is given as follows :

h = hash(m) (to the scalar field)
r randomly generated from the scalar field
R = rG t = F(R) // where F is a function that maps R back to the
                // scalar field (commonly taking the x coordinate)
if t == 0 || h + tk == 0, fail
else s = r^{-1} (h + td)
return sigma = (s, t)

And the verification algorithm is simply that the verifier, given sigma, and m, and knowing K, performs the following :

h = hash(m)
R = s^{-1}hG + s^{-1}tK
if R == 0 || F(R) != t, fail
else signature is valid

Additive key derivation

Additive key derivation is a process of taking the public key from the key generation algorithm given above and adding another number to it, so that the new secret key can be computed only by the holder of the original one. Often this is done by generating a random element j, with J = jG, and then k' = k + j, and K' = K + J (= kG + jG = (k+j)G). In BIP32’s case, the element j is instead derived from some information in a deterministic way, which is where the name hierarchical deterministic key derivation comes from. The elements J and j do not need to be private for the process to be secure (where security here means that only the original holder of k can compute k + j and sign transactions corresponding to the new key pair).

Why is this useful?

Key derivation protocols are useful because they increase the number of key pairs that can be created with knowledge of just one long term secret. For cryptocurrency wallets (both hardware and software based), the 24 word seed phrase is used to derive the initial base key pair, and then all others are derived from that one using BIP32. This means that in the case you lose your hardware wallet or forget credentials for a software wallet, you can re-derive all of your keypairs with just the one seed phrase. The reason why addition is used over some more complicated key derivation process is mainly due to efficiency and simplicity.

Presignatures

Presignatures take into account that one of the threads of computation of the ECDSA signing algorithm doesn’t depend on the message being signed at all. It’s perfectly possible to generate r at random, then compute R = rG and t = F(R) before the message itself is known.

Why is this useful?

The value R is referred to as a presignature, and it’s main value is found when computing threshold ECDSA. In a threshold implementation, the value k is shared across parties, with no one party knowing the true value of k. Each party’s share is represented [k]. In this setting, it’s also possible to precompute, for a random scalar u, sharings [r], [u], [r′] = [ru], and [k′] = [ku].

With these precomputed shares, to sign a given message m, the parties only need to locally compute h = hash(m), and [v] = h[u] + t[k′], and then they can share their values [v] and [r'] (opening the secret sharings, to reveal v and r themselves), which allows

s = v/r' = (hu + tku)/ru = (h + tk)/r

to be computed with only one round of interaction between parties after the message m is decided, rather than the two rounds that would be needed otherwise.

ECDSA + presignatures + additive key derivation – an attack

The verification algorithm for ECDSA is that given sigma, m, K:

h = hash(m)
R = s^{-1}hG + s^{-1}tK
if R == 0 || F(R) != t, fail
else signature is valid

Rewriting this we have sR = hG + tK. For additive key derivation, this equation instead becomes sR = hG + t(K + jG), or rewritten, sR = (h + tj)G + tK.

We then have a weakening of security due to being able to manipulate (h + tj). The attack works by quering a presignature oracle to get an R, computing t = F(R) (as normal), and then finding m, j, m*, j* satisfying h + tj = h* + tj*. Given a signature for m, using j to change the key k, and with R as the pre-signature, you then also have a valid signature on m* using j* using k, and R as pre-signature (without knowledge of k itself). This constitutes a forgery, and is not good.

What does this attack mean for threshold ECDSA with presignatures and AKD?

With security parameter lambda, the ability to forge a proof by finding m, j, m*, j* that satisfy h + tj = h* + tj* lowers the complexity of breaking ECDSA in this sitaution from O(lambda^1/2) to O(lambda^1/3), equivalent to security of 85 bits rather than 128. That’s not good! But there are mitigations.

Mitigations

The main mitigation suggested is to rerandomise R at time of use, by some public value only generated at time of signing. R would then instead become R + deltaG, which eliminates the possibility of t being known in advance, meaning that an attacker no longer has enough information to solve h + tj = h* + tj* for any h, j, h*, j*, as t itself is not known in advance. In a cryptocurrency setting, it’s easy to think of sources for this public randomness, for example the blockhash of the previous block, etc. And then the attack is eliminated!