Solana: Ed25519 BIP32

[t-nelson]

We need a BIP32esque deterministic key derivation mechanism. This is tricky due to Ed25519's non-prime cofactor.

Notes on Ed25519 BIP32 quirks:

• https://datatracker.ietf.org/meeting/interim-2017-cfrg-01/materials/slides-interim-2017-cfrg-01-sessa-bip32-ed25519
• https://ostif.org/the-ostif-and-quarkslab-audit-of-monero-bulletproofs-is-complete-critical-bug-patched/
• https://jonasnick.github.io/blog/2017/05/23/exploiting-low-order-generators-in-one-time-ring-signatures/
• https://forum.web3.foundation/t/key-recovery-attack-on-bip32-ed25519/44

Potential starting point for a Rust implementation. Seems woefully light on tests

• https://crates.io/crates/ed25519-bip32

[garious]

cc: #5246

[danpaul000]

@t-nelson Is this task really a QA issue, or is it simply a new feature? Perhaps we should have a separate QA issue tracking its testing? How time sensitive is this issue?

[garious]

Just acknowledging the "Ed25519's non-prime cofactor" concern is time sensitive. The implementation can fall under another ticket.

[danpaul000]

So is there an action item that needs to be completed for this task, if no implementation? Do we need to more publicly acknowledge the non-prime cofactor issue?

[garious]

Yeah, an HD wallet decision that's known to be not vulnerable to that attack.

Maybe QA isn't the right place for this, but if we do this right, there's QA work we don't have to do.

[t-nelson]

I'd say this is a feature request with a potential QA action item depending on implementation.

Agreed with Greg. If we can find a BIP32 crate that supports Ed25519 and has sufficient test coverage for the non-prime cofactor quirks, that'd be ideal.

[t-nelson]

cc/ @rob-solana

[rob-solana]

Is this another starting point?
https://ristretto.group/
https://crates.io/crates/bip32
This is the 0.0.0 crate to which I referred.

[t-nelson]

Potentially. The code is MIA though 🤕

[tarcieri]

My personal recommendation would be to use Ristretto to key new systems if possible (or failing that, just stick with secp256k1 or another prime order curve). I say this as someone playing around with Ed25519 hierarchical derivation schemes around the same time BIP32 was being formulated (please don't use the linked scheme, it's broken due to repeated "clamping").

If you really want to use Ed25519, there are a number of different incompatible schemes for hierarchical key derivation, none of which I can confidently recommend and all of which I find quite messy. The main ones I'm aware of are Tor's Next Generation Hidden Service Keys, SLIP-0010, and Dmitry Khovratovich's "BIP32-Ed25519". I'd suggest reading Jeff Burdges' writeup on them as they all have issues.

I'd still like to write the bip32 crate, with the goal of implementing the original BIP32 for secp256k1 in terms of a PrimeOrderGroup trait, and then swap out secp256k1 for another prime order group: Ristretto255. I'd recommend using Ristretto for new designs if it meets your needs: since it's a prime order group, it eliminates all of the subgroup complexities and related attacks, and allows for a derivation protocol which is identical to BIP32 save for the group it operates over, as opposed to a FrankenBIP32 with a lot of added complexity around ensuring derived keys are in the same subgroup.

[t-nelson]

@tarcieri Thanks so much for taking the time out to reply here! It looks like I have some evening reading to do

[jstarry]

Thanks for the recommendations @tarcieri, they are very much appreciated!

[jstarry]

After quite a bit of reading, I'm still unable to give a solid proposition on how to move forward here but would like to share what I've learned.

As @t-nelson pointed out, Ed25519 is not compatible with BIP32 due to its small cofactor and also due to its "bit clamping" _(used to prevent attacks: 1, 2)_ as discussed in these threads:
https://moderncrypto.org/mail-archive/curves/2017/000858.html
https://moderncrypto.org/mail-archive/curves/2017/000866.html

A number of work arounds have been implemented to enable BIP 32 for Ed25519. But they are not compatible with each other as mentioned by @tarcieri. This has certainly caused a fair bit of confusion in the monero project for example. If Solana chooses a work-around, we should be clear on one implementation to prevent UX issues.

The 2 most common work arounds are:

1. BIP32-Ed25519
   
   
   
   • Used by Cardano / Tezos
   
   
   • Existing Ledger / Trezor hardware wallet support
   
   
   • Supports soft/hardened key derivation
   
   
   • Prone to key recovery attack as already mentioned by @t-nelson. The attack assumes a mis-implementation detail where a wallet developer fails to limit the max depth of the hierarchy.
   
   
2. SLIP-0010
   
   
   
   • Used by Stellar
   
   
   • Existing Trezor hardware wallet support
   
   
   • Limited to hardened key derivation
   
   

Rust implementations

I have not been able to find Rust implementations of either of the above most common implementations. Here's what I have been able to find:

• https://github.com/w3f/schnorrkel
  
  
  
  • Built for Ristretto support but includes this approach for hard derivation for Ed25519 secret keys
  
  
  • Although the author seems very keen on ripping out Ed25519 key derivation
  
  
• https://github.com/w3f/hd-ed25519
  
  
  
  • Un-finalized and unreleased
  
  
  • Deviates from Ed25519 but compatible with ed25519-daleks implementation
  
  
  • Same author as the above schnorrkel project, he recommends using that project over this one
  
  
• https://github.com/typed-io/rust-ed25519-bip32/ which is active but based on cryptoxide, a fork of the un-audited and abandoned rust-crypto project

Other approaches we could take for BIP32

1. Use secp256k1
   
   
   
   • Obviously well supported and popular choice for BIP32
   
   
2. Use ristretto
   
   
   
   • Very limited wallet support, all I found was polkawallet
   
   
   • Very new, still a draft
   
   
3. Tor's approach
   
   
   
   • Soft / hard key derivation
   
   
   • Ignores Ed25519 clamping
   
   
4. Torsion safe representation
   
   
   
   • Never implemented AFAIK
   
   

Concerns

Changing a HKD scheme after choosing one is likely to be a really big pain. So we should be thoughtful about our decision here.

[t-nelson]

Concerns

Changing a HKD scheme after choosing one is likely to be a really big pain. So we should be thoughtful about our decision here.

Nailed it

[garious]

Remove this from SLP2 Security?

[t-nelson]

✅

[garious]

@CriesofCarrots, fyi