HD keys for Ed25519

[peacekeeper]

/re hierarchical-deterministic-keys--bip32-and-beyond.md
/re cool-hack-xdi-blockstore-bip32.md

We are exploring "cryptographic numbers" to be used for personal identity. In the context of an XDI-based PoC, we define "cid-1" identifiers created from Ed25519, as well as "cid-2" identifiers created from secp256k1. The former curve is attractive for its credibility in the open/free Internet community, whereas the latter has some desirable crypto properties such as hierarchical deterministic keys (see BIP32).

Issue: What would it take to have HD keys for the Ed25519 curve?

[sipa]

Curve25519 secret keys require specific bits to be set and unset. That is incompatible with the linearity that BIP32 and related schemes (pay to contract) require.

[benma]

@sipa

That is a bummer. Is there a way to make it work (I guess not since one probably cannot infer from the deduced public key whether the deduced private key has the 255th bit set)? Do you know of any other useful algorithms that rely on linearity in the secret keys, which would not work with ed25519?

Edit: maybe it is possible by sacrificing one bit in the secret key.

[ChristopherA]

@sipa I spoke to Daniel Bernstein and Tanje Lang #RealWorldCrypto and the say we can do HD keys with 25519. The low 3 bits are cleared to avoid the small subgroup attack, so for the HD derivation you multiply the result by the small subgroup, i.e. 8. The high byte being cleared is only implementation specific, a good implementation doesn't need to do it.

They said that that the TOR team is doing derived keys using this method so I'll look further into that.

[ChristopherA]

Here is the only thing I've found so far about TOR considering using it:

https://trac.torproject.org/projects/tor/ticket/8106

https://lists.torproject.org/pipermail/tor-dev/2012-September/004026.html

[arnuschky]

I am curious about Ed25519 hierarchical deterministic keys as well (for totally unrelated reasons, though ;) ). Did anyone make any progress on this? I fiddled a bit with us using ed25519-python, but didn't get anywhere.

[shea256]

@peacekeeper @ChristopherA @benma @arnuschky
Would any of you be interested in combining resources for a bounty to be rewarded to whomever can implement a BIP32 library with Ed25519?

[benma]

@shea256 you can't do it with the normal ed25519. As @ChristopherA mentioned, you need to change the ed25519 format to not set the most significant bit, to restore linearity. It does not weaken the scheme, but it wouldn't be compatible with all the ed25519 implementations out there.

If you decide to ignore the most significant bit, implementing bip32 is not super difficult. You could just take one of the existing implementations and replace the curve / curve operations.

[shea256]

Ha I know I can implement it by building off of an existing implementation but I would prefer to have someone else tackle it and contribute financially to their efforts.

[zmanian]

Chain has a spec for this https://chain.com/docs/protocol/specifications/chainkd

…

On Wed, Dec 21, 2016 at 8:38 PM Ryan Shea ***@***.***> wrote: Ha I know I *can* implement it by building off of an existing implementation but I would prefer to have someone else tackle it and contribute financially to their efforts. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#13 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAFs-rqaIaIUsDKDlLe1FgYxqLaS3-fRks5rKf6pgaJpZM4GYU9M> .

[shea256]

@zmanian Oh very cool, thanks! Is there code anywhere for this?

[zmanian]

https://github.com/chain/chain/tree/main/crypto/ed25519/chainkd

…

On Wed, Dec 21, 2016 at 8:54 PM Ryan Shea ***@***.***> wrote: @zmanian <https://github.com/zmanian> Oh very cool, thanks! Is there code anywhere for this? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#13 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAFs-pdE4vkx6kjym0arEt24y0Krnn6Bks5rKgJpgaJpZM4GYU9M> .

[shea256]

@zmanian Awesome, thanks! Do you use Chain Core?

[zmanian]

Nope!

[jasonalaw]

Hey, @shea256. We wrote a spec for HDKeys for Ed25519 here. We also have some early code (python) that we can publish if there's enough interest.

@ChristopherA suggested we compare to ChainKD. @khovratovich and I are taking a closer look.

[jasonalaw]

@shea256, we took a closer look. It looks like there are some issues with Chain's approach. Here are some high-level findings...

EdDSA requires the highest bit to be cleared, and the second highest bit to be set. In their scheme, Z_L and k^P_L are added together and even though they individually meet the highest bits criteria, the sum modulo n may not.

Bit 254 is set to make some implementations of EdDSA constant-time. Without that protection, the resulting extended private key is vulnerable to timing attacks on an implementation that uses bit-searching multiplication.

Also, the signature procedure is not compatible with EdDSA, so existing libraries couldn't be fully reused.

Having fully compatible EdDSA extended keys is nice when you can't control all of the implementations using it. It's also nice not to have to explain why it's OK that your EdDSA key is non-standard.

I don't know the Chain folks. It might make sense to connect with them to talk through our approaches. Someone want to make an introduction?

[dpc]

Please excuse my ignorance here. Just trying to educate myself. Is there anything preventing using BIP32-like construction, but with "seeds" (as like in libsodium) where sub-keys are just a H(base_key || subkey_n) concatenation or something like that? The way I understand it, the only property lost would be generating xpubs allowing deterministic derivation of public keys without knowing the secret key, which is is not great, but at least it's a way to have HD derivation from one key. Are there any other downsides / limitations?

[ChristopherA]

Doing equivalent to HD keys in 25519 space is not easy, as not all keys are valid unlike secp256k1. There has been proposals for how to do HD keys by some Evernym folk, but I don’t know current status, cryptographic review or working code.

— Christopher Allen

[zmanian]

curve25519 is not a prime order curve. It is a cofactor 8 curve. As a result, it difficult to use the homomorphism between scalar and point addition safely because it is easily to end with points that are not in the prime order group.

Ristretto is designed to solve these problems.

We haven't yet designed an HD key scheme for ristretto but we are interested in doing so.

[llorllale]

@peacekeeper @ChristopherA were any working implementations made?

[ChristopherA]

In fact this is an issue that I'm concerned about. Clearly some 25519-based blockchains are able to secure using Ledger or Trezor hardware, which means they are turning cryptographic seeds into HD master keys (master private key and chaincode), however, how they are deriving child keys in 25519 is non-trivial, and I've not seen a consensus on what is the best way to do so. I know that Everynym had at least one proposal a few years ago, but I have also heard there were some concerns and that there may be at least one other. Also note that the non-standard ristretto variant of 25519 may not have the same HD issues that standards based 25519 has.

A survey on how actually deployed implementations of 25519 HD key derivations is needed.

[baha-ai]

Does this spec seem to answer this issue: https://github.com/satoshilabs/slips/blob/master/slip-0010.md#test-vector-1-for-ed25519

There are reference implementations in the readme, and I also found a GoLang implementation (based off of the original BIP32 Go implementation):
https://github.com/lmars/go-slip10

update: unfortunately the Golang implementation doesn't have Ed25519 key conversion, it's only creating an HD key using NIST - P256 curve.

[HRezaei]

Hi everyone!
I have prepared a working implementation of EdDSA and HD and have been able to sign messages and verify them using other libraries.

However, I don't have a deep knowledge of cryptography, and to resolve an issue in the signing operation, I've used something extra suggested by a more experienced developer, but he discouraged using it in production.

Thus, I'm wondering if anyone here is willing to take a look at this and let me know their opinion? How safe or unsafe is this implementation and what is needed to be done to make sure it's suitable for production?

[ChristopherA]

There are some real risks of using HD-Keys with 25519. The reason is cryptographic and has to do with the consequences of having to clamp the raw private key, and additional tests to remove weak keys. These, combined with the other characteristics of 25519's curve's cofactor of 8, has resulted in cryptographers suggesting avoiding HD-Keys with 25519, and otherwise moving over to Ristretto for new protocols like FROST.

• On clamping: https://www.jcraige.com/an-explainer-on-ed25519-clamping
• On weak keys: https://eprint.iacr.org/2020/1436.pdf
• On clamping and HD-Keys: https://moderncrypto.org/mail-archive/curves/2017/000858.html
  • https://moderncrypto.org/mail-archive/curves/2017/000874.html
  • https://mailarchive.ietf.org/arch/msg/cfrg/lM1ix9R-0tVzhZorQhQlKvi4wpA/
• On cofactor: https://moderncrypto.org/mail-archive/curves/2017/000888.html
  • Hierarchical Deterministic Keys jedisct1/libsodium#609 (comment)
• Ristretto - The Ristretto Group
  • RFC 9496 - The ristretto255 and decaf448 Groups

I think it is reasonably safe to use devices like Ledger and Trezor that use BIP32 HD-Key technique to derive a single master key for a coin (as it does for Ethereum, Tezos, etc.) but going beyond that for multiple keys with hardened/unhardened aspects, with HD-Keys, are broken in 25519.

Coincidently, I'm currently puzzling HD-Key-Like thoughts for Ristretto, where it will be "safer", but also take advantages of other requirements that BIP-32 breaks. For instance, the double-SHA256 hash is overkill, and in fact, using a zk-friendly hash, could have some really powerful advantages. You could then safely offer a zk-proof that a particular key is derived from another, which you can't do with HD-Keys.

I have a bunch of notes on 25519 and these issues in a gist at https://gist.github.com/ChristopherA/a7732cdd01c99b8bd1859708dc5ef9a1 — they are not quite curated for broad consumption, but some good links in there.

-- Christopher Allen

[ChristopherA]

Hi everyone! I have prepared a working implementation of EdDSA and HD and have been able to sign messages and verify them using other libraries.

However, I don't have a deep knowledge of cryptography, and to resolve an issue in the signing operation, I've used something extra suggested by a more experienced developer, but he discouraged using it in production.

Thus, I'm wondering if anyone here is willing to take a look at this and let me know their opinion? How safe or unsafe is this implementation and what is needed to be done to make sure it's suitable for production?

my above note is about edDSA aka ed25519. ECDSA, in particular, threshold-ECDSA is another matter, and may plausible.

[HRezaei]

Thank you @ChristopherA for your reply and the links! I'll take a deeper look into them soon.

I think it is reasonably safe to use devices like Ledger and Trezor that use BIP32 HD-Key technique to derive a single master key for a coin (as it does for Ethereum, Tezos, etc.) but going beyond that for multiple keys with hardened/unhardened aspects, with HD-Keys, are broken in 25519.

Actually, our purpose is to provide services like Ledger and Trezor, but our requirements are mainly two things:
1- Keeping only a single master key (generated in MPC distributed manner) and deterministically derive public child keys using a path from that master.
2- Being able to sign messages using the master key and a path in MPC manner, so that the signature can be verified with the child public key.

Beyond that, we don't need hardened/non-hardened keys, not even the tree-like hierarchical structure of them. With such a requirements, many cryptographic features which HD/BIP32 does/doesn't provide are not subject of my question. I'm just wondering:

1. Can private keys be somehow reverse engineered from public keys using our method?
2. Can private keys be somehow reverse engineered if single singing party gets compromised?