6

Need some help understanding the math regarding why multiple checksums work for mnemonic phrase generation (BIP39).

Let's assume a 12 word passphrase. If we divide the 2048 wordlist into groups of 16 ... exactly 1 word out of 16 word "block" will be a valid checksum for the 11 words selected.

With a 24 word passphrase, 1 word out of every 256 would be a correct checksum.

When generating a phrase by hand... I know that the ENT / 32 bits of the sha-256 hash are appended to the entropy to generate the checksum word.. but this generates one specific word.

So I guess my long-winded question is ... what is the math behind other checksum values being valid? I guess my real question is how is the ENT + CS validated as legitimate?

See this example:

Entropy (128 bits): 11010011 01100100 00000010 01011110 01010011 11101100 01010011 01101110 01101010 01111000 11010010 11011000 10111010 00100011 11101100 11110010

SHA-256 Hash of entropy = 14 c5 8b c9 05 11 5e 08 27 49 61 1e 48 d6 04 c0 2a 70 8c 39 ad 6c dc 0c 91 2f 70 62 c3 24 71 23

First 4 bits of SHA-256 Hash = 1 (hex) Binary = 0001

Generated Recovery Phrase: square cactus nurse pond share rescue prepare bottom suffer speed will tomorrow

another valid phrase (with same entropy but different checksum): square cactus nurse pond share rescue prepare bottom suffer speed will account

Account = 13 (on the BIPS39 wordlist) Subtract 1 since word index starts at 0 = 12 12 to binary = 1100 Hex = C

C (hex) != 1 (hex)

another valid phrase (with same entropy but different checksum): square cactus nurse pond share rescue prepare bottom suffer speed will acoustic

Acoustic = 17 (on the BIPS39 wordlist) Subtract 1 since word index starts at 0 = 16 16 to Binary: 10000 Hex = 10

10 (hex) != 1 (hex)

I guess I'm also confused how these checksums are valid when their values do not equal the first 4 bits of the SHA-256 Hash of ENT? I'm guessing it has to do with how the checksum is validated (and pointing back to my original question)?

4

You aren't actually encoding the same entropy with different checksums. The last word does not encode just the checksum, it also encodes some portion of the original entropy. For a 12 word mnemonic, the last word encodes 7 bits of the original entropy and 4 bits of the checksum.

In your example, the last 7 bits of the original entropy is 1110010. Combined with the 4 bit checksum of 0001, the corresponding word is tomorrow.

In your second phrase, the last bits of the encoded entropy is actually 0000000 which changes the checksum bits to 1100 so you get a different word, account.

In your third phrase, the last bits of the encoded entropy is actually 0000001 which changes the checksum bits to 0000 so you get another word, acoustic.

So in actuality, BIP 39 mnemonics have unique last word because it is a combination of the original entropy with the checksum which is unique. Changing the entropy bits changes the checksum, and changing the checksum invalidates it.


Original answer which is still correct but not applicable to this question.

A careful reading of BIP 39 shows that there are not multiple words which fit the checksum. Rather the BIP is so broad that invalid checksums are allowed and should only be warned against.

In your example, the second phrase is actually invalid. But BIP 39 says that such invalid phrases should be allowed, and so the wallet software will allow it. The checksum is effectively ignored and not checked (which kind of defeats the purpose of a checksum).

5
  • Thanks for this. This is interesting. Edits coming (hit enter too soon)
    – Ryan Ellis
    Feb 1 '18 at 17:03
  • 1
    So really ledger's tool for BIP39 generation, ledgerwallet.com/support/bip39-standalone.html (looks like a copy of Ian's tool) has a technically incorrect implementation. This is because BIP39 states that if an invalid checksum the software should say so. The code at: github.com/bitcoinjs/bip39/blob/master/index.js#L78 Line 76-78 splits the ENT & CS from the binary of mnemonic. Then Line 87 calls the function to generate the checksum from entropy, and compares it to the mnemonic phrase. Line 88 should throw the invalid checksum error, but doesn't. Not sure why
    – Ryan Ellis
    Feb 1 '18 at 17:17
  • I was actually using Ian's BIP39 tool, and not the code referenced above. I'll need to test this other code out. Thanks again!
    – Ryan Ellis
    Feb 1 '18 at 17:25
  • @Andrew Chow Your answer is incorrect. A careful reading of BIP39 shows that his second phrase is totally valid for the first 4 bits of the sha256 of the first eleven words + 7 bits of "acoustic" are equal to the remaining 4 bits of "acoustic". What the BIP39 is referring to when talking about invalid checksums is, well, if the checksum is invalid (as when before mnemonic seeds were used and, say, plain random 256 bits were used). Feb 26 at 3:03
  • @CedricMartin Indeed. This answer was written assuming that the mnemonics actually encoded the same entropy, but they actually do not. I will edit this answer.
    – Andrew Chow
    Feb 26 at 5:11
2

I believe the checked answer is incorrect. However, so are some assumptions in the question. First off, since there are 2048 words, each word encodes eleven bits (not 8). And since 128/11 = 11 remainder 7, the entropy itself encodes the first 11 words and part of the 12th word. Conveniently the 4 bit checksum appended to the remaining 7 bits makes exactly 11 to encode the final word ("tomorrow").

In your example the other wordlists are also valid (and have valid checksums), but they do not have the 128 bits of entropy you wrote, and correspond to different entropy in the last 7 bits from above.

1
  • you're totally right. The upvoted and accepted answer is wrong: Feb 26 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.