Topic: BIP39 mnemonics: checksum vs plausible deniability (Read 4319 times)

Thanks for the colourful example gmaxwell.  Damned ninjas and their jtag-enabled throwing stars!


From what I understand: if the ninjas are unable to brute-force the secret passphrase and are unable to extract it from either the suspect or his property then the deniablility that the addresses are associated with the suspect is not further weakened.

However, gmaxwell suggests that it is unreasonable to assume such ineffectiveness on the part of the ninjas and, once the secret master key is revealed, absurd for the suspect (after already admitting to owning the dummy wallet) to claim that the secret wallet is not his.


Nor do I.  The PBKDF2 looks technically sound to me (assuming the choice of a sound hash function) but then again I'm not a cryptographer.  I really don't know what gmaxwell was driving at with the "woefully weak KDF" comment.

Care to explain further?  I am not sure what you mean by nearby key.  The output of PBKDF2 should approximate a random oracle.  The closest thing would be a brute force attack on weak passphrases to search for potential key trees.  I remain skeptical of an attack vector which is faster than a brute force search of passphrases and certainly not one which can be done with a gpu in a second.  So lets make sure we are talking about the same thing.


Let m be a given BIP39 mnemonic and p and p' be two distinct passphrases.  Unique seeds s and s' and produced using BIP-33.  I argue that s' can not be derived without knowing p' even if m and p are known if s' is sufficiently strong to make brute force search infeasible.

s = PBKDF2(m, "mnemonic"+p, HAMC-SHA512, 2048) where s is the derived seed, m is the mnemonic (128 bit to 256 bit random value), and p is the passphrase.

I see nothing in the details which makes it weaker than a hypothetical KDF so lets simplify it to a generic representation as:
s = KDF(m, p) where s is the derived seed, m is a random value with at least 128 bits of entropy and p is a user supplied passphrase

So given two unique passphrases and the same mnemonic we have:
s = KDF(m, p)
s' = KDF(m, p')

Are you saying that s' can be derived knowing m & p and not knowing p' just using a GPU powered laptop?  If not then there is no way to link any child derived keys (BIP32) without knowing p even if m is known.  If there is some vulnerability please show it to me.

Example:

You've got a "deniable" mnemonic written down, with a few bitcents in it.

The 'real' wallet is a word or two changed from what you've written down.

Ninjas bust in your doors and demand your keys. They find the mnemonic and aren't impressed by your cover-- they found your house due to your purchases at their dry cleaning cover operation and their records show you have hundreds of coins and transactions not reflected in the wallet they've found.

They torture you-- as ninjas are known to do-- but somehow you resist the lead pipe cryptanalysis.  Unfortunately for you, they also own a laptop computer with a fast gpu an in a fraction of a second they've found your other wallet just by searching a few billion nearby keys; alternatively they turn on your computer and find the missing word(s) in your swap file (most (if not all) BIP39 implementations have no ability to mlock their memory), or they find it loaded into some 'hardware wallet' and defeat the pitiful physical security with a flick of a jtag enabled throwing star.

Now they have your secret stash, you think: oh well, you're not worse off that if you hadn't used the deniability... But actually:

They tell you the penalty for the anti-ninja sources of funds they find in that wallet is death-- you plead "No, that wallet must be my _evil inlaws_, not mine!" but your claim isn't just implausible, it's absurd. The partial mnemonic is in your handwriting; weakly you protest "I'll tell the ninja overlord that you made me write it!" but there is no chance another randomly selected key maps to a mnemonic that anyone could possibly ever find, so the overlord will know both of those addresses started with the (same) mnemonic and couldn't have been produced the other way around. The first 'cover' one was well linked to your identity-- in your effort to make the cover more plausible you made the (undeniably) linked sibling more undeniable linked to you.

If instead the attempt at deniability were implemented as a difference between two keys and coded bijectively, using keyed permutations instead of hashing, such that for any pair of keys there was some set of words that encoded the difference between them; the story would still be sad (because the ninjas will likely run of of patience before you finish your cryptographic explanation) but perhaps less so-- they really could have picked any two random addresses, computed the linking words between them, and coerced you to write them down; perhaps your plea to the overlord would be heard.

Realistically, the deniability is operational security theater in any case. Virtually no users manage, nor does the software they use really support, operating with the kind of incredible fastidiousness required to sustain any level of real deniability against scrutiny stronger than a bored child. Preventing information leakage is insanely hard, far more so than most give it credit.  I shouldn't complain, stunts like this (and software that encourages it) results in many more coins being lost then they could possibly protect for theft. Everyone elses Bitcoins become more valuable as a result, ... hurray, I guess?   ::shrugs:: I protest a bit just because it's weird to see something called 'deniable' when its so undeniably linked to its sibling once you do know all of them.

Effectively BIP39 is a thinly veiled brainwallet scheme with a woefully weak KDF. It's prone to misuse, and when misused it picks up all the bad properties you might expect it to pick up.

Agreed.  My current understanding of PBKDF2 is that there's a near symmetry between the functions of the mnemonic and of the passphrase.  The main difference seems to be with intent, where the mnemonic is expected to contain more entropy while the passphrase is easier to remember.

At the time I was referring to the use of "plausible deniability" in BIP0039 (which focuses only on the passphrase) and certainly could have made that clearer.


I didn't understand this but it seems interesting.  Could you elaborate please?

It seems to me that, without both the mnemonic and the password, any attempt to prove a link between a mnemonic (resp. password) and a seed (perhaps a BIP0032 master key) would practically require brute-forcing the password (resp. mnemonic).  In both cases I believe that, as DeathAndTaxes suggests, one or several dummy keys, potentially with some activity, could be accommodated and even fully revealed without weakening this brute-forcing requirement.

That deniability is less strong than you (and others) think.

Assume I do recover the full mnemonic (e.g. from sniffing if off your computer). Because the mapping is one way (it's not an efficiently computable bijection) I can trivially prove that all the private keys that I do happen to know of are all linked to (and derived from) the same mnemonic (fragment).

Well it does to the mnemonic as well because more than one wallet (master rootkey) can be produced from a single mnemonic depending on which password (if any) is used.

Say you find the mnemonic "usage satoshi manage perfect solar peanut rebel few cruise cable antenna project" in my possession and demand the proper passphrase to produce the master rootkey.  I give you the password of "password" which when used with the mnemonic above produces the following key:
xprv9s21ZrQH143K2qeQTSzy5B6E4FMW5tm8q1a7eGWUg7EEBQ89i1FqtaBcB2fhpmewu3ks6hB9vVn X2WkupU41mVVbcJoVRjQRitn3C3SnQiv

Is that my valid wallet?  Or did I just lie to you about the password.  I don't even need to plan this out in advance, any password will produce a valid (and unique) rootkey.  "Ok for real, my passphrase is 'JumpingJackFlash2038' I promise".  Same mnemonic but a different password produces a different master rootkey:
xprv9s21ZrQH143K4bxB5n2vPZZt5A5cUMWj5qR318tdFuofMF4jwuZt4cjTCWqSbBkCS4xn8AoNNc4 K1ctBCrt92y1Z67TuhzL3Xvh1ZDtb1DZ

The denability of any given wallet (master rootkey) is still maintained even if you can link a mnemonic to me.  Now if I give you any random passphrase the wallet is going to be empty.  You can't prove that there is an additional passphrase which produces a different funded wallet but I can add an even stronger level of plausible deniability by creating two wallet from the same mnemonic and fund the first one with a trivial amount of coins.   So in the example above I tell you my passphrase is "password" and it does produce a wallet with a few transactions and a small amount of Bitcoins.  There is no way for you to prove that the passphrase 'JumpingJackFlash2038' will produce a second wallet with even more funded transactions except a brute force attack (so make sure you passwords are secure if you want to maintain deniability).

Yes, the plausible deniability refers to the passphrase, not the mnemonic.

Of note: you could simply use random data in place of the checksum and punch your way through all warnings but I expect that, in most cases, the cons will outweigh the pros.

Ok, got it. Thanks. I misread "passphrase" in the second quote as meaning the mnemonic itself.

mnemonic != passphrase

the mnemonic has a checksum, and thus is limited in combinations.

the passphrase is a salt to the hash used with the mnemonic, so changing the salt changes the seed of the HD wallet.

Optional plausible deniability.

It's referring to this. You pick an additional passphrase as salt, which any passphrase works.

BIP39 describes how to generate a multi-word phrase and then how to convert it to a seed. It states that phrase is directly hashed into a binary seed, so it gives us plausible deniability ("any phrase can work"), but at the same time the phrase contains the checksum, so I can't provide "any" phrase. If I tell some guys another phrase that happens to have a broken checksum, that will easily notice that. Should I understand that "plausible deniability" applies only to a set of all "valid" phrases, i.e. those with valid checksum? Maybe this should be clarified better in the BIP.



https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki