Author

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

Michael_S

sr. member

Activity: 278

Merit: 251

Bitcoin-Note-and-Voucher-Printing-Empowerer

I didn't really understand in what way the plausible deniability is broken in BIP39 when using same mnemonics with different optional passwords.

So let's check/proove by example to see if I got this right, to see if the plausible deniability of BIP39 is really broken:

Via "http://bip32jp.github.io/english/" and "https://dcpos.github.io/bip39/" I created the following HD wallets:

HD Wallet 1 (let's assume this is what the "Ninjas" found out):

Mnemonics: secret blame broken hundred bid express effort snow bike category wonder wrist
Optional password: (i.e. no password at all!)

The first five addresses and key pairs are:

Code:

0     1HVYYLvskm9b9BnMkFvFwNgwAEPC5pQ8pm        KxPoX3MdNA2MKdERJAdRwQpX1LdM6DuHKmUeTLTKxUFSio1n7UKV
      Pub.Key: 0341931E073869EE4DFC769D14D35A1451E80CF3B44F1BB01EAB0FC970A5E6CC6D

1     14x3Z5HV4e6VfGMpJTENkP4abyQz1HqCrN        L2kD3HXTfL7F6nkUAxwX8hWeFMx7ssbpHijYVNJFq18xyfe9ABm3
      Pub.Key: 02BF3FD42086E624FC1684F99B35CC16BD02BF1E70AEC34BD017D8A7D266D789B3

2     14X2ypUStaG8nYsWaQHTsGhXrMVkieQtjG        KwciLYshfsAzLgpd2kJjeZD3tta7Fbwevz6Heayzugmw37P4Eunh
      Pub.Key: 03F1B8473B5781940E3B1036F572A64C7E6B4718D1A33FE2DD1A0CC6292335A0D0

3     1Nn46XR98hDWaX6mqeqdcQcyBrQPDPNCrN        L4WFgLKPSoCZHLwoSZKv76hAyziCmbACLDyWgXRz9RZc19RBcJMV
      Pub.Key: 023D529949196D46AF39147AF5021ED0DA64BB2C14405F3DBE25CDF94DB8C5D86A

4     12v88JPgLJ2dMKunUySA74hvBTS47FEvHG        KyXYjjTAmu1vW1umNG4FedrBMTqJXu5G4NBdkfbcDRYNCEvLZZXB
      Pub.Key: 029C2CFD4D65D18E9C5FA8E056D66BAB80D6CF933A6E6680B8C2B6BFAC352EC3A5

HD Wallet 2 (let's assume that the "Ninjas" found this out, too):

Mnemonics: secret blame broken hundred bid express effort snow bike category wonder wrist (same as above)
Optional password: simpletestpw

The first five addresses and key pairs are:

Code:

0     1DyP6aGfaev9NBoSZwW2CotiyreoEsDfhm        L4k4mCW4nrrVDu1iVG1a7qwavKfA6w4MDLVKuxqFmabdKFKKthBg
      Pub.Key: 038D24199DFCAE21879C7849FFFCBB5D5DA16416B7B7EB88945ECF53D293238099

1     1GjB3CEDdrbeSxgFJ4DesvgzBidxg6REwv        KxHGxoMuWBFh2pq7mdeprDwYHjyi2UwDuS6vXiUdnAwHCWMmU8Ur
      Pub.Key: 03ED97088DF8B193AD74B81747CE89B21A0535344CDA6E12A3C52AA3038060C8FF

2     12K2vAaSYWMApRuq7HUNszyfuPgzkbvjjc        L5SL1akFNR59cY5Yr3VG6uXheq9sfoc1QYTQ7vS1DEGzzgaDRR2S
      Pub.Key: 02BF29E7C2BC14948E7F4ED6DA6930C80E339AFF2351939FA2A2C2C0A14452E729

3     19FxPD5VqskxYDgqoZDNkftaTZFAPhGuFC        KyJmkryHDFTWWtgR1peGscwx4oJugBcrcqKsoGtpFsNvn716gf5p
      Pub.Key: 02BBF1E25FF57155BA747389AE493ECA019D6275AF6C98459AC3F3F70543E309DB

4     1eC5dJBakJSNjZj8g4SKyyhexoZUTBPSY         L3zgDkNCpqSrVR24AFvVMJmzxna5nJZZSEQe53aYWXiwSZxJtEcd
      Pub.Key: 020D634A935814F574565EA921D711440A6AEF611E594EBD263A5EB33F45CE9149

Now let's assume that there EXISTS a third HD-Wallet with the same mnemonics but yet another, more complicated, password (>>50 quasi-random alpha-numerical characters).
The Ninjas don't know this password and the victim is denying its existence, although the first 5 keys of that HD wallet have already been used in the blockchain, such that their pub keys are published.

The question: Can the "Ninja-attackers" find out that I lied when denying the existence of that wallet?

So I am asking gmaxwell or any other "advocatus attackeris":

Which of the following sequences of 5 public keys is the one that belongs to a HD wallet generated with:

Mnemonics: secret blame broken hundred bid express effort snow bike category wonder wrist (same as above!)
Optional password:

Out of the following 10 lists (A-J) below...

Exactly one list is generated from a BIP39 HD wallet generated with the same mnemonics as above, plus a complicated password. The question is: Which one? (out of A-J)
At least 3 lists are generated from other BIP39 HD Wallets with different mnemonics and with or without optional password.
At least 3 lists are just random independently generated "standalone" keys.

Option A:

Code:

0     1EEdcPQPM1k442qVDrP7LnUVLysAgPdJSY
      Pub.Key: 027E4B1EC307A3B80070A2E2E22657A591D17293D4DE5F29CC8F24F04430181734

1     1D7C9jQNoaHMvMgQSDpAqkBa3e7eaxgoVg
      Pub.Key: 034C75E5BE62DC4FEE402809D34CA30C5292090AED620D52BDDFC8D5C3C7E0022D

2     1QDCbJSdKunDECwVkTA8AeZ9Mt2cA9rowb
      Pub.Key: 02F2F101E432204C4A32DE32E757413E351FE642FDC707184223FBBB5466579C04

3     17SuCFUbV2g83BPthzkmhFod91VeyyYpRM
      Pub.Key: 02A4FB6AFBBB1DF29AB17F9519EEC77E47E7662E8399158C83F7B35501D36ECD83

4     1HHbDh3zif851finurUphR1fF6TcyqatoA
      Pub.Key: 02C82A90DBB6E1DB6CDC2EDCB2081833C7C85D83254167CAA4C46A5D1C5119764E

Option B:

Code:

0     1Fx11oAE7nSzw1vnxtXJjKU5gkQ6qyeAWQ
      Pub.Key: 02FDC70A76434C3A8F44729866F714188E9FA25BCE0A5C93482CDC306CAFF3E4F1

1     15zdQ2wkXntrMKgs7Pkwq7D4sLVdSjJDPr
      Pub.Key: 032BCD23D0CEA5FDFE622080F9C3BF2680F1D7EEAE8FC56DA64FC2ED536B630E53

2     1J81WVVNjfmoxHSqHgKUzv1aW8gwyX4R9E
      Pub.Key: 023680424FEE801DBBD626D5248189D179C67976D2C9934EEDDB8A8B04FE63E192

3     1LrbvPQQ8yiG5SKnsCAVHbnwHkwKw1hURB
      Pub.Key: 024F69025CF3768AFBB28D03AA9CD90D16BD8382AE021B8719809408C36C8A2401

4     1B88w1HNW6cwRmYSRM32HdX7gtQzWJy4Us
      Pub.Key: 0268E345CD29D1D4FAA9652BE0F47B72170D510655552B56AAB2BEFBAE859BC44E

Option C:

Code:

0     1HpXydZyZhjjbbHwjqXe6CbqTxDrpUV6wg
      Pub.Key: 02425F50BA0E0238528F03FE40FA1BA375DB30092739BC8ED48BB3EA917190CAA4

1     19SubykBdAGChGJV7qzractUuHchv2TGV9
      Pub.Key: 039CE488557C3C72A7FFDE7E81314808516AE2CD227E96A60E1A47814E2413C9D5

2     1MSJu8cv1LFJbvXkVmg2GcB95sjJQv8uS7
      Pub.Key: 030EA81265DCF94528D1A3AB0FF28EEC2A6E2E752A8D4E753B05943D6B82398534

3     1MhXzhgwtviqqx4KtFQTu2eoSLjcEJrPFz
      Pub.Key: 026B68C00DC1EDA7886BB42DD859E58F412E5AC7C7FD25BC99C08C47F16B6CC2D4

4     1FbLCfrHLtgwc9iVaMTWCxPjVDogWbMQyY
      Pub.Key: 036EC441E65F573DFC5B2659D3821575C0044E4C489690C36F77CD84DE6F815D97

Option D:

Code:

0     19PQKSYwGiYo25eqFQu2ZEMUQeEaEfhM72
      Pub.Key: 026CB7302696C9CB5EBE1AFDDBFBE15809E544210EDA0C9307D46AE4311A8593CC

1     18UQk41j7DQbnAjSHvghF4XT7xQcB144Bj
      Pub.Key: 03ECCE5D50902B27BFB99E3C1B3A10F5777CC7118025630D18BA20FD0DEA51F688

2     1CuqcG2Bk2UkffM5xGCrLjADaXQtCvzKrm
      Pub.Key: 0396614D44AB0AD96F348CFA7A1B8C04710819A2C80BB506A801CB239D8B9F7632

3     18LbxdoySf7EHJS1NrCb9yo4UrX8RwoZ2t
      Pub.Key: 02BADC6EF32A885CA1A375CF96BC66002DBE881FF3DC2EC345420689F7CCDC5A66

4     1CoiEc8859xJSEH3dHQWqBL6fczkqo4RQb
      Pub.Key: 03A46B6691853F69E8319720B725A17A83BC55136E43195010DF5DF758BC46A655

Option E:

Code:

0     1Ayg5AAubRcJgxEdWUpBKKG5BqMGBoXsct
      Pub.Key: 03355E414BC4247A5E50C4F2678C3780BD3076926BE80371C841B43989FEA1096D

1     12af3bd7x7BcwpnAK4vJT6WvZgFwzFt2rP
      Pub.Key: 038DB17B8890CD4A8049DBD2D3C9BF8307AFD6567714A71F1B22AF7154BB8316FE

2     1EF6zrRSdm94HjdUdRqLCguoMZab7PHyJf
      Pub.Key: 03721B8BBEDDDD18B218466787E2F072A269DA6D8AD8D181DCB0FFFAD13AF25DDA

3     1EL36j33b4tTUGN5pEBajFttXvM18i9zem
      Pub.Key: 03A633239EE71C05689AAE62BF4C286E4386DB88236A638CD51D9E3E393783AA1A

4     1LYCWdxxrystURtWz9mjnDssomSbkTvkJq
      Pub.Key: 025E77B059394E38F5B44B8FE96FD47F3C9A2A1FA557D3B48F5E58CF30C8008804

Option F:

Code:

0     1Dbgo7M43BmywoBnY1x6MuZkNyiKS3X6uq
      Pub.Key: 029F66217714A8AA2CF5493F9B52898EAAA19466CD70CB390032FE2D4DB2158FD1

1     16uSekTBuMrYavo9iQiJV1MNeay8H3UarH
      Pub.Key: 033A58073D43870A2F112CCDE2ECCDD19F55B90A8B885ACDD60242E773C29707CD

2     1EmGFtfUeQNfNb3EnaVLGAjP6bshimghXy
      Pub.Key: 03A2938B76D31C594E3526868F72BD18FFCEC588234156E4DF7B4593A843767A77

3     1PJyhCszxcN8gV8xRvEiVogQUjJhA3Ji4F
      Pub.Key: 024044CBA5BB113669B7350C8FD41691F8E9F26F6EDFFB1E2C4A7416E23D2EB2AF

4     19jxSLZCUeG5u65baNtAEbTqjtuDP1NvQo
      Pub.Key: 02C278BF4DB75E52019B7EA5FEAF1C541EAFEB87605BD1200F2ECE77C4DF552E3F

Option G:

Code:

0     1FdZxbjc9QaFKgSPLQCu5QfSRWVhSW4ATA
      Pub.Key: 039735DB6B669EF85E0F8883E97C7EEFE5244679CF1B793117050EBA47608ADAD4

1     1BqpuGvqsSBHa5pvsuefxsFQnqXZUH5B4f
      Pub.Key: 03C13515B42DD13CFD5670CF82674AE0299FB01E900A9038E41E2146F73B8395B2

2     13Z8MgJ4bcCzeaK2j5Enezr92CjFgFaNcw
      Pub.Key: 031E2F6B238F26826505CD2407FDAD9BE6B84359A47DA6954A70F78F0A7C5371E3

3     1MyaVy9CciMyMc1KSUCLJfxQUR5WFZYKjD
      Pub.Key: 02FECDED98734080F40042920C6C945ACD91832A3095EDAC78427549B8EA3134D2

4     1EpzR2feGgyweejJWoPeERcbf3jCb3LBDt
      Pub.Key: 02E968FCB36A23C9AE61E789EB57720F610E642C65BB174D7A6994E2456A9DCFD9

Option H:

Code:

0     1AJbwWp64eoPVbtA3S2UG9t4g9h2pLPnqq
      Pub.Key: 02240C4D5E91E8A161CAA4C92139E1D037DCBEB800DF3C6913FB2798EF291E9735

1     19cdF1u9GdgrJUshJTCVvgdvaeathwTaHx
      Pub.Key: 0331A6EBAE0279ED545A24FCDDDAF28BB59FB505C6D6E7E4B34038C838473625C8

2     1BFvirWvd7e2zVNR2pQeyQrFZjquK95xav
      Pub.Key: 02E6E6AB43B08EB0E244EE043F49DBFE1AB21D174396C8AF6F058216F866BDCEAC

3     1NDQbzuYLrkbKSV6r1gNTWQkcBoAeTDoDU
      Pub.Key: 02184CE4C6591A1BADBA9676E325DA3DE76A14CF9A8172A11BE9B5259CC2B8E736

4     1Cnf8NaHDnbYjMeE4TxvDF61DANRvUNJoR
      Pub.Key: 030DE58B172B08A89AEA7C0F7F1380205F2557CA82EB50D271C82676C108107760

Option I:

Code:

0     1CJN29dzkxm9rRm2aGAaQkrXHWyv5ZXFZp
      Pub.Key: 02C4234923632972E51297A9A8333F44FEE1D7A0B51A3C5EE8BF9D8EC497BE55D8

1     19jJ5kTXwmKR15Dg2zb2BtUgRX42uL5Y9Z
      Pub.Key: 033C17C742C8E1164C8654A8B485C046D13F8FD20B66F6E08E17A94187D379F89F

2     1PRwoPu9NyZyHy1M1HySmSjWhWnHV3Q3GS
      Pub.Key: 03D5508D6CF212C43BD1581417D399C0373C1DDAE0BCF7A98AC5114FFB35F0D5AE

3     1HCjrSnPcEy1PXFX7sa9QPXTyQF5KJTs3A
      Pub.Key: 0323D2D6EC89F30401B569AA1684F2F2E0251F4EC2CD135351C2124D33C07C8C87

4     18oJDyHNvdmN4g9x84rnv5e4b5Qg3769QR
      Pub.Key: 02939A94E558B1F40E2415D2F6BB019BD349D6E5B869A4A9CDF7D851025B614945

Option J:

Code:

0     16cAHfhHD3txXhLaQPDktig9oy56kDcPEv
      Pub.Key: 034F4A5B215077512A91C05AF8AEB787ECAC586A5E05E60ED121709AC224DF5691

1     1JAFeaKgKiTMKf6eDMFyTdhWsKFDSdjxEj
      Pub.Key: 03E7853E8F5FE607410C3DF43ABF71050C2ED8C16B1FBC1BA90D93C4EF6681F0D3

2     1K746TgpUHNbxxAd1EwKMh2SBMBMaoqG4r
      Pub.Key: 02DE4A2C0A46505D99B86EE41EFDA6DDB2731E5821119C12414C7EDE1C7DCD305B

3     1Gn8torjmDdtXx8DZMpnuYBXZWotAwwq6y
      Pub.Key: 031B81A9B99EA06900A8E3530A8732F77ACE30E916733FDFEEDDAF3BD80C509CE7

4     1NQYJ5ZaJZwVn1KkPcdye4Ytu4xYYRkFYL
      Pub.Key: 03BEDECD9AC2916BE4E6012E2936901B1CC0F4A4D44F658757E10140CB75E54FDA

Now I am very curious: Can you tell, which of the public key sequences A-J above is derived from the same mnemonics HD wallet as above (plus a different password)?

If yes, you have proven by example that the plausible deniability of "BIP39+password" is in fact attackable.

Otherwise, it yet needs to be proven - or I completely missed something.

Carlton Banks

legendary

Activity: 3430

Merit: 3080

Quote from: gmaxwell on March 27, 2015, 10:09:00 PM

Stated another way; Absent the brainwallet anti-feature it's possible to have a scheme where a mnemonic exists and is easily computable for any combination of password and private key, and in such a scheme the existence of a mnemonic, password, and pair of keys does not automatically undeniably prove their linkage. You can't have that in a scheme which is designed to not need any persistent storage, however.

So you're saying BIP39 was designed around the capabilities of the hardware that the authors of BIP39 knew they would be implementing it with? Undecided

Seems a little, well, I'll say unambitious, as surely they must have considered the possibility of creating a more advanced device that could make use of a more extensible spec? What then, a new BIP, designed only around the new hardware?

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote from: DeathAndTaxes on March 27, 2015, 09:51:51 PM

Which has nothing to do with the claimed lack of deniability.

Are you having a bad day? Your message seems needlessly antagonistic. (Edit: Ah you edited your post. ... OKAY, yea, tone can be hard to convey.)

That particular flaw is only somewhat related to deniability, although it's not unrelated. Please refer to the prior conversion, I remarked that the specification was largely designed as a brainwallet scheme as one of the general negatives against it. You claimed this was inaccurate, assuming a particular model of use which is intentionally not mandatory, I clarified.

Say there exist two Bitcoin Core wallets encrypted with the same passphrase. Can anyone use their keys to prove that they are linked? _No_. Any existing wallet you have the private keys for can be encrypted with any passphrase. There is no linkage created by using a particular storage scheme. Even to whatever extent that someone way convinced you were the owner of both because they personally found you in possession of two wallet files and the key,that proof isn't transferable-- they could have fabricated that evidence themselves.

Now say there exist two BIP39 wallets sharing a mnemonic or sharing a password. Can anyone use their keys and the mnemonic data to prove that they are linked? Yes. Because BIP39 generates a key using a one way function instead of encrypting a uniform value with (a requirement for working with short user generated strings), all usage of the same data will be linked. It may be surprising to people that using this facility (which, at best, only protects against fringe threats of the sort that one probably ought not worry about) can leave them more exposed to other fringe threats. It could be called 'denyable' relative to a single wallet for everything, but it's very much less denyable than two totally separate wallets, or two wallets encrypted with the same passphrase. Likewise, its not possible to rotate your passphrase if you're concerned that it might have leaked... not without expiring all the keys (for which no facility really exists in the Bitcoin space if you've given any of those keys out).

The actual scheme here prevents the non-linkable usage even when used perfectly, because it's not possible to take a random unrelated private key and convert it into a mnemonic in this scheme; so the bad use by people actually does have an effect on everyone else. (Except by not using the 'deniability' feature at all and just keeping two totally separate wallets)

Stated another way; Absent the brainwallet anti-feature it's possible to have a scheme where a mnemonic exists and is easily computable for any combination of password and private key, and in such a scheme the existence of a mnemonic, password, and pair of keys does not automatically undeniably prove their linkage. You can't have that in a scheme which is designed to not need any persistent storage, however. Probably not a big deal, but enough that I think its a bit sad and ironic to see people use something to gain the 'feature' of denyability when they would be better off not using it; the feature should probably be called "multiple wallets with less written down", which may well be interesting to people-- but probably an entirely non-overlapping set of people.

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: gmaxwell on March 27, 2015, 09:40:07 PM

The lack of checksum enforcement on the mnemonic means that many people directly use the 'mnemonic' as a "brainwallet".

Which has what to do with the claimed lack of deniability? So some people may choose to misuse the proposal that doesn't weaken the security of those who use it as proposed (random value encoded as mnemonic plus optional passphrase with deniability).

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: teukon on March 27, 2015, 05:54:02 PM

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.

Then there is no such thing as deniable cryptography under any circumstance. The definition of what is deniable has been stretched to a point where no possible cryptographic system can fit it and thus there is no point in either using the term. I would hope you can see that if you graphed all scenarios involving deniability at least some of them would fall on the spectrum short of torture.

Honestly if you suspect you will be tortured in the near future you should NOT use deniable cryptography. Why? because it is deniable. Say you give up the sacrifice key but they torture you. Maybe now you aren't holding out to protect the key but the fact that it is very likely they will kill you once they get it. Eventually you crack though and give them the second key. Bad news for you is that one of the torturers turns to the other one and says "what if there is a third key". Now there is no third key but you can't prove that there isn't. Under torture you may swear there is no third key but of course you would say that. So with no way to provide what they want and no way to prove you don't have what they want you are going to die a very slow and painful death.

No deniable system can prevent compromise due to a weak key or disclosure of key by force. The first is a limitation of any cryptographic system and the second isn't even a cryptographic problem. It is like saying locks on your door aren't useful because I could always torture you until you open it.

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote from: DeathAndTaxes on March 27, 2015, 09:36:46 PM

The comparison to brainwallet is inaccurate. Would you call bitcoin core's encrypted wallet a brainwallet? Of course not unless you stretch the definition to the point of being silly.

You misunderstand. The lack of checksum enforcement on the mnemonic means that many people directly use the 'mnemonic' as a "brainwallet". The suggested uniform mnemonic encoding approach is completely non-normative. (This was an intentional design feature, and at one point a draft of the BIP basically advocated the usage; this was a quite controversial proposal, if you may note some of its former authors even had their names removed from it due to disputes about the construction; the state of the BIP was as far as the community was able to push the remaining authors away from that kind of dangerous construction; but its still possible to use it that way and many people do).

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: gmaxwell on March 27, 2015, 07:10:42 PM

Part of it is because the application space of BIP39 is unclear. If the keys are chosen securely then there is no gain from having a KDF (and no real harm in having a weak one, except for code complexity). If people use it like a brainwallet then given what we know about how users choose "random secrets" then the KDF is seriously inadequate; considering the infrequency of use and the huge attacker advantages (precomputation because brainwallet schemes cannot be effectively salted, and hardware advantages) you'd likely want something that takes several seconds on the best hardware the user has access to.

It isn't random mnemonic OR passphrase it is random mnemonic AND (optional) passphrase. The comparison to brainwallet is inaccurate. Would you call bitcoin core's encrypted wallet a brainwallet? Of course not unless you stretch the definition to the point of being silly. You need the wallet.dat PLUS the (optional) passphrase. Here you need the mnemonic PLUS the (optional) passphrase. Precomputation isn't possible in either scenario.

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote from: teukon on March 27, 2015, 05:54:02 PM

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.

Just so.

Quote from: DeathAndTaxes on March 27, 2015, 11:44:05 AM

I see nothing in the details which makes it weaker than a hypothetical KDF...

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.

The intensity of the PBKDF2 at 2048 iterations is almost completely ineffectual, it's likely not worth the code/implementation complexity.

For comparison, on my laptop bitcoin core chooses about 200,000 iterations for its wallet encryption (it dynamically picks a number that takes 100ms to decode)-- and it only uses one core (if we redo wallet encryption in a new format we'll be sure to fix that).

Part of it is because the application space of BIP39 is unclear. If the keys are chosen securely then there is no gain from having a KDF (and no real harm in having a weak one, except for code complexity). If people use it like a brainwallet then given what we know about how users choose "random secrets" then the KDF is seriously inadequate; considering the infrequency of use and the huge attacker advantages (precomputation because brainwallet schemes cannot be effectively salted, and hardware advantages) you'd likely want something that takes several seconds on the best hardware the user has access to.

teukon

legendary

Activity: 1246

Merit: 1011

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

Quote from: DeathAndTaxes on March 27, 2015, 11:44:05 AM

Quote from: gmaxwell on March 27, 2015, 04:55:33 AM

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;

Quote from: DeathAndTaxes on March 27, 2015, 11:44:05 AM

I see nothing in the details which makes it weaker than a hypothetical KDF...

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: gmaxwell on March 27, 2015, 04:55:33 AM

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;

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.

gmaxwell

staff

Activity: 4284

Merit: 8808

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.

teukon

legendary

Activity: 1246

Merit: 1011

Quote from: DeathAndTaxes on March 26, 2015, 06:08:33 PM

Quote from: teukon on October 14, 2014, 06:31:41 PM

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

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.

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.

Quote from: gmaxwell on March 27, 2015, 02:01:04 AM

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).

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.

gmaxwell

staff

Activity: 4284

Merit: 8808

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: teukon on October 14, 2014, 06:31:41 PM

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

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).

teukon

legendary

Activity: 1246

Merit: 1011

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.

oleganza

full member

Activity: 200

Merit: 104

Software design and user experience.

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

dabura667

sr. member

Activity: 475

Merit: 252

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.

instagibbs

member

Activity: 114

Merit: 12

Quote

To create a binary seed from the mnemonic, we use PBKDF2 function with a mnemonic sentence (in UTF-8 NFKD) used as a password and string "mnemonic" + passphrase (again in UTF-8 NFKD) used as a salt.

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

oleganza

full member

Activity: 200

Merit: 104

Software design and user experience.

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.

Quote

First, an initial entropy of ENT bits is generated. A checksum is generated by taking the first (ENT / 32) bits of its SHA256 hash. This checksum is appended to the end of the initial entropy.

Quote

Described method also provides plausible deniability, because every passphrase generates a valid seed (and thus deterministic wallet) but only the correct one will make the desired wallet available.

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