Key recovery attack on BIP32-Ed25519

We shall discuss a key recovery attack on the BIP32-Ed25519 proposal. We consider it unlikely BIP32-Ed25519 was ever deployed in a vulnerable way, but warn against its use since it breaks reasonable interpretations of its own security model.

Problem

BIP32 provides “hierarchical deterministic” key derivation for BitCoin wallets. It’s poorly designed and conflates unrelated functionality, but the only tricky part permits payers to derive a new public key for the payee, for which only the payee can derive the private key.

BIP32 accomplishes this by having the payer (1) make up a new private key by hashing the public key and some additional inputs, (2) derive the corresponding public key, and (3) add this public key to the payees public key. We can do this addition because both public keys are points on an elliptic curve (secp256k1), which is a group. In the end, our payee can produce the private key that corresponds to this public key because the can derive the private key produced in (1) and adding the scalar parts of both it and their own private key to get a private key that corresponds to the combined public key. [1]

We love that secp256k1 is a group of prime order (size), which protects against things like small subgroup attacks, but… We believe Edwards curves to be "safer’, including surviving mathematical advances better better. [2] Also, Edwards curves have complete addition formulas, which gives simpler implementations, and may avoid tricky dangers in key derivation too.

We thus face the question:

How should a key derivation work on an Edwards curve?

There is one good published solution in Next-Generation Hidden Services in Tor by David Goulet, George Kadianakis, and Nick Mathewson, originally proposed by Robert Ransom, which even has a security proof in the random oracle model (ROM). It employs a multiplicative blinding instead of an additive one, but the performance hit resulting from multiplication over addition sounds completely irrelevant, or conceivably even beneficial in some contexts.

There is a questionable solution proposed by Chain, which conceivably enables small subgroup attacks. It requires new signing and verification code though, so maybe they address anything problematic.

There is also a BIP32-Ed25519 by Evernym, which claims to improve upon the Chain proposal by eliminating a timing attack. In fact, there is no timing attack if the underlying library is already constant-time, but worse the Evernym proposal actually enables a far easier key recovery attack.

We make two assumptions in our attack on BIP32-Ed25519:

First, we require that BIP32-Ed25519 be implemented with an Ed25519 library that does clamping immediately before signing. We consider this a reasonable assumption because BIP32-Ed25519 makes supporting this a design criteria.

Second, we give the adversary the power to make numerous small payments in deep hierarchies of key derivations, observe if the victim can cash out each payment, and adaptively continue this process. There are limits on the derivation depth given in BIP32-Ed25519, which makes this attack hard for typical keys. We judge these limits insufficient because simple limits do not protect all keys, other BIPs add depth recklessly, the word “hierarchical” need not indicate limits, and developers might forget or bypass the depth check, and hence we grant our adversary the power to exceed the limits.

We shall discuss two attack routes below:

Cofactors

An Edwards curves always has a point of order 4, unlike secp256k1, so the group itself has order divisible by 4. We could protect against small subgroup attacks by multiplying adversary controlled curve points by this cofactor h such that the curve has order h*l with l prime, but one normally merges this multiplication into the private key instead. As an example, Ed25519 has order 8*l where l is a 252 bit prime, and 8 is the cofactor. In this case, we normally choose 255 bit integer scalars for private keys with the low three bits zeroed, so that doing a scalar multiplication by that scalar including multiplying by the cofactor 8.

We should therefore do the scalar addition mod 8*l for key derivation. We can implement addition mod 8*l from addition mod l as suggested by Mike Hamberg, by bit shifting the 255 bit scalar into a 252 bit scalar, doing the addition mod l, and shifting back to a 255 bit scalar with the low three bits zeroed.

We’d create chaos if we do the addition mod anything else, but BIP32-Ed25519 tries doing it mod 2^256 by restricting their scalar to 224 bits. If however a payer can trick a payee into cashing out many long derivation chains then their derived private key would exceed 8*l and leak private key bits. It sounds okay if one restricts the derivation depth, but this requires all implementations implement this restriction.

As an aside, there are better answers to the overall cofactor problem like using the Ristretto encoding to force all points p to satisfy l*p = 0, but that is another discussion.

Constant-time

There are side channel attacks on most cryptographic primitives, which one minimizes by writing constant-time code. In GCC, you must outwit certain optimizations for this, but even LLVM’s more modern architecture makes constant-time harder. And interpreted or JIT languages like JavaScript make constant-time code very hard.

In Ed25519, DJB decided to requite that private key scalars have their high bit set, as a poor man’s protection against the worst possible timing attacks. Ed25519 has flourished for simple things, in part due to being easier to implement safely in more languages. Yet, this breaks natural homomorphic properties like the addition required by BIP32.

Now BIP32-Ed25519 also tries preserving this high bit by restricting their scalar to 224 bits. Again if a payer can trick a payee into a cashing out many long derivation chains then they’d eventually zero this high bit.

We’d have only a possible side channel attack if this happened inside the ed25529 library, but BIP32-Ed25519 exists to support libraries that set the high bit themselves, in which case signing fails. At this point, our attacker can make payments with derived keys that exhibit different bit patterns in the high bits of the scalars added to the secret keys, observe if the payments are cashed out, and adaptively select the next bits on which they focus. Any non-cashed out payment represents an addition that zeroed the high bit, or possible exceeded 8*l, so the attacker can gradually learn bits from the private key.

Solution

As we said, there is absolutely nothing wrong with the solution provided in Next-Generation Hidden Services in Tor.

We have also implement an additive variant at https://github.com/w3f/hd-ed25519/ which exploits the fact that Isis Lovecruft’s ed25519-dalek library handles extended keys without resetting the high bit. In fact, zeroing the low three bits is not well defined under the scalar addition mod l provided by ed25519 libraries, so we handle the cofactor using Mike Hamberg’s suggestion mentioned above.

It appears the security proof for Tor’s scheme works fine with an additive scheme, due to mostly using only ROM and Ed25519’s security, and never directly using DLOG assumptions.

We emphasize that our additive variant breaks any ed25519 libraries that clamp the bits immediately before signing, including all that do not provide extended keys. This is unavoidable.


[1] An ECDSA hierarchical key derivation scheme is used in the GNU Name System. Also, there are related ideas used in semi-private keys, as used by Tahoe-LAFS, ala “Security notions for cloud storage and deduplication” by Colin Boyd, Gareth T. Davies and Kristian Gjøsteen, Håvard Raddum, and Mohsen Toorani.

[2] In fact, we happily use curves far “worse” than secp256k1, especially curves with pairings like BLS12-381. We expect pairing friendly curves to require replacement roughly as often as RSA key sizes grow, so more frequently than “safe curves”, but not that often. In Polkadot, we shall only use such “weak” curves for temporary signing keys, which protocol upgrades can definitively change, while an Edwards curve sounds safest for values protected over longer time frames, like say 30 years.

[3] BIP32 indexes subkeys with 32 bit integers, so that payees can scan the blockchain for addresses they expect to receive payments on in the near future. There is no way to make scanning the blockchain scalable, so these indexes should be replaced with arbitrary data communicated offchain by the payer.

3 Likes

Curious what you think of https://github.com/satoshilabs/slips/blob/master/slip-0010.md (used in Stellar, Ledger, Trezor, among others)

There is no problem because they provide no soft derivation path for ed25519 keys:
“For ed25519 only hardened key generation from Private parent key to private child key is supported.”