Brain Wallet standardization

[anu]

from a 5000-word dictionary

The dictionary I am looking at has 2 Million words, containing mostly words that are common in English plus variations thereof.

given that there are 500 other languages and dialects,

That would be southern India (Dravidian languages) alone. The real number of languages and dialects is closer to 50,000. Which gives you a dictionary in the order of 1 Billion words to choose from (since there are many repetitions). Which in my book is around 30 Bit - assuming that such a dictionary even exists.

Then you spice that up with some personal info like your first ever X.400 address and good luck to the cracker.

Ah, about math. If you use X rounds of hashing, the cost for the attacker is X times as much. So if a cracker needs to run a PC for $500 for a month to find your pass phrase at one round, he has to pay 500 Million for a huge cluster to find the same phrase if 1 Million rounds are employed. Or run his PC 100,000 years. If this is incorporated in the standard, it comes for free - for the user at least, since he doesn't have to remember any more data for the improved security - 1 Million rounds are as good as 20 Bits.

[1714108240]

1714108240

[1714108240]

1714108240

[1714108240]

1714108240

[jgarzik]

Actually, XKCD has packed an amazing amount of password wisdom into a single comic:

     http://xkcd.com/936/

Title:  "password strength"

[gmaxwell]

Actually, XKCD has packed an amazing amount of password wisdom into a single comic:
     http://xkcd.com/936/
Title:  "password strength"

It's excellent but:  It's presuming e.g. bruteforcing a website where the site effectively rate limits the attempt.  His impossible to crack passwork at 1000 attempts per second is only a few hours work on a GPU cracker that does a billion attempts per second in an offline attack. So people should be careful not to carelessly generalize the conclusions there.

The only sane approach for a threat model where the attacker can mount a fast offline attack is to use a strong CSPRNG to generate 128 bits or so of random data.. then convert that to some thing you feel like typing be it 'random' letters words from some dictionary, etc.  And... much of the time its perfectly fine to write it down, broken into two parts if you like— because the attackers that matter today are mostly in places far far away from you.

The kind of advice often given for passwords commonly gets people exploited. You think you're being quite clever using ")qww!83w" but this an every other clever scheme you can imagine can be easily generated by the cracking tools. You think you're being quite clever using "What all agree upon is probably right; what no two agree in most probably is wrong" but a fast GPU attack can scan through every phrase in a whole library of books in short order.  Actually random is safe, anything else is guesswork and hoping that the sum of all attackers over all the future is less smart than you in this instant. — especially for something like private key material where there is no strengthening, and where an attacker attacks all users with almost O(1) effort.

[anu]

but a fast GPU attack can scan through every phrase in a whole library of books in short order. 

It should be possible to throw some sticks into the legs of SIMD & friends:

How about if the number of rounds are not specified, but the resulting hash has to satisfy a condition, which has a chance of 1/difficulty*? I think with such an algorithm, the CPU is way faster than the GPU.



* Motivated by Bitcoin mining. Of course, one would take the N-1 hash, otherwise the resulting private key would have less than 256 Bits.

[jgarzik]

I occasionally think about making the number of rounds variable, based on some algorithmic factor:  ALGO_A(passphrase), take lower N bits (16? 20?) as number of rounds of ALGO_B(passphrase)

[anu]

I occasionally think about making the number of rounds variable, based on some algorithmic factor:  ALGO_A(passphrase), take lower N bits (16? 20?) as number of rounds of ALGO_B(passphrase)

But then the GPU program knows ahead of time it has to loop say, 547492 rounds. But if the hash has to be checked after each round I think this makes any SIMD or SIMT or such impractical. The disadvantage is of course that it may possibly loop indefinitely / too long. But I think this will be extremely rare.

[ElectricMucus]

This may sound silly but if you just want a privkey from a passphrase you can do that without any hashing.

You can store all characters in the alphabet plus the space in three trits. (Trinary system)

It has to be 26 characters long though (including spaces) That is because ln3(2^128)/3 = 26.92
So you loose just 0.92 bits of entropy. This can also help you to come up with long enough passphrase to use otherwise.

[Pieter Wuille]

Here is a short version of a text-to-key algorithm, resulting from a discussion with gmaxwell and etotheipi. I'm currently working on other things, but I hope it can already provide some inspiration.

The idea is to have both a variable number of iterations, and a checksum (by not allowing every possible input text).

To go from text T to key:

• Calculate SHA512(SHA512(...(SHA512(T))), with 256 iterations
• If the 256th iteration results in a hash that starts with 8 zero bits, output the 255th iteration result as key
• If not, do more iterations, until the 512th
• If the 512th iteration results in a hash that starts with 9 zero bits, output the 511th iteration result as key
• If not, do more iterations, until the 1024th
• If the 1024th iteration results in a hash that starts with 10 zero bits, output the 1023th iteration result as key
• and do on ...

So you sacrifice some bits in checksums, but compensate those exactly by more iterations. This way, the seed text itself  encodes the number of iterations, and an attacker cannot know the right number in advance, preventing a short way out.

A more complex version, with some mathematical guarantees is derived here, but there is little explanation.

[Joe200]

The only sane approach for a threat model where the attacker can mount a fast offline attack is to use a strong CSPRNG to generate 128 bits or so of random data.. then convert that to some thing you feel like typing be it 'random' letters words from some dictionary, etc.  And... much of the time its perfectly fine to write it down, broken into two parts if you like— because the attackers that matter today are mostly in places far far away from you.

With a dictionary of 850 Basic English words, you would need to type 13 words.

The Basic English word list is a good choice because it is standardized, few words means less chance of typos, it could work better for non-English speakers. Typing 13 words is easy.

[anu]

The Basic English word list is a good choice because it is standardized, few words means less chance of typos, it could work better for non-English speakers. Typing 13 words is easy.

From "difficult to remember, easy for a computer to guess" in http://xkcd.com/936/ you move to "sure to forget, difficult for a computer to guess".

How does it improve security of a native Arab speaker if he is forced to remember English words? Using his native Arab would put him out of reach of most dictionary attacks.

[gmaxwell]

Using his native Arab would put him out of reach of most dictionary attacks.

No. It wouldn't.  Anyone making a real effort to crack private keys would have dictionaries in every language, including Klingon.  In almost every post people underestimate what the attacker will do. Here is a hint: If you think to say that he won't do something, then in fact he will think of it too and some will eventually do it— unless he simply can't, and getting more/larger dictonaries is something anyone can do. He will do things you can't even imagine.

You must defend against all attackers, now and in the future. An attacker can find any victim, and with the same effort of attacking one victim he attacks all. The economics of these attacks strongly favor the attacker.  The only way to have reasonable confidence is to move things into the realm of cant: e.g. having tractable strong entropy and accepting reasonable upper bounds on the sum total energy expendable by all attackers on computation you can say an attacker _can't_ crack a key with greater than negligible probability.

[DeathAndTaxes]

It's excellent but:  It's presuming e.g. bruteforcing a website where the site effectively rate limits the attempt.  His impossible to crack passwork at 1000 attempts per second is only a few hours work on a GPU cracker that does a billion attempts per second in an offline attack. So people should be careful not to carelessly generalize the conclusions there.

It isn't presuming a websiting is rate limiting.  What website puts the number of login attempts at 1,000 per second and doesn't lock the account after the first billion wrong passwords?

It is presuming that person protecting the passwords actually cares about security.

bcrypt or pbkdf2

That is the whole point SHA-256 is TOO FRIGGIN fast to provide any brute force resistance (unless the passphrase is extremely long).

bcrypt w/ workload of 10 will slow a GPU down to 10,000 or so password attempts per second.  At workload 20 it is more like 10 (no thats no a typo) password attempts per second.  

Now rethink that carton if a high end GPU is only able to attempt 10 to 10,000 passwords per second?

[DeathAndTaxes]

Here is a short version of a text-to-key algorithm, resulting from a discussion with gmaxwell and etotheipi. I'm currently working on other things, but I hope it can already provide some inspiration.

The idea is to have both a variable number of iterations, and a checksum (by not allowing every possible input text).

To go from text T to key:

• Calculate SHA512(SHA512(...(SHA512(T))), with 256 iterations
• If the 256th iteration results in a hash that starts with 8 zero bits, output the 255th iteration result as key
• If not, do more iterations, until the 512th
• If the 512th iteration results in a hash that starts with 9 zero bits, output the 511th iteration result as key
• If not, do more iterations, until the 1024th
• If the 1024th iteration results in a hash that starts with 10 zero bits, output the 1023th iteration result as key
• and do on ...

So you sacrifice some bits in checksums, but compensate those exactly by more iterations. This way, the seed text itself  encodes the number of iterations, and an attacker cannot know the right number in advance, preventing a short way out.

A more complex version, with some mathematical guarantees is derived here, but there is little explanation.

I like it.  Still 256 is probably too small.  Modifying the algorithm so the min passphrase is say 2,000 iterations and the average passphrase is closer to 10,000 iterations would be better.  Also I think we should move away from SHA-256.  With all the OpenCL, FPGA, and soon ASIC hitting the market for massively acceleration SHA-256 hashing using a chained function of an algorithm already massively accelerated seems like steps forward, one step back.  Even SHA-512 would be better.  Something like bcrypt would be even better.

[Pieter Wuille]

I like it.  Still 256 is probably too small.  Modifying the algorithm so the min passphrase is say 2,000 iterations and the average passphrase is closer to 10,000 iterations would be better.  Also I think we should move away from SHA-256.  With all the OpenCL, FPGA, and soon ASIC hitting the market for massively acceleration SHA-256 hashing using a chained function of an algorithm already massively accelerated seems like steps forward, one step back.  Even SHA-512 would be better.  Something like bcrypt would be even better.

It is using SHA512; I prefer not to use SHA256 as the Bitcoin world already has way too much power for cracking that.

Also, generating a 256-iteration/8-bit key requires 65536 iterations on average (both for you and for an attacker, except the attacker doesn't know you're only using a 256/8 key).

[casascius]

A problem with using multiple iterations for a key generation algorithm brought up by gmaxwell way back when we were discussing the merits of supporting SHA256-based minikeys in the Satoshi client.

Each time you do an iteration, you LOSE entropy.  This is unavoidable, and the reason why we have algorithms like PBKDF2 using SHA256 HMAC (or something stronger to allay the SHA256 concern).  When you do thousands or tens of thousands of iterations, you practically hemorrhage entropy.

For quick and dirty brainwallets, sure, SHA256 is great.  But when we decide that's not enough and go down the road of specifying iterations of a hash function, that's when it's probably time to start specifying a proper key derivation algorithm.

What do you guys think?

PBKDF2 takes two input strings and a number of rounds as input: one string is meant to be the "password", and the other is meant to serve a purpose much more like salt.  What if the "standard" recommended non-1xSHA256 brainwallet consisted of the following?
* Your passphrase
* Your e-mail address (which will go in the "salt-like" field)
* A PIN number (which will be used as the number of rounds)

Of course, any user can use anything they want.  But if they stick to these simple recommended guidelines and choose a strong passphrase, they're likely to enjoy an excellent degree of security along with a low probability that they will forget how they set their brainwallet up.

[Pieter Wuille]

Each time you do an iteration, you LOSE entropy.  This is unavoidable, and the reason why we have algorithms like PBKDF2 using SHA256 HMAC.

That is why you use a hashing algorithm with more bits than the output. Use SHA512, and eventually (after all iterations), truncate the output to 256 bits. For any number of iterations computable using all available energy on earth, the loss in entropy will be negligable.

[DeathAndTaxes]

I like it.  Still 256 is probably too small.  Modifying the algorithm so the min passphrase is say 2,000 iterations and the average passphrase is closer to 10,000 iterations would be better.  Also I think we should move away from SHA-256.  With all the OpenCL, FPGA, and soon ASIC hitting the market for massively acceleration SHA-256 hashing using a chained function of an algorithm already massively accelerated seems like steps forward, one step back.  Even SHA-512 would be better.  Something like bcrypt would be even better.

It is using SHA512; I prefer not to use SHA256 as the Bitcoin world already has way too much power for cracking that.

Also, generating a 256-iteration/8-bit key requires 65536 iterations on average (both for you and for an attacker, except the attacker doesn't know you're only using a 256/8 key).

Sounds awesome then.  I need to take a closer look.  Using single round fast hash functions (like MD5 or SHA-1/2) for passwords is a pet peeve of mine.  People underestimate how fast those functions are.   An iterative chained function is essential for providing brute force resistance.

[anu]

Using his native Arab would put him out of reach of most dictionary attacks.

No. It wouldn't.  Anyone making a real effort to crack private keys would have dictionaries in every language, including Klingon.  In almost every post people underestimate what the attacker will do. Here is a hint: If you think to say that he won't do something, then in fact he will think of it too and some will eventually do it— unless he simply can't, and getting more/larger dictonaries is something anyone can do. He will do things you can't even imagine.

I didn't say "Rely on it". The same rules apply to Arab as to English, of course. That should really go without saying.

Limiting the choice of words to 850 English words does not improve security. And enforcing 13. A forgotten pass phrase is as good as a stolen one. After not thinking about your 13 words for a month, they are gone from memory. And that's for English speakers. Now try to remember 13 Cantonese words to appreciate the difficulty of a non-English speaker.

[Ente]

A problem with using multiple iterations for a key generation algorithm brought up by gmaxwell way back when we were discussing the merits of supporting SHA256-based minikeys in the Satoshi client.

Each time you do an iteration, you LOSE entropy.  This is unavoidable, and the reason why we have algorithms like PBKDF2 using SHA256 HMAC (or something stronger to allay the SHA256 concern).  When you do thousands or tens of thousands of iterations, you practically hemorrhage entropy.

For quick and dirty brainwallets, sure, SHA256 is great.  But when we decide that's not enough and go down the road of specifying iterations of a hash function, that's when it's probably time to start specifying a proper key derivation algorithm.

What do you guys think?

PBKDF2 takes two input strings and a number of rounds as input: one string is meant to be the "password", and the other is meant to serve a purpose much more like salt.  What if the "standard" recommended non-1xSHA256 brainwallet consisted of the following?
* Your passphrase
* Your e-mail address (which will go in the "salt-like" field)
* A PIN number (which will be used as the number of rounds)

Of course, any user can use anything they want.  But if they stick to these simple recommended guidelines and choose a strong passphrase, they're likely to enjoy an excellent degree of security along with a low probability that they will forget how they set their brainwallet up.

I like it!
Although, I would rather not have to memorize my emailaddress.. How about birthdate as "salt"?
Yes, it may (or may not) be less secret than a emailaddress, but thats not the point of salt anyway.
There will be people who change their email every other year and who will lose track of what they used back then. Or who only documented their passphrase and pin, and their heirs will have a tough time figuring it out..

pin..
how about having a default pin too, which currently would make the calculation take, say, one minute? If people just want to remember the passphrase, they use the default pin. If they choose a different pin, be it.

I agree, we should define a different method than SHA* for the standard. Or, at least, make two modes into the standard, SHA* and PBKDF2 et al.

Ente

[casascius]

I like it!
Although, I would rather not have to memorize my emailaddress.. How about birthdate as "salt"?
Yes, it may (or may not) be less secret than a emailaddress, but thats not the point of salt anyway.
There will be people who change their email every other year and who will lose track of what they used back then. Or who only documented their passphrase and pin, and their heirs will have a tough time figuring it out..

Using a birthdate is a bad idea, 90% of the demographic that would use a brainwallet will predictably have one of about 10,000 birthdates, neutralizing the value and making a mass attack feasible.  One should be able on the other hand to try each of their recent emails if there is more than one candidate.

Heirs aren't really relevant since a brainwallet is by definition a memorized thing that will be lost upon death. But if someone writes one down for safekeeping, there is no reason they can't or wouldn't want to write down all of the strings needed to restore it.

I would agree with what you suggested on PIN - the more I think about it, there is actually little reason for it because it could be brute forced so easily. For the stakes involved and given that users are likely to choose piss-poor passphrases, an iteration count that requires a very long time (60+ seconds on today's hardware) is actually quite reasonable.