BIP 32 seed resulting in an invalid private key

Question

everyone.

For my final year project, I'm developing some Bitcoin/Bitcoin related technologies (BIP32, BIP 38, BIP39, Bas58Check encoding/decoding, etc) in pure Node.js (using only native libraries, such as 'crypto').

After writing the module dealing with BIP32 wallet generation, I wrote a bunch of tests trying to cover 100% of statements/branches/functions/lines, but there's one scenario I can't seem to reproduce, due to it being very unlikely to stumble upon.

Given a random seed, you apply HMAC-SHA512 to get the master extended private key. In it, there is a private key, which can be invalid if equal to 0x0000000000000000000000000000000000000000000000000000000000000000 or greater than 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140.

Have you guys seen any seed which generates an invalid private key? I looked through the internet for such known value and could not find it.

The same can happen when generating children private keys. Is there any known parent private key + parent chain code + index resulting in an invalid private key?

Thanks a ton!

Answer 1

Sounds like a cool project!

Given a random seed, you apply HMAC-SHA512 to get the master extended private key. In it, there is a private key, which can be invalid if equal to 0x0000000000000000000000000000000000000000000000000000000000000000 or greater than 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140.

That's mostly right. It should error if I_L is greater than the curve order, (that's the number you have there) or if the child key (k_i) is 0. (https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#private-parent-key--private-child-key)

Have you guys seen any seed which generates an invalid private key? I looked through the internet for such known value and could not find it.

It would be really surprising if someone knew a seed that would do that. The two conditions happen about 1 in every 2^127 times, and about 1 in every 2^256 times, respectively. If SHA512 is a secure hash function, it should take about 2^127 runs of it to find a seed that fails.

To be clear, such a seed exists, but we don't know what it is.

While researching this, I found this error message in the pycoin library. It shows up if either of the conditions you mentioned happen.

_SUBKEY_VALIDATION_LOG_ERR_FMT = """
BUY A LOTTO TICKET RIGHT NOW! (And consider giving up your wallet to
science!)

You have stumbled across an astronomically unlikely scenario. Your HD
wallet contains an invalid subkey. Having access to this information would
be incredibly valuable to the Bitcoin development community.

If you are inclined to help, please make sure to back up this wallet (or
any outputted information) onto a USB drive and e-mail "Richard Kiss"
<[email protected]> or "Matt Bogosian" <[email protected]> for
instructions on how best to donate it without losing your bitcoins.

WARNING: DO NOT SEND ANY WALLET INFORMATION UNLESS YOU WANT TO LOSE ALL
THE BITCOINS IT CONTAINS.
""".strip()

Sound advice. Winning the lottery is a mere 1 in 2^28 chance.