Proposal: Base58 encoded HD Wallet root key with optional encryption

[riplin]

I'm having trouble seeing any value whatsoever in wallet encryption.

Given the amount of computing power available to attackers (botnets, GPU mining farms, etc), you'd need to use scrypt parameters so onerous (multiple days on a regular PC) that there would be a significant chance of a single-bit error occurring during the calculations.

It's an offline wallet for one, so most of the security comes from the fact that it's pretty hard to steal. Second, it's the last line of defence. See my comment above about the time it takes to crack even a 5 character password. It's pretty significant. And lastly, what are the chances that 1: someone breaks into your house. 2: he finds your paper wallet, 3: he knows what it is, 4: he has a bot net / gpu mining farm to brute force it.

[jspilman]

Given the amount of computing power available to attackers (botnets, GPU mining farms, etc), you'd need to use scrypt parameters so onerous (multiple days on a regular PC) that there would be a significant chance of a single-bit error occurring during the calculations.

The cost of breaking the password is based on the strength of the password AND the strength of the KDF. If the password is 'password', nothing will save you. If your password is random 14 character case-sensitive alphanumeric (80 bit), your KDF can even be a single round of SHA512, and it would take the entire BTC network 63 years at the current hashrate (300,000GH/s) to break it.

If the password is 9 random lowercase alphanumeric, that's 46-bits of entropy, or about 50 trillion guesses to decrypt. If you were using scrypt/10-1-1 (LTC) and you had the whole LTC mining network (24GH/s) at your disposal, you could bust through that in 30 minutes. scrypt/18-16-16 however would reduce 24GH/s *well below* 24MH/s for the same network, meaning now the entire network would take 30,000 minutes (20 days) to decrypt the file, which is plenty of time to move funds after your house is broken into and your encrypted paper wallet is stolen.  (Yes, that assumes you know your house was broken in the first place.)  A single iteration of scrypt/18-16-16 takes less than a second on my i7, it's quite manageable.

Now if Satoshi put 1,000,000 BTC into an password-based encrypted wallet and published it on the internet, and promised not to move the funds for exactly 5 years, with a random 12 character case-sensitive alphanumeric (71 bits of entropy) and scrypt/18-16-16 KDF, actually, I think those bitcoin would be pretty damn safe. The cost to decrypt is reasonably in-line with the value of the coins themselves.

TL;DR the point is to increase the cost to steal the funds. The tradeoff is increased risk of losing funds through forgetting the password.  There's no free lunch, but some people will chose to encrypt their paper wallets, and in that case, it would be nice if there was a standard agreed-upon way to do it.

[riplin]

Ok, point taken.

I think I've found a nice way to have multiple encryption parameters, preserving the 'ws' prefix and be backwards compatible with the current test vectors.


128 bit seed:

prefix 0x14D60D : scrypt 14, 8, 8
prefix 0x14D60E : ...
prefix 0x14D60F : ...
prefix 0x14D610 : ...
prefix 0x14D611 : ...
...


256 bit seed:
prefix 0x263AA2 : scrypt 14, 8, 8
prefix 0x263AA3 : ...
prefix 0x263AA4 : ...
prefix 0x263AA5 : ...
prefix 0x263AA6 : ...
...


512 bit seed:
prefix 0x023804 : scrypt 14, 8, 8
prefix 0x023805 : ...
prefix 0x023806 : ...
prefix 0x023807 : ...
prefix 0x023808 : ...
...

And more can obviously be added.

So now it's a simple matter of defining a bunch.

[riplin]

Added user selectable KDF + parameters, encoded in the prefix.

[gmaxwell]

Hm. Why are such weak KDFs supported?  Considering that you can now obtain specialized crackers for bc.i wallets that do ~10m passwords per second on a gpu, I'm a little more concerned about the systemic risk of weak KDFs than I was before.

[riplin]

Although I agree that the scrypt 2¹⁴/8/8 KDF isn't very strong, consider that using a 10 character password with upper, lower, numbers and special chars (say 72 different characters) is still going to take you over 5,935 years on average to crack at 10M hashes per second. And that's ignoring the AES / EC public key generation / double SHA256 part that you need to do to verify if it's correct.

The main reason it's in there is for mobile. The scrypt 2¹⁶/16/16 is probably not even going to run on a mobile device and my laptop (rmbp) has trouble running scrypt 2¹⁸/16/16 (but that's probably due to the scrypt implementation I'm using).

Currently there are 3 defined KDF's with 29 left to be defined. If you have any suggestions, that would be awesome.

[grau]

Hm. Why are such weak KDFs supported?  Considering that you can now obtain specialized crackers for bc.i wallets that do ~10m passwords per second on a gpu, I'm a little more concerned about the systemic risk of weak KDFs than I was before.

Scrypt on typical Android mobile is hardly able to run with more than 2^14/8/8

Since key birth is added, this became an interesting BIP. I consider supporting it as master backup format for the BeBop wallet.

[gmaxwell]

Although I agree that the scrypt 2¹⁴/8/8 KDF isn't very strong, consider that using a 10 character password with upper, lower, numbers and special chars (say 72 different characters) is still going to take you over 5,935 years on average to crack at 10M hashes per second. And that's ignoring the AES / EC public key generation / double SHA256 part that you need to do to verify if it's correct.

That ignores how people actually use passwords, if you have space to store that much entropy you're not actually far from just putting the whole key there. Typical passwords have much lower entropy than that and can be found with far fewer attempts than you'd expect from a uniform probability model.

That said, I'd actually forgotten how the scrypt memory hardness was effected by the parameters, I thought it was just N*128 bytes, which is hardly memory hard considering script memory/computation trade-offs, but it's actually N*R*128, which is a good improvement here. So I'm a bit less than 8 times less concerned than I was before.

Basically, there is a bit of a moral hazard with supporting an insecure KDF— users are known to use bad keys, and application developers are known to use the most inefficient code possible in JS and then force users to the insecure KDFs, and everyone has to follow along for compatiblity. These are well established behaviors in the bitcoin world. But I think your minimum is probably fine.

Currently there are 3 defined KDF's with 29 left to be defined. If you have any suggestions, that would be awesome.

The obvious thing to use instead of scrypt is cantena since script has data-dependent access patterns that leak key material in contexts where timing or power analysis are risks. Might be interesting to get a recommendation from colin percival.

Some other random questions. Is there a reason base64 was not considered? These keys are all too long for the one click copying and reading applications where base58 is somewhat better for... base 64 is 10% smaller and with the right padding can result in a deterministic length. We decided to go with base64 for signmessage and I don't think we've regretted it.

Is there a reason that the sale is HASH256(Base58Check(RIPEMD160(SHA256(K)))) instead of the simpler HASH256(K)?  This avoids a needless entropy bottleneck, additional computations, and an indirect network binding. If you want to bind the network you could just add a network string: HASH256("BITCOIN"+K)

Is there a reason the date and KDF code is not included in the derivation of the salt e.g. salt = length + prefix + date + HASH256(length + prefix + date + K)[0..3]? (length is 16/32/64 or such).  This alternative construction puts the prefix and date under your authentication code, and also increases the space of possible salt values. (the latter probably not very important, though OS password hardening seems to use 64 bit salts typically, but the former sounds useful and important)

Minor bug, your input seed can be 64 bytes, but the rest of the text assumes 32, e.g. the offsets for the whitening and aes key. This should be clarified.
(As an aside I am happy you whiten the input to the EBC mode cipher).

Should the master generation procedure just reference BIP32?

Has there been no interest from wallet implementers in a possible span parameter: e.g. "this key has addresses assigned out to position X?"

[grau]

Has there been no interest from wallet implementers in a possible span parameter: e.g. "this key has addresses assigned out to position X?"

For sure. I am hoping for this evolving more into a description of the wallet, not just the master key seed. Master key birth is the first step.
The next would be topology of the tree (again with births) from this root and highest address used on the leafs.

[riplin]

That ignores how people actually use passwords, if you have space to store that much entropy you're not actually far from just putting the whole key there. Typical passwords have much lower entropy than that and can be found with far fewer attempts than you'd expect from a uniform probability model.

True. But there's not much we can do in software to protect against bad passwords (other than running the obvious checks). You're storing the master key of an entire wallet. When generating one of these codes, it's probably a good idea to make a big deal out of password strength when asking for it

The obvious thing to use instead of scrypt is cantena since script has data-dependent access patterns that leak key material in contexts where timing or power analysis are risks. Might be interesting to get a recommendation from colin percival.

I'll have a look at this, thanks!

Is there a reason base64 was not considered? These keys are all too long for the one click copying and reading applications where base58 is somewhat better for... base 64 is 10% smaller and with the right padding can result in a deterministic length. We decided to go with base64 for signmessage and I don't think we've regretted it.

This proposal started off as an extension of BIP 0038, which influenced most of the choices, like the initial scrypt 2¹⁴/8/8 KDF and encryption scheme / encoding scheme.

Is there a reason that the salt is HASH256(Base58Check(RIPEMD160(SHA256(K)))) instead of the simpler HASH256(K)?  This avoids a needless entropy bottleneck, additional computations, and an indirect network binding. If you want to bind the network you could just add a network string: HASH256("BITCOIN"+K)

I like the network dependency the way it is, because it's clearly defined how to handle alts.  HASH256("BITCOIN"+K) means that I'd have to define it for all the alts as well, including testnet.

In addition to this, if you now look at the parts needed to verify if a password is correct, you need:

Selected KDF, AES, EC Public key derivation, SHA256+RIPEMD160, HASH256, bigint math to go to string (mod 58), another HASH256. All of this will significantly affect the effectiveness of a GPU based attack.

Is there a reason the date and KDF code is not included in the derivation of the salt e.g. salt = length + prefix + date + HASH256(length + prefix + date + K)[0..3]? (length is 16/32/64 or such).  This alternative construction puts the prefix and date under your authentication code, and also increases the space of possible salt values. (the latter probably not very important, though OS password hardening seems to use 64 bit salts typically, but the former sounds useful and important)

Sounds good, I'll have a look at updating this.

Minor bug, your input seed can be 64 bytes, but the rest of the text assumes 32, e.g. the offsets for the whitening and aes key. This should be clarified.

I'm not sure what you're referring to:

9. Derive a hash H from the passphrase using the selected KDF + parameters. The output length = seed length + 32.
10. The first number of bytes in H, equal to length of seed S are used to xor seed S. Call the result X.
11. Do AES256Encrypt(message = X, key = last 32 bytes of H), call this encrypted_seed.

The 32 mentioned here is the AES key length.

Should the master generation procedure just reference BIP32?

I'll add an explicit mention of this.

Has there been no interest from wallet implementers in a possible span parameter: e.g. "this key has addresses assigned out to position X?"

There has, however, I'm still not entirely convinced I'd want to store a tree structure in the encoding. The point was to make this as compact as possible in order to create a paper wallet out of it.

I guess some form of notation could be added along side it to indicate the tree structure. But even then, I expect the tree structure to grow over time.

[gmaxwell]

I like the network dependency the way it is, because it's clearly defined how to handle alts.  HASH256("BITCOIN"+K) means that I'd have to define it for all the alts as well, including testnet.

Hm. Is an internal network binding really desirable? wouldn't it be preferable to use a prefix character?

Selected KDF, AES, EC Public key derivation, SHA256+RIPEMD160, HASH256, bigint math to go to string (mod 58), another HASH256. All of this will significantly affect the effectiveness of a GPU based attack.

The base58 encode can be done without bitint math, it's just a less obvious implementation. Does make a embedded C implementation more of a pain. You get your attack hardness from your KDF... these other operations make the implementation more complicated... which also may make people more likely to roll their own rather than use your scheme. I would encourage thinking about it some.

I'm not sure what you're referring to:

Sorry, my inability to read. The word 'seed' in the text seems to have given me trouble I keep reading past it. What you're encrypting is a root key. I think I keep thinking it's a salt.

There has, however, I'm still not entirely convinced I'd want to store a tree structure in the encoding. The point was to make this as compact as possible in order to create a paper wallet out of it.
I guess some form of notation could be added along side it to indicate the tree structure. But even then, I expect the tree structure to grow over time.

Yea, I just wanted to see if there was something simple like a depth counter that would satisfy people, serializing a tree would be kind of ugly in a compact format.

[riplin]

I like the network dependency the way it is, because it's clearly defined how to handle alts.  HASH256("BITCOIN"+K) means that I'd have to define it for all the alts as well, including testnet.

Hm. Is an internal network binding really desirable? wouldn't it be preferable to use a prefix character?

The current proposal has 6 prefix values. I guess we could make the alts use new prefixes, but considering that these could be (and if the proposal goes onto the wiki, probably will be) listed on the prefix page (many alts are listed there), this could get out of hand real quick.

Selected KDF, AES, EC Public key derivation, SHA256+RIPEMD160, HASH256, bigint math to go to string (mod 58), another HASH256. All of this will significantly affect the effectiveness of a GPU based attack.

The base58 encode can be done without bitint math, it's just a less obvious implementation. Does make a embedded C implementation more of a pain. You get your attack hardness from your KDF... these other operations make the implementation more complicated... which also may make people more likely to roll their own rather than use your scheme. I would encourage thinking about it some.

All operations performed here are already needed in one way or another (except for AES) in any self respecting Bitcoin client. In the current form, that part is shared with BIP 0038. Although I agree that a HASH256("BITCOIN"+K) is easier, I haven't heard any complaints about code complexity here or in the BIP 0038 thread.

As for people rolling their own solutions, I think that interoperability far outweighs the complexity though.

I'm not sure what you're referring to:

Sorry, my inability to read. The word 'seed' in the text seems to have given me trouble I keep reading past it. What you're encrypting is a root key. I think I keep thinking it's a salt.

I could go through and rename it root key. Far more descriptive.

[riplin]

I've changed the salt to be prefix + date + checksum. I've also renamed it 'root key' instead of 'master seed'.

I contacted the Catena authors and they're currently developing an improved version. They also sent me a copy of their code, but they don't consider it to be a proper reference implementation.

[Jan]

That ignores how people actually use passwords, if you have space to store that much entropy you're not actually far from just putting the whole key there. Typical passwords have much lower entropy than that and can be found with far fewer attempts than you'd expect from a uniform probability model.

True. But there's not much we can do in software to protect against bad passwords (other than running the obvious checks). You're storing the master key of an entire wallet. When generating one of these codes, it's probably a good idea to make a big deal out of password strength when asking for it

End users are notoriously bad at selecting strong passwords (hmm... need a special character, let me put ! at the end). One way to handle this is by letting the software generate a random password using the full key space. This allows you to reason about the combined strength of the KDF and the entropy it works on. Obviously a randomly generated 14 character password is impossible to remember, so this forces the user to put it on paper, which is good.

I would love to see some calculations on the strength of scrypt with selected parameters for various amounts of entropy. The best source I found so far is from a presentation by Colin Percival's (scrypt author): http://www.tarsnap.com/scrypt/scrypt-slides.pdf
His presentation outline the cost of breaking scrypt for various parameters in one year. The interesting part is on page 16-18.
With:

10 characters selected from the 95 printable 7-bit ASCII characters; e.g., “H.*W8Jz&r3”.

which is about 65 bits of entropy.
He estimates that it will cost you:
 $43B to brute force in one year with parameters (N=2^14, r=8, p=1)
 $175T to brute force in one year with parameters (N=2^14, r=8, p=8)

Measuring the cost to brute force is ingenious in a Bitcoin context as it gives normal people an idea about what they are dealing with and the amount of funds they are willing to protect under certain scrypt parameters.

I cannot tell whether his numbers still hold, some time has passed since then. In the meantime we have seen scrypt mining, albeit with pretty small memory requirements (N=2^10, r=1, p=1). Thoughts?

[adam3us]

The main reason it's in there is for mobile. The scrypt 2¹⁶/16/16 is probably not even going to run on a mobile device and my laptop (rmbp) has trouble running scrypt 2¹⁸/16/16 (but that's probably due to the scrypt implementation I'm using).

I pointed this out in another thread, and to Mike Caldwell in relation to BIP 38, but I think people are not aware.

You do not need to do work when you create the key.  Only when you decrypt it.

Instead of k=scrypt(salt=0,iter=65536,mem=1GB,passphrase) you can use random 16-bit salt k=scrypt(salt=16,iter=0,mem=1GB,passphrase) with a salt you securely delete after key generation.  The work is the same and the setup cost trivial for a smart phone.  Obviously its easy to create key stretches you cant undo even with a super computer or the entire bitcoin network, so you have to apply strict sanity checking to the parameter choices.

(As an curiosity aside, to create asymmetric work decryption with symmetric crypto, is an extremely old design, due to Martin Hellman which led to the discover of public key cryptography, practically cryptographic archeology

You can also adjust the difficulty over time, by deleting another bit to adjust for moore's law once a year or so without changing keys and addresses.  You can after the fact harden your KDF.  eg if the bitcoin become worth more, or if you start simple and end up with more holdings relying on it.


I have another KDF approach also based on a blind version of Rivest et al's time-lock puzzle which allows third parties to do the KDF work for you, in zero-knowledge for a fee.  At litecoin prices it allows you to add 44bits to your KDF for a fee of 50c.  (or 40bits for a fee of 3c).  Lower than the bitcoin fee.  That can make grinding even  relatively weak password economically infeasible and litecoin-like networks are probably the most efficient rentable computer on the planet.

It gives GPU miners something to do and allows a smartphone to directly provide massive KDF security.  Your private key, if encrypted, once in the hands of your attacker - be that physical laptop theft, cyber criminals from an online or USB bios attack, law enforcement investigation - *becomes* a brain-wallet.

I encourage people to consider the offloadable KDF approach.  It provides a combined cryptographic/economic defense and level of assurance to brainwallets and stored-wallets that is not feasible otherwise.

Currently there are 3 defined KDF's with 29 left to be defined. If you have any suggestions, that would be awesome.

Have you looked at what bitcoin armory does?  They are using scrypt's romix which is has a memory hard security proof, but tweaked slightly for cpu/memory.

Btw I presume people know that scrypt has TMTO tradeoffs and is was actually not designed to prevent that.

Adam

[gmaxwell]

Some of the concerns about KDF costs could potentially work by making the KDF work delegatable.

Adam3us' blind puzzles are probably a bit too far rocket-science for this BIP, but simply restructuring the encryption like:

Key = HMAC(  KDF(HMAC(passphrase,salt)), passphrase||salt)

This would make it possible for a mobile device to ask a fast computer to do that KDF for it without completely losing all security.  Mike Caldwell had indicated that the ability to delegate was a shortcoming of BIP38 that he'd like to see addressed.

[riplin]

Sorry for the late reply, I was AFK for a while.

gmaxwell,

I'll see what I can do to add support for adding delegatable KDF work.



Adam,

You do not need to do work when you create the key.  Only when you decrypt it.

You need both the encrypted and clear version of the key during generation. The end result contains a partial hash of the root address, so you won't be able to get around doing the work at least once when generating a key.

As for the rest of your proposal, it's a bit above my head. Would gmaxwell's proposal open up the possibility to do what you proposed? If not, what kind of additional changes would you suggest to make it work?

[adam3us]

You do not need to do work when you create the key.  Only when you decrypt it.

You need both the encrypted and clear version of the key during generation. The end result contains a partial hash of the root address, so you won't be able to get around doing the work at least once when generating a key.

You do have the key.  My point is you can do it fast before you delete the salt.  After you delete the salt it becomes hard as you have to search for the salt.

You do not need to do work when you create the key.  Only when you decrypt it.

As for the rest of your proposal, it's a bit above my head. Would gmaxwell's proposal open up the possibility to do what you proposed? If not, what kind of additional changes would you suggest to make it work?

Replying to gmaxwell now I have another idea.  Secure offload with symmetric crypto no blinding.

Adam

[adam3us]

Some of the concerns about KDF costs could potentially work by making the KDF work delegatable.

Adam3us' blind puzzles are probably a bit too far rocket-science for this BIP, but simply restructuring the encryption like:

Key = HMAC(  KDF(HMAC(passphrase,salt)), passphrase||salt)

This would make it possible for a mobile device to ask a fast computer to do that KDF for it without completely losing all security.  Mike Caldwell had indicated that the ability to delegate was a shortcoming of BIP38 that he'd like to see addressed.

But I think you can do it by making 100 KDFs, and add 50 of them together mod n.  Then you shuffle them send all 100 to the network, it does the KDF stretching which is expensive, sends the 100 back to you.  You pull out the 50 that are correct combine and decrypt.

https://bitcointalk.org/index.php?topic=330819.msg3548144#msg3548144

what makes it hard is the network doesnt know which 50 of 100 which is work ~2^128.  There is no closeness metric so you have to brute force.

Adam

[gmaxwell]

I'm not so sure about that.

Your (correct) KDF queries are generated from the password, and perhaps a salt.  Right?

We're assuming that the attacker somehow has your encrypted wallet key. He's trying to guess your password, and he's previously done KDF work for you.

The attacker guesses your password is "bob", now he generates the resulting KDF queries and sees that they match the work you asked him to do. He goes and simulates your full process, looks up his saved kdf results, and can now steal your coin.

The problem there is because the process is deterministic given your password and the wallet seed he can just regenerate the correct queries and ignore the chaff ones. (Unless you have a KDF which has some homomorphism that allows blinding, and I think thats both asking too much of implementors and escaping from the realm of memory hard KDFs that we'd prefer to use)