[PULL] Wallet Private Key Encryption

[jgarzik]

I think it's pretty measly a defense that would be primarily a PR tool (SEE? WE DO CARE ABOUT SIMPLETON J. USER!) and not an actual security measure.

This is...  60% true

It is bad PR, but it is also the primary current attack vector, because wallet stealing is so easy right now.  The majority of trojans and malware are stupid, and are actively exploiting this.

[just_someguy]

What you are currently doing is concocting a very specific countermeasure against a very narrow implementation of a certain attack vector.
It is futile.

With a reasonable password it completely solves the issue of someone gaining access to a copy of your wallet without access to your machine.
I'd say thats excellent progress.

[Unthinkingbit]

Hi Matt,

Thank you very much for this patch.  I have a suggestion about the number of rounds:

Keys are encrypted with AES-256-CBC through OpenSSL's EVP library. The key is
calculated via EVP_BytesToKey using AES256 with 1000 rounds.

I don't know how many keys are decrypted in your patch or how fast AES-256-CBC is, however given that even a low end CPU can calculate more than 100,000 SHA hashes/second, I suggest that you experiment with increasing the number of rounds to 10,000 or more until bitcoin slows down noticeably.  This would give some extra protection for medium strength passwords.

With a reasonable password it completely solves the issue of someone gaining access to a copy of your wallet without access to your machine.
I'd say thats excellent progress.

I agree with just_someguy, with a strong password this solves the problem of leaving your computer unattended, computer theft and simple malware.  It is an excellent step in the right direction.

[gmaxwell]

In light of the extreme crappyness of the mtgox passwords I think the hardening in the encrypted wallet branch is woefully insufficient. EVP_BytesToKey's 1000 rounds of sha256 is similar in computational complexity to the freebsd MD5 used for mtgox when run without special code on cpus and such tools slice through the mtgox password file like butter.

We already know that GPUs can do hundreds of millions of 2xSHA256 per second.... Having to do 1000 SHA256 to test a password is no big deal.

The salt also appears to be _constant_ unless I'm misreading the patch. Instead it should be per-user and saved in the wallet. Otherwise someone can simply pre-compute a ton of possible wallet keys for use against thousands of stolen wallets.  They could even make a nice wallet rainbow table using the same gpu cluster they originally bought for mining.  I think this is a CERT announcement level weakness and must be urgently fixed regardless of the other points I'm raising here.


I'd suggest instead that it be changed to use

A = scrypt(salt||password, 4 seconds)
key = scrypt(A||password, 10ms)

and simply save A in mlocked memory so that the high delay only happens the first send during a bitcoin session. (the second step could just as easily be BytesToKey if you want... it's just there to make searching memory of long running daemons unprofitable)

(see http://www.tarsnap.com/scrypt/scrypt.pdf and the implementation at http://www.tarsnap.com/scrypt.html)

Considering the mtgox passwords if this isn't done then it will still be _highly_ profitable to write wallet stealing worms unless the strengthening is made very strong.

[passerby]

I think it's pretty measly a defense that would be primarily a PR tool (SEE? WE DO CARE ABOUT SIMPLETON J. USER!) and not an actual security measure.

This is...  60% true

It is bad PR, but it is also the primary current attack vector, because wallet stealing is so easy right now.  The majority of trojans and malware are stupid, and are actively exploiting this.

Well, I didn't say we don't need no  wallet encryption
Just that malware specificallywill rapidly adapt and hoping that encryption will keep it at bay is futile.... Various smash@grab scenarios and other offline attacks are addressed by it splendidly.

What you are currently doing is concocting a very specific countermeasure against a very narrow implementation of a certain attack vector.
It is futile.

With a reasonable password it completely solves the issue of someone gaining access to a copy of your wallet without access to your machine.

You mean evil maid, smash&grab and stuff like that?

Well, yes. But you don't need your encryption to be particularly sophisticated to defeat those (and again, my point was that encryption does not address the issue of malware infections at all, since malware will work around it, not that encryption of wallets is totally meritless , it's good against other things)

[Matt Corallo]

The salt also appears to be _constant_ unless I'm misreading the patch. Instead it should be per-user and saved in the wallet. Otherwise someone can simply pre-compute a ton of possible wallet keys for use against thousands of stolen wallets.  They could even make a nice wallet rainbow table using the same gpu cluster they originally bought for mining.  I think this is a CERT announcement level weakness and must be urgently fixed regardless of the other points I'm raising here.

(see http://www.tarsnap.com/scrypt/scrypt.pdf and the implementation at http://www.tarsnap.com/scrypt.html)

I appreciate your comments, but you've added nothing new to the discussion, if you read back on the previous posts on the pull request, both scrypt and a dynamic salt have been discussed.  Although I might add a dynamic salt if I get around to it, it was agreed that it would be better to stick with OpenSSL's key derivation rather than scrypt, but you can reopen that debate if you wish.

[Gavin Andresen]

RE: making it harder to brute-force:

I have a couple of thoughts.  First, if users choose passwords like 'abc123' or 'password' or any of the other top-1,000 passwords it doesn't matter if we're scrypt'ing; they're toast. I'd rather see work on either giving users feedback on how strong or weak their password is rather than adding a tiny-little-bit-more security by scrypting.

That said, changing the 'ekey' data so that ONLY the 256-bit private key is encrypted should increase security with very little extra code. Consider what you'd have to do to brute-force:

1000 x SHA256(password_text)

Now you have a 256-bit number.  Is it the right private key?  To check:
ECC multiply to get candidate public key
RIPEMD160(SHA256(candidate public key)), and check to see if it matches public key.

Anybody know how easy it is to GPU parallelize ECC multiplies?  A quick google search gives me the impression that is an area of active research.


RE: pre-computing wallet keys:  ??  wallet private keys are 256-bit random numbers.  Am I misunderstanding you gmaxwell?

[Pieter Wuille]

RE: making it harder to brute-force:

I have a couple of thoughts.  First, if users choose passwords like 'abc123' or 'password' or any of the other top-1,000 passwords it doesn't matter if we're scrypt'ing; they're toast. I'd rather see work on either giving users feedback on how strong or weak their password is rather than adding a tiny-little-bit-more security by scrypting.

That said, changing the 'ekey' data so that ONLY the 256-bit private key is encrypted should increase security with very little extra code. Consider what you'd have to do to brute-force:

1000 x SHA256(password_text)

Now you have a 256-bit number.  Is it the right private key?  To check:
ECC multiply to get candidate public key
RIPEMD160(SHA256(candidate public key)), and check to see if it matches public key.

I agree - I've suggested storing only the private parameter before, but didn't realize it would also make bruteforcing harder.

While we're at it, I would like to suggest using a master wallet encryption key, itself encrypted using the passphrase/keyfile, instead of directly using the passphrase-derived key for encrypting the wallet privkeys. This would make changing passwords a lot easier, and you could eg. have more than one valid passphrase. It would also make it harder to corrupt your wallet when doing as, as you could do a (add the new passphrase, commit, remove the old passphrase, commit) sequence, with at each point in time at least one of both passphrases capabable of decoding the entire wallet.

Also things like a "Generate unlock string" wizard in the GUI that creates a new random passphrase, and shows it to you with the suggestion to print it on paper and store it in a safe location, would be possible. Such an idea would probably need some discussion, but with a single key that is tied to a single passphrase, i feel we're limiting our options.

[gmaxwell]

RE: making it harder to brute-force:

I have a couple of thoughts.  First, if users choose passwords like 'abc123' or 'password' or any of the other top-1,000 passwords it doesn't matter if we're scrypt'ing; they're toast. I'd rather see work on either giving users feedback on how strong or weak their password is rather than adding a tiny-little-bit-more security by scrypting.

That said, changing the 'ekey' data so that ONLY the 256-bit private key is encrypted should increase security with very little extra code. Consider what you'd have to do to brute-force:

1000 x SHA256(password_text)

Now you have a 256-bit number.  Is it the right private key?  To check:
ECC multiply to get candidate public key
RIPEMD160(SHA256(candidate public key)), and check to see if it matches public key.

Anybody know how easy it is to GPU parallelize ECC multiplies?  A quick google search gives me the impression that is an area of active research.


RE: pre-computing wallet keys:  ??  wallet private keys are 256-bit random numbers.  Am I misunderstanding you gmaxwell?

Here I mean precomputing the result of the 1000x SHA256 so that the marginal work is zero to try it on a new wallet.  As the software is currently implemented I can precompute the SHA256x1000 of the top hundred thousand most likely passwords then reuse it over and over again on many wallets. I could also construct disk-space compact tables of _all_ sufficiently simple passwords as exist for other unsalted schemes.

The current system is unsalted for all intents and purposes (there is something passed in as "salt", but it's a constant, so it doesn't do anything useful except make the hash different from other 1000x SHA256 EVP_BytesToKey users). This is pretty bad, in all cases it gives the attacker a speedup proportional to the number of wallets they can steal on top of the speedup they get from using a GPU farm.

If you're not going to change schemes, at least encode the iteration count in the file and turn it up so that it takes, say, 100ms when the password is set. Or failing that, at least pick something that takes 100ms on your own machine. CPUs are doing roughly 4 million SHA-256 per core per second with optimized code.  This could easily be made 100x harder without making it unacceptably slow even if nothing was done to address specialized hardware speedup.

Yes, of course the "top 1000" passwords are toast regardless. But hopefully giving good password advice, as Gavin suggests, prevents any of the top 1000 from being used. I'm more concerned about the "top 100000", which can be harder to eliminate with good password advice, and slowing down the attack by a factor of 100+ would make a material improvement to the effectiveness of these attacks.

Also, part of the purpose of wallet encryption is herd immunity:  Causing people to not bother writing and distributing wallet scarfing worms because they don't expect it to pay off.  So even weaker passwords get some increased protection from a scheme that makes harder passwords unreachably hard.

Encrypting only the high entropy part of the keying material sounds like a good idea idea to me. It sounds like a free boost to the complexity of checking a candidate password.

[gmaxwell]

I appreciate your comments, but you've added nothing new to the discussion,

I reviewed your code and noticed that you were using an effectively unsalted scheme which would have been a security embarrassment to the project had it been deployed.  I read this entire thread before commenting. I apologize for not having the chance to read other forum threads which were not linked in the original post. I think its unfortunate that you believe I added nothing to the discussion.

I do see now that you made the incorrect claim that using the address as the IV prevents bruteforce attacks on the pull request— I missed it before because I only looked at the line by line comments.   Sadly using the address as the IV does almost nothing to prevent dictionary attacks.  I can still precompute the 1000x SHA-256, so what is the point of making this computationally hard when it can be trivially precomputed and shared between multiple stolen wallets? Each precomputed password requires only a single decryption to validate.

[Pieter Wuille]

gmaxwell: You are right. With the current proposed system, if you have a large table with (scheduled) AES keys derived from many popular passwords, the work to attempt a crack is a single AES decryption per wallet and per passphrase (as the current serialized privkeys contain a pubkey, only a comparison with the known pubkey must be tried after decrypting).

With Gavin's suggested improvement (only storing the private parameter instead of the entire serialized key), this becomes 1 AES decryption + 1 EC point multiplication. If the ekey's key is modified to have the address instead of the pubkey (as Gavin seems to imply), an addition SHA256 and RIPEMD160 hash are required to verify correctness.

With my suggestion to use a separate masterkey, it becomes 1 AES decryption of the master key, 1 AES key scheduling, 1 AES decryption of an ekey, 1 EC point multiplication.

Neither of these schemes take advantage of the key strengthening performed by EVP, as it can be done in advance (for simple passwords only).

[Pieter Wuille]

Suggestion to improve upon all concerns, making sure each and every crack attempt requires: 1) iterated key strengthening 2) AES decryption 3) EC point multiplication 4) RIPEMD160+SHA256 hashing:

Master keys are stored using a db record:

• KEY = ("mkey", id)
• VAL = (salt, iterations, AES(key+iv=KeyDeriveSHA512(passphrase_id, salt, iterations), data=masterkey))

Wallet keys are stored using a db record:

• KEY = ("ekey", versionByte_n, RIPEMD160(SHA256(pubkey_n)))
• VAL = AES(key=masterkey, iv=RIPEMD160(SHA256(pubkey_n)), data=privkey_n)

Both legitimate access and crack attempts need to (for each mkey entry, until a match is found):

• perform iterated key derivation from the passphase and the mkey's salt, to find key/iv for the masterkey
• Decrypt an ekey's data using it
• Do EC point multiplication on the decrypted privkey to find the pubkey
• Hash the pubkey twice
• Compare this hash with the ekey's KEY

Depending on which encryption algorithm is used, RIPEM160(SHA256(pubkey_n)) may not have enough bits to use as IV, but I'm not sure to what extent that is an issue. Alternatively, a much shorter identifier-based ekey KEY can be used, making it even harder to verify a passphrase is correct (you'd need to go looking for transactions matching the given address and so on... this would be so fuzzy that some checksum-based verification mechanism would need to be put in place, making cracking a bit easier again as well). Another alternative is adding a additional nonce to ekey's VAL, used as IV.

The reason for "versionByte_n + RIPEMD160(SHA256(pubkey_n))" in the ekey's KEY, is that it matches addresses, and could be used in the future when the entire wallet isn't loaded from disk anymore. This is probably not really an issue now.


EDIT: as public keys are stored unhashed in several places in the wallet file anyway (txouts, keypools, ...), an attacker does not need to always do the RIPEMD160(SHA256(pubkey)) operation to verify correctness.

[Matt Corallo]

I do see now that you made the incorrect claim that using the address as the IV prevents bruteforce attacks on the pull request— I missed it before because I only looked at the line by line comments.   Sadly using the address as the IV does almost nothing to prevent dictionary attacks.

Just to set the record straight.  I'm sorry with how I handled your suggestions, I didn't fully think through, nor read the IV-related bruteforce things, you are right. I still disagree with the move away from EVP things for the reasons discussion on the pull comments.  I plan on rewriting based on wallet class anyway, and will implement something similar to what Pieter propsed +/- some stuff.

[riush]

FYI, just noticed there is now a metasploit module that collects wallets. Thats exactly the kind of thing that is solved by this feature.

https://dev.metasploit.com/redmine/projects/framework/repository/revisions/12993/entry/modules/post/windows/gather/bitcoin_jacker.rb

[riush]

What would it take to put in separate passwords for each wallet 'account'?
So that for multiple user systems each user can access their own account details and functionality without affecting or having access to others accounts.

And yes, with the ability to put in a 'master' password for global wallet access?

Yeah, that would be really great. For my online-wallet I'd also like the keys for each user to be encrypted separately.

Would there be problems with bitcoin trying to use transactions from different accounts as inputs? What about change?
Would it be difficult to modify the sending code to choose only inputs from the given account and also use a change address from this account?
Has this been discussed already, or does it warrant a new thread?

[Pieter Wuille]

What would it take to put in separate passwords for each wallet 'account'?
So that for multiple user systems each user can access their own account details and functionality without affecting or having access to others accounts.

And yes, with the ability to put in a 'master' password for global wallet access?

Yeah, that would be really great. For my online-wallet I'd also like the keys for each user to be encrypted separately.

Would there be problems with bitcoin trying to use transactions from different accounts as inputs? What about change?
Would it be difficult to modify the sending code to choose only inputs from the given account and also use a change address from this account?
Has this been discussed already, or does it warrant a new thread?

You essentially want separate wallets, which is a very useful feature, but not really what accounts are intended for. I think we should rather try to move to a general system where the client can open more than one wallet file at the same time, and provide built-in possibilities to move coins from one wallet to another.

[phillipsjk]

RE: making it harder to brute-force:

I have a couple of thoughts.  First, if users choose passwords like 'abc123' or 'password' or any of the other top-1,000 passwords it doesn't matter if we're scrypt'ing; they're toast. I'd rather see work on either giving users feedback on how strong or weak their password is rather than adding a tiny-little-bit-more security by scrypting.

I had a thought: The user should not choose the password. the average user does not know how to choose secure passwords.

The user should be presented with a random 24 character base58 passphrase (128bits of entropy) and told to write it down twice. One copy should be kept off-site somewhere such as a safety-deposit box. After the user clicks "OK" without reading the message, the user should be prompted to enter the passphrase they just copied down. If they fail to enter the passphrase, they should be reminded that losing the passphrase is equivalent to deleting their money permanently*.

Of course, some (most) people will find such a long passphrase inconvenient. I think encryption should be optional. Though, I think a better approach would be support for multiple wallets: One with no encryption for petty cash/impulse purchases, and another for a wallet that is only accessed occasionally to pay bills. A savings wallet should not be stored on the computer at all; though the address for the savings wallet should be.

*Edit: I don't mean the nag screen should be permanent...
Edit: only one copy (the off-site one) of the passphrase would need to be written down if a smart-card is used to store an "easy to use" copy unlocked with a short pin.

[gmaxwell]

The user should be presented with a random 24 character base58 passphrase (128bits of entropy) and told to write it down twice. One copy should be kept off-site somewhere such as a safety-deposit box. After the user clicks "OK" without reading the message, the user should be prompted to enter the passphrase they just copied down. If they fail to enter the passphrase, they should be reminded that losing the passphrase is equivalent to deleting their money permanently*.

There was discussion on IRC about having a "recovery code" which users were forced to write down in this manner... not to address the password security issue— no password people will be comfortable typing every time they spend will be secure, but to address the very real outcome that encryption is going to increase the amount of btc lost by people, because theft is uncommon (especially the narrow set of theft that encryption stops) but forgetting things is fairly common.

[phillipsjk]

I still think encryption should be disabled by default. One issue I have seen in the forums is that many users are not even aware a file called "wallet.dat" exists; and that portions are secret. Upon learning about it, the first thing demanded is some kind of encryption like GPG.

Of course, with money on the line; you don't ever want the user to accidentally forget the passphrase. Getting a passphrase right is difficult, even if you know what you are doing. That is why I think the user should be assigned a randomly generated passphrase.

I guess I am advocating an "all or nothing" approach. If passwords don't really enhance security because they are too short, why bother?

[twmz]

I still think encryption should be disabled by default.

It is.