Using HD tree branch for encryption with Curve25519?

[coder5876]

Re HD keys - BIP 32 and beyond
CC @ChristopherA

I've been meaning to use specific branches of an HD tree for encryption using a tool like Minilock that uses Curve25519. My thought was basically to hash a private key from the branch of the HD tree (using the secp256k curve) to create the (32-byte) private key for Curve25519 and use that for encryption. It seems that this should give enough entropy for the encryption key, but are there some subtleties I might be missing?

[peacekeeper]

I'm also interested in this, my issue #13 asks a similar question.

[coder5876]

Yes, good point! My naive method above should work to obtain private keys for encryption (unless it's a bad idea for some reason I'm missing), but it won't give the HD properties for the Curve25519 public keys.

[ChristopherA]

All you should need to do minilock style permits on the secp256k1 curve that Bitcoin uses is to Schnorr Signatures, which have now been implemented in a library from Blockstream.

That being said, the are some interesting ideas of very deep and wide HD paths that Ryan Shea @shea256 has written about in selective disclosure that could be used for other purposes.

[coder5876]

True, I could probably implement the minilock specification using secp256k1, but one of the reasons I prefer to use minilock is that it's been security reviewed and is based on the (also thoroughly reviewed) tweetnacl library for Curve25519.

Agree that the high-entropy HD chain paths by @shea256 are very interesting and might have some cool applications. These were discussed also in issue #15.

[ChristopherA]

I'm told that Blockstream's library has also been significantly security reviewed. Ask them Tuesday.

[ChristopherA]

/cc @gmaxwell & @sipa, what is the security review/audit status of https://github.com/bitcoin/secp256k1, especially as compared to tweetnacl's? There is a common belief that because of the publicity about TweetNacl about its audit that it is more secure, but I'm not sure.

Related, security review/audit status of your extensions in https://github.com/ElementsProject/secp256k1-zkp ?

[coder5876]

@ChristopherA @gmaxwell @sipa I think the main differentiating factor between these two libraries is that (tweet)nacl is directly targeted at encryption (with high-level crypto_box APIs etc) whereas secp256k1 is targeted towards signatures rather than encryption. I guess one could use the secp256k1 library to compute the shared secret and then use that in the xsalsa20-poly1305 symmetric encryption function from the nacl library. I'd rather avoid rolling my own stuff as much as possible though, and in this case the added minilock implementation on top (which in itself is security reviewed) would also need to be reimplemented.

[sipa]

libsecp256k1 is aimed at:

• Cryptography that uses the secp256k1 curve
• Very well tested & verified
• Efficiency
• Hard to use in unsafe ways

The past few months have mostly been focussed on API changes and testing/verification, as Bitcoin Core is planning to switch its signature validation to it. To give an idea of what we're talking about:

• libsecp256k1's unit tests which do (or did) comparison with OpenSSL have led to the discovery of:
  • CVE CVE-2014-3570 (see https://www.openssl.org/news/secadv/20150108.txt): OpenSSL's bignum squaring function was incorrect for a very small number of possible inputs on some platforms.
  • OpenSSL's platform dependency in its ASN.1 parser (see https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-July/009697.html for its effect on Bitcoin).
• Very high branch coverage in units tests, which required extracting a minimally covering set of inputs generated from over a trillion random inputs (by @gmaxwell).
• The low-level field arithmetic code carries (human verifiable) correctness proofs.
• We have code under review (Add sage verification script for the group laws bitcoin-core/secp256k1#302) to formally verify the implemented group laws.
• We have code under review (Add exhaustive test for group functions on a low-order subgroup bitcoin-core/secp256k1#310) that tests correctness by changing the curve equation to make the number of points on it small enough to exhaustively test all inputs.
• A lot more...

libsecp256k1 did originally start as an implementation of just signing/verification, but is currently much more. For example, it does include a fast ECDH implementation (which is a primitive needed for Elliptic Curve based encryption).

[sipa]

Instead of high-entropy HD chain paths, you can just use pay-to-contract derivation (pubkey = base_pubkey + HASH(base_pubkey || entropy) * G). The only reason to use BIP32 is when you need the ability to exhaustively iterate children. If you don't need that, you can avoid its complication.

[coder5876]

@sipa Oh, nice! So if k = HASH(base_pubkey || entropy), then privkey = base_privkey + k. So you can share R = k*G to show your knowledge that pubkey = base_pubkey + R to verify that you own base_pubkey, but if you share privkey with someone then you would also share base_privkey with them which is the desired property. Very slick, thanks for sharing! 😊
CC @shea256

[coder5876]

Or rather: You share knowledge of entropy to prove that you had a pay-to-contract derivation from base_pubkey to pubkey (and hence knowledge of base_privkey). But sharing entropy means sharing k which leads to sharing base_privkey if you share privkey.

[shea256]

@sipa do you know of any libraries that employ this method that I could take a look at?

[shea256]

@sipa never mind, I just ended up making my own library.

Check it out: https://github.com/blockstack/ecdsa-keychain-js

@christianlundkvist @ChristopherA would love your thoughts on this as well.

[tarcieri]

Anyone still interested in this should read this paper:

Ed25519_BIP.pdf

There's also Ristretto, which would provide for a simpler implementation of a BIP32-like protocol on top of Curve25519 libraries than what's in the above paper:

https://ristretto.group/