So, bitcoin client still use unencrypted wallet.dat

[JoelKatz]

Great work. How computationally expensive is the algorithm that converts the passphrase to the key that decrypts the private keys? What I'm worried about is a trojan that captures the encrypted private keys and plaintext public keys (or hashes), and then knows how many BTC each wallet holds. He can then try to brute force the wallets with the most coins using compromised machines to do the brute forcing.

You can find some technical details here: https://github.com/TheBlueMatt/bitcoin/commit/9914f01fac25ff3891c3af8ac76c3ad5d6c3e9c6

25,000 rounds of SHA-512, salt changed each time the wallet is encrypted. Sounds good to me.

[BubbleBoy]

25,000 rounds of SHA-512, salt changed each time the wallet is encrypted. Sounds good to me.

FFS, don't gox your own password derivation scheme, especially not one with a fixed difficulty, especially one that the current miners can attack (low asymptotic hardware cost).

Password derivation is a well studied field, please tell me Pieter why would you favor this solution over scrypt ?
http://www.tarsnap.com/scrypt.html

We estimate that on modern (2009) hardware, if 5 seconds are spent computing a derived key, the cost of a hardware brute-force attack against scrypt is roughly 4000 times greater than the cost of a similar attack against bcrypt (to find the same password), and 20000 times greater than a similar attack against PBKDF2.

[Pieter Wuille]

FFS, don't gox your own derivation scheme...

We didn't. It uses OpenSSL's EVP_BytesToKey routine with a standard hash function.

... especially not one with a fixed difficulty ...

It's not, the number of iterations is stored in the file. The implementation will probably try to iterate for 0.1s, which gives already >100000 iterations on my system here. 25000 is just a minimum/default.

... especially one that the current miners can attack (low asymptotic hardware cost).

We specifically don't use SHA256 for that reason.

Password derivation is a well studied field, please tell me Pieter why would you favor your solution over scrypt ?
http://www.tarsnap.com/scrypt.html

The disk format has an "derivation method" field, which is currently always zero (meaning EVP+SHA512), but may in the future be extended to support other methods.

This is done with the intention to support more derivation methods in the future, including scrypt, which looks really nice and aplicable here. I'm not sure scrypt is not "too young" to trust right now, though.

You can find some of the discussion about the system here: http://forum.bitcoin.org/index.php?topic=8728.20
Note that the resulting hash of the passphrase is never stored directly or indirectly, and the only thing encrypted with it is a random 256-bit AES key, so a rainbow-table attack is not possible.

[memvola]

• The GUI currently only has one way for unlocking a wallet, namely by entering a passphrase. The disk format does support several independent passphrases, although adding a second one is currently not implemented. In the future, this may allow a "generate unlock code" wizard or something similar.

Cool. Hopefully we won't have a wave of forgotten passwords, like the wave of stolen wallets we had. Secondary passwords / unlock codes would prevent this from happening, since I'm guessing inexperienced users would take notice, if it's by default. Maybe one unlock code could be generated by default and displayed on setup for the first version, before implementing a proper management interface. User has the option to ignore it.

[JoelKatz]

Note that the resulting hash of the passphrase is never stored directly or indirectly, and the only thing encrypted with it is a random 256-bit AES key, so a rainbow-table attack is not possible.

It's salted, so a rainbow table attack is impossible for that reason as well.

[BubbleBoy]

We specifically don't use SHA256 for that reason.

The same GPUs that are used for mining can be easily reconfigured to attack PKBDF - SHA512 (that EVP_BytesToKey uses). The hacker only needs to rent the mining farm for the duration of the attack.  There will plenty of GPU farms available for rent when ASICs put them out of bussines (indeed, ASICs probably can't be configured to attack another hash).

A single 5970 can try 10.000 keys per second of the 100.000 iteration variety, so it can break a 40 bit entropy password in about 100 days. If you can rent a 5970 for a few $/day, than you can break many wallets for a few hundred dollars each. You know from the start what wallet is worth cracking from those you managed to stole, since the public key thus the amount enclosed are stored in plain text. It would be cost effective to crack allinvain's wallet even if he uses a 50bit entropy password, which let's face it not many users do.

Regarding scrypt being too young, from what I've seen in the code it still employs PKBDF2 before and and after the the memory-hard part. So even if it fails at being memory-hard, it will not compromise the password, it will be at least as secure as the current scheme.

[bcearl]

How computationally expensive is the algorithm that converts the passphrase to the key that decrypts the private keys?

That doesn't matter. Computers get faster exponentially, it doesn't matter whether you hash 10 times or 1000 times, if you want it to be secure for years or decades.

Password complexity cannot be substituted by this. Passwords get exponentially harder to break when you add more characters. (That's the whole point in password and key lengths).

You will have the advantage of AES256 over AES128 when you have more than 20 characters of random (same probability for each character independend of other characters). With 40 characters you reach the highest level AES256 can give you. That should be good for quite a while.

[MikesMechanix]

A single 5970 can try 10.000 keys per second of the 100.000 iteration variety, so it can break a 40 bit entropy password in about 100 days. If you can rent a 5970 for a few $/day, than you can break many wallets for a few hundred dollars each. You know from the start what wallet is worth cracking from those you managed to stole, since the public key thus the amount enclosed are stored in plain text. It would be cost effective to crack allinvain's wallet even if he uses a 50bit entropy password, which let's face it not many users do.

How did you come to these numbers?

@40 bits of entropy the average time to crack a password, given 10000 trials per second, is
2^40/10000/60/60/24/2 = 636 days

And, FWIW, a 8 character all-lowercase random alphanumeric is typically more than 40 bits entropy.

@50 bits
2^50/10000/60/60/24/2 = 651562 days

Hard to see the cost effectiveness of a 1000 5970s blasting out keys for a year or two. And that's still only an 8 character alphanumeric with one special character.

[Horkabork]

A single 5970 can try 10.000 keys per second of the 100.000 iteration variety, so it can break a 40 bit entropy password in about 100 days. If you can rent a 5970 for a few $/day, than you can break many wallets for a few hundred dollars each. You know from the start what wallet is worth cracking from those you managed to stole, since the public key thus the amount enclosed are stored in plain text. It would be cost effective to crack allinvain's wallet even if he uses a 50bit entropy password, which let's face it not many users do.

How did you come to these numbers?

@40 bits of entropy the average time to crack a password, given 10000 trials per second, is
2^40/10000/60/60/24/2 = 636 days

And, FWIW, a 8 character all-lowercase random alphanumeric is typically more than 40 bits entropy.

@50 bits
2^50/10000/60/60/24/2 = 651562 days

Hard to see the cost effectiveness of a 1000 5970s blasting out keys for a year or two. And that's still only an 8 character alphanumeric with one special character.

The 10k passwords/sec seems is a bit off. I've seen that on a few different forums. I think that was for cracking zip files or something.

A single 5870 can do 4.2 MD5 ghash/sec in whitepixel. A 5970 probably like 7 (in an x4 rig, they got 28.6 Ghash/sec).

At 40 bits that would be:

2^40/7000000000/60/2 = 1.3 minutes on average.

At 50 bits:

2^50/7000000000/60/60/2 = 22.3 hours on average.

Okay that can't be right. Would somebody please tell me what I'm assuming that is wrong? (Whitepixel data)

[JoelKatz]

Okay that can't be right. Would somebody please tell me what I'm assuming that is wrong?

You're assuming it only takes one hash to try a password.

[Jazkal]

http://www.youtube.com/watch?v=3yoduTFjZW4&#t=1143s

Somebody is building a better wallet, with built in two factor. Hmm.

[BubbleBoy]

How did you come to these numbers?

I think I've assumed 100.000 keys per second. With the correction, it costs maybe a few thousand $ to break a 40 bit entropy wallet.

And, FWIW, a 8 character all-lowercase random alphanumeric is typically more than 40 bits entropy.

Absolutely not. 8 single case alphanumerics can have at most 41.3 bits of entropy (5.17 bits/char), assuming a perfect random number generator and no inter-symbol memory (i.e something not generated by a human). An average 8 character human-generated password has about 18 bits of entropy, and that after allowing the whole set of 94 printable ASCII characters !

I must insist on this point because it's the main takeaway: users don't choose good passwords. The average PayPal user has about 42 bits of entropy, and the majority of PayPal users have even less.



It follows than that if you can increase the asymptotic hardware cost for the attacker with 2^10 or 2^20, as scrypt allows, you are achieving a great deal: moving from a situation where most passwords are crackable for a few thousand $, to a situation where most passwords need a few million dollars to crack. The same can be achieved by forcing users to chose good passwords, but that's hated by users and requires more implementation effort than just dropping scrypt in the source code.

[phillipsjk]

If I use GPG for my e-mails in Evolution, for every encrypted e-mail it asks for the password.
Why not implement this also in a bitcoin client: for every transaction the password is required, and the wallet is decrypted but not saved on HD, only in RAM when it is needed for the transaction.
This way the wallet is never decrypted in a file on the HD and is difficult to be stolen.

The GPG keys are replaced periodically.  If you forget the passphrase, you are not likely to lose large sums of money. A savings wallet may be stored for decades. Are you really going to remember a passphrase consisting of 32 random digits in 10 years?

Computers are now fast enough that you pretty much have to write down important secure passwords (With the security implications understood my most).

Take-away: good passphrases are hard.

[ctoon6]

Why do we need encryption? If you need to keep a wallet for a long time drop it on 3-10 drives and delete the originals, or make them on live cds and have them connect online until you need to spend them.

my philosophy is as follows

1. humans are forgetful.
2. humans are predictable.
3. humans loose stuff, hence 3-10 copies, also for data redundancy.

The best solution i can think of is to hypnotize and embed you passwords into your friends in such a way that you do not even know the password. But we are not all mentalist now are we?

overall the most realistic solution i can think of is the standalone bit coin device. it would connect over wifi and never need to be hooked up to a computer. it could have a qr code reader for use at stores and such.

[JoelKatz]

Why do we need encryption? If you need to keep a wallet for a long time drop it on 3-10 drives and delete the originals, or make them on live cds and have them connect online until you need to spend them.

my philosophy is as follows

1. humans are forgetful.
2. humans are predictable.
3. humans loose stuff, hence 3-10 copies, also for data redundancy.

The best solution i can think of is to hypnotize and embed you passwords into your friends in such a way that you do not even know the password. But we are not all mentalist now are we?

overall the most realistic solution i can think of is the standalone bit coin device. it would connect over wifi and never need to be hooked up to a computer. it could have a qr code reader for use at stores and such.

What if you lose one of the 3-10 copies and the person who finds it empties your wallet? The Bitcoin system, obviously, has protection against double spending. So you're screwed in that case.

[phillipsjk]

overall the most realistic solution i can think of is the standalone bit coin device. it would connect over wifi and never need to be hooked up to a computer. it could have a qr code reader for use at stores and such.

I think you are taking the term "air gap" too literally

[MikesMechanix]

A single 5870 can do 4.2 MD5 ghash/sec in whitepixel. A 5970 probably like 7 (in an x4 rig, they got 28.6 Ghash/sec).

The assumption was a 100k rounds of SHA-512, not a single round of MD5. I don't know if the 10k trials / sec is correct, I just assumed that the OP had it right. It translates to roughly 1 gigahash/second of SHA-512 per 5970 which sounds slightly high to me but is probably ok given the assumption that GPUs wll probably keep getting more powerful each year.