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

During rwc2022, Victor Shoup presented joint work with Jens Groth on the security of additive key derivation and presignatures for ECDSA, which lowers the complexity of breaking ECDSA in this situation to the equivalent of 85 bits of security, rather than the expected 128. Seeing as things with around ~80 bits of security generally are considered insecure by cryptographers, this attack and its mitigations are important to understand and apply in any relevant settings!

Why should we care?

ECDSA is the signing algorithm used to sign transactions in bitcoin and the vast majority of other cryptocurrencies. A break in ECDSA would mean people can forge valid signatures, moving any amount of money they desire from any account to any other account, for example from one controlled by a whale to one controlled by themselves, without even needing to know the private key of the whale.

Additive key derivation (AKD) is used widely throughout the cryptocurrency space as 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 in the large number of software wallets that have adopted BIP32 — a search on github reveals 203,000 mentions. Presignatures are used to reduce the needed rounds of communication during construction of a threshold ECDSA, and this attack importantly relies on the use of presignatures. Before digging into the security proof and attacks identified, we’ll first define both additive key derivation and presignatures, talk about why they’re useful, and recap what ECDSA itself looks like.

ECDSA

Keypairs for ECDSA are composed of a private key k,randomly selected element from the relevant scalar field, and the corresponding public key K = kG, with G the generator of the elliptic curve group in use in the specific application. The signing algorithm for signing a message m with key k is given as follows :

h = hash(m)     // hash to the scalar field
r = random()    // 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)

The verification algorithm is simply that the verifier, given sigma and m, and knowing the public key 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. The use of this is that key rerandomisation can be easily performed, with the knowledge that the new secret key can be computed only by the holder of the original one.

Often additive key derivation is performed by generating a random element j, with J = jG, and then k’ = k + j andK’ = K + J (= kG + jG = (k+j)G) form the new key pair. 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 keypairs that can be created with knowledge of just one long term secret. For cryptocurrency wallets (both hardware and software based), the 24 word seedphrase is used to derive the initial base key pair, and then all others are derived from that using BIP32. This means that in the case you lose your hardware wallet or forget your credentials for a software wallet, you can re-derive all of your keypairs with just one seed phrase. The reason why addition isused 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 m is even known.

Why is this useful?

The value R is referred to as a presignature, and its main value is found when computing threshold ECDSA. In a threshold implementation, the value k is shared across parties, with no single party ever knowing the actual value of k. Each party’s share of k is represented as [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 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 the signautre 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

The inverses make the R = s^{-1}hG + s^{-1}tK line above a bit difficult to parse, but 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 querying a presignature oracle to get an R, then 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 presignature, you then also have a valid signature on m* using j* to change key k and again with R as presignature, without knowledge of k itself. This constitutes a signature forgery, and that 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 situation from O(lambda^(1/2)) to O(lambda^(1/3)), giving the signature scheme an equivalent of security of 85 bits rather than 128. That’s really not good! But there are mitigations.

Mitigations!

The main mitigation suggested is to rerandomise R at time of use, for example 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!