Inconsistent BIP32 Derivations

By Rob Witoff, CTO

While testing several popular BIP-32 HD key derivation implementations, we recently discovered inconsistencies in the keys they’re supposed to deterministically derive. Further investigation revealed these inconsistencies – while safe – exist across several libraries and were rooted in a(nother!) padding inconsistency.

We’ve spoken with several colleagues that have run into this bug across our industry so we’re sharing our findings here to help other developers better understand the issue and resolutions in downstream libraries.

Background

Hierarchical Deterministic Derivation

To avoid the need to securely generate and track new secrets every time a new public address is needed, the BIP-32 standard defines a common method to deterministically derive a master and many hierarchical child keys from a single secret seed¹.

Given that secret seed, a master secret key can be generated with the following pseudo code²: This also returns a “chain code” which is used as extra entropy shared by child addresses³.

secretSeed := []byte{...}
hmacKey := "Bitcoin seed"
hmac := hmac.sha512(hmacKey, secretSeed)
// Secret 
masterSecretKey := hmac[:32]
masterChainCode := hmac[32:]

A similar algorithm is then used to derive additional child keys from this master key, of which more child keys can be derived at many levels as shown below. Combining these two properties

Deterministic BIP-32 Key Derivation. Credit: [bitcoin/bips]

Mnemonic Seed Codes

Since BIP-32 allows an arbitrary number of keys to be derived from a single seed, that seed becomes a critical root of trust and durably storing that seed is important for the security of a wallet. To make storing that seed easier by humans, they’re often formatted using a BIP-39 compatible mnemonic code. This standard substitutes bytes with recognizable words from a fixed list of 2048 (2¹¹) distinct words representing 11 bits of entropy per word. You can interactively play with BIP-39 mnemonics here, of which a valid code looks like:

name dash bleak force moral disease shine response menu rescue more will

In this scheme, 12 randomly selected words including a 4 bit checksum, gives us 11x12-4=128 bits of entropy, and 24 words with an 8 bit checksum gives us 11x24-8=256 bits of entropy. 256 bits of entropy represents the ~1x1077 possible secret seeds – – comparable to the number of atoms in the known universe. In other words: extremely hard to guess.

Combining BIP-39 mnemonic representations and BIP-32 HD wallets allows millions of cryptocurrency users to simply and securely use many millions of addresses.

Independent Code Paths

Working with critical systems we follow industry best practices like relying on cryptographers for independent audit, but we also look to other industries for inspiration. One industry we’ve learned from is the space industry’s low tolerance for software failure, particularly NASA’s Software Assurance and Safety Standards.

This standard includes a set of questions that are helpful to ask of components in newly designed systems like:

1. “Does the software determine when to perform a critical action?”
2. “Are the software safety-critical controls truly independent?”
3. “Is the software that makes safety-critical decisions fault-tolerant?”

To confidently answer these questions we treat multiple, independent protections as key design principles when prototyping new systems. This extends to multiple people, languages, libraries and implementations to reduce our susceptibility to an obscure fault in one system.

Inconsistent Derivations

Testing Code Paths

When testing multiple bip32 & bip39 code paths in our testsuite, we discovered the following inconsistency across two common libraries, where common golang and rust derivation libraries returned different addresses:

 hd_path:       m/44'/60'
 mnemonic:      name dash bleak force moral disease shine response menu rescue more will
 bins:          [../bin/golang ../bin/rust]
 addresses:     [0xcaF629BA3Eb35B2DA654649105Aa4D456E9fB6bA 0x0ba17e928471c64AaEaf3ABfB3900EF4c27b380D]

That’s not how “deterministic” derivation is supposed to work!

The first heuristic we looked at to get more information on this error was how often the inconsistency was occurring. Was this a rare bitflip or something more common?

After running enough test cases against randomly generated mnemonics, we can see our error rate converge on .39%. This is roughly once every 256 times – also the familiar 2⁸ bits that can be stored in a single byte. Could there be a special byte that randomly causes our derivation to break? Perhaps a leading byte that tends to get dropped?

34900 Cases, 137 Errors for 0.39% Error rate
35000 Cases, 137 Errors for 0.39% Error rate
35100 Cases, 137 Errors for 0.39% Error rate

With a hypothesis that a bad leading byte leads to incorrectly derived addresses and test cases, we extracted the underlying keys that were being derived. Inspecting the secret key hierarchy for our above test case we see:

• Seed:
  • 0x65c8e3ff14f782859d5764111db9e9cbce00539522cf11edbf8613df2f55f60e
• Master Secret
  • 0x5d53771c24fcf518ed3799667063928315d1ec42dceca728e76345ebf3c15d69
• Wallet Secret:
  • 0x001d19d9503c3dce311e8a9d9fefc24f552c4611f2fccd2a2fedf4234ede1766

This looked like our smoking gun: this address derived inconsistently between our tooling had a leading 0x00 byte. Was this being incorrectly truncated? (Spoiler: Yes!). After updating our test harness we could validate that every time a hardened secret had a leading zero, an address was incorrectly derived, suggesting that these bytes might be incorrectly truncated and the source of our inconsistencies.

Upstream Fixes

With our added context, we were able to more easily look for others having similar errors. We quickly discovered the upstream btcsuite/btcutil issue #172 “why not add leading zero bytes to make childkey 32 bytes long”?

First reported in June of 2020, others had noticed that secret keys weren’t being fully padded when leading 0x00’s make them appear to be less than 32 bytes. This was later patched in #182 with a breaking change to btcutil that wisely protects other developers from upgrading and silently breaking. This patch tests for Issue172 affected keys by simply:

func (k *ExtendedKey) IsAffectedByIssue172() bool {
	return len(k.key) < 32
}

Btc utils hasn’t yet issued a new versioned release since this was patched, so developers wishing to correctly derive their addresses will need to manually pin to a more recent commit. With 300+ forks, it’s likely that other collaborators will also want to consider an upgrade (or maintenance) path for the 1/256 keys they’ve already derived that may also be susceptible to issue 172.

Further downstream users of libs derived from go-ethereum-hd-wallet like go-bip32 can address this by setting the GO_ETHEREUM_HDWALLET_FIX_ISSUE_179 environment variable or directly in code with the fixes added here:

// This works as it did before.
account, err := wallet.Derive(path, false)

// This derives correctly
os.Setenv(issue179FixEnvar, "1")
account, err = wallet.Derive(path, false)

// This also derives correctly
wallet.SetFixIssue172(true)
account, err = wallet.Derive(path, false)

Takeaways

As the first rule of cryptosystems continues to be not implementing your own cryptography, we’re excited to see safe, but confusing edge cases slowly working their way out of the mature foundations that much of our industry is built on. Those affected by this bug should explore the discussions in btcutil or go-etherum-hdwallet to find an upgrade path that doesn’t break access to keys that have already been derived inconsistent with the bip specification – which is in the process of being updated with new test cases to help protect against this.

Finally, prudent implementers should continue to rigorously test their implementations with multiple code paths and aggressively eliminate human and technical single points of failure at every level.