Bitcoin Forum
December 03, 2016, 01:48:30 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 3 [4] 5 »  All
  Print  
Author Topic: Brain Wallet standardization  (Read 14392 times)
anu
Legendary
*
Offline Offline

Activity: 938


P2P Everything


View Profile WWW
August 02, 2012, 01:48:14 PM
 #61

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.

Zero Reserve - A distributed Bitcoin Exchange

Install - Getting Started - BitcoinTalk Thread - Github Source
1480772910
Hero Member
*
Offline Offline

Posts: 1480772910

View Profile Personal Message (Offline)

Ignore
1480772910
Reply with quote  #2

1480772910
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480772910
Hero Member
*
Offline Offline

Posts: 1480772910

View Profile Personal Message (Offline)

Ignore
1480772910
Reply with quote  #2

1480772910
Report to moderator
1480772910
Hero Member
*
Offline Offline

Posts: 1480772910

View Profile Personal Message (Offline)

Ignore
1480772910
Reply with quote  #2

1480772910
Report to moderator
jgarzik
Legendary
*
Offline Offline

Activity: 1470


View Profile
August 02, 2012, 02:02:42 PM
 #62

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

     http://xkcd.com/936/

Title:  "password strength"


Jeff Garzik, bitcoin core dev team and BitPay engineer; opinions are my own, not my employer.
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
gmaxwell
Staff
Legendary
*
Offline Offline

Activity: 2016



View Profile
August 02, 2012, 02:16:22 PM
 #63

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
Legendary
*
Offline Offline

Activity: 938


P2P Everything


View Profile WWW
August 02, 2012, 02:26:04 PM
 #64

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.

Zero Reserve - A distributed Bitcoin Exchange

Install - Getting Started - BitcoinTalk Thread - Github Source
jgarzik
Legendary
*
Offline Offline

Activity: 1470


View Profile
August 02, 2012, 03:15:23 PM
 #65


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)


Jeff Garzik, bitcoin core dev team and BitPay engineer; opinions are my own, not my employer.
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
anu
Legendary
*
Offline Offline

Activity: 938


P2P Everything


View Profile WWW
August 02, 2012, 03:46:05 PM
 #66


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.

Zero Reserve - A distributed Bitcoin Exchange

Install - Getting Started - BitcoinTalk Thread - Github Source
ElectricMucus
Legendary
*
Offline Offline

Activity: 1540


Drama Junkie


View Profile
August 02, 2012, 04:11:34 PM
 #67

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.

First they ignore you, then they laugh at you, then they keep laughing, then they start choking on their laughter, and then they go and catch their breath. Then they start laughing even more.
Pieter Wuille
Legendary
*
Offline Offline

Activity: 1036


View Profile WWW
August 02, 2012, 04:20:56 PM
 #68

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.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Joe200
Sr. Member
****
Offline Offline

Activity: 266



View Profile
August 02, 2012, 05:57:38 PM
 #69

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
Legendary
*
Offline Offline

Activity: 938


P2P Everything


View Profile WWW
August 02, 2012, 06:40:55 PM
 #70


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.

Zero Reserve - A distributed Bitcoin Exchange

Install - Getting Started - BitcoinTalk Thread - Github Source
gmaxwell
Staff
Legendary
*
Offline Offline

Activity: 2016



View Profile
August 02, 2012, 09:56:25 PM
 #71

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
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
August 02, 2012, 10:27:04 PM
 #72

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? Smiley

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
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
August 02, 2012, 10:32:20 PM
 #73

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
Legendary
*
Offline Offline

Activity: 1036


View Profile WWW
August 02, 2012, 10:59:50 PM
 #74

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

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
August 02, 2012, 11:09:03 PM
 #75

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
Pieter Wuille
Legendary
*
Offline Offline

Activity: 1036


View Profile WWW
August 02, 2012, 11:11:07 PM
 #76

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.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
August 03, 2012, 03:13:18 AM
 #77

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.
Ukigo
Hero Member
*****
Offline Offline

Activity: 924


View Profile
August 03, 2012, 07:02:01 AM
 #78

I'm playing with another algo :
In "pseudocode" :
Code:

           pass = SHA512(your_long_passphrase)
           salt = SHA512(pass)
           dk_length = 360000
           dk = Scrypt( pass, salt, 524288, 8, 1, dk_length)
           split "dk" into 64-byte chunks
           produce privkey from every chunk : privkey = SHA256(chunk)

  Any flaws or suggestions ?

"...Enemies are everywhere ! Angka is all rage ! Be a good soldiers, blow everything... " <-- Pol Pot (C)
anu
Legendary
*
Offline Offline

Activity: 938


P2P Everything


View Profile WWW
August 03, 2012, 07:39:59 AM
 #79

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.

Zero Reserve - A distributed Bitcoin Exchange

Install - Getting Started - BitcoinTalk Thread - Github Source
Ente
Legendary
*
Offline Offline

Activity: 1834



View Profile
August 04, 2012, 09:59:09 AM
 #80

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
Pages: « 1 2 3 [4] 5 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!