Topic: Brain Wallet standardization (Read 15378 times)

Speaking of Scrypt parameters,
standard trinity of 16384, 8, 1 is likely not enough for our case.

If you have enough RAM on board you can use these params :
( from my post above ) :
this setup will take LOOONG time to calculate, but it's Ok ,
because you'll have  a lot of privkeys , and not just one.

Well, Scrypt should fit the bill, and I think that's what's used in bcrypt [sorry, I was wrong there]. Although there are now GPU versions of scrypt miners, that is not a problem for a proper implementation of scrypt. The miner versions (litecoin, etc) of scrypt have tweaked parameters that make it faster, such as reduced memory requirements. If these settings are left at the default, it would be more difficult to make it run on a GPU.

This is a good point. Ideally a method that GPUs could not do easily would be ideal?

No idea what inputing the original passphrase in each round will do.


The purpose of the unknown number of rounds is to make SIMD SIMT... architectures inefficient and force the attacker to use CPUs. Since the user is using CPUs, the attacker has higher costs.

But I don't know if that will have a similar effect on FPGA. If not, this is not such a great idea. But then, doing an operation like the residual divide is making the FPGA waste loads of gates.

Consider using the algorithm PBKDF2.  It is specifically intended as a "key derivation" algorithm and adds iterations and salt while avoiding the lost entropy problem.

The way I understand it, PBKDF2 is not the entire algorithm - it actually is a partial algorithm that sort of has a "fill in the blank" with the hash algorithm of your choice to do the hashing.  Which algorithm is up to you the implementer, not PBKDF2.  Using PBKDF2 takes a simple hash function and extends it to add salting and iterations without loss of entropy.

So, PBKDF2-HMAC-SHA512 means use the PBKDF2 algorithm and, where it calls for a hash algorithm, use SHA512 to generate the hash.

Avoiding SHA256 is preferable simply due to how fast the Bitcoin community has accelerated SHA256 hashing, making it somewhat less preferable as a key derivation algorithm.

Are you sure about that? I think that Casascius was talking about another algorithm that just hashed the previous hash without introducing any new entropy. By reintroducing the passphrase every round I think the entropy is topped up every iteration to the same amount the passphrase originally introduced. I don't think more bits are needed due to this and it would be nice if this standard made use of existing primitives already in the code base.

I would love to hear what Casascius has to say on this.

Regarding the number of rounds I think that since you cannot skip ahead with this method that just being sufficiently deep is enough. However, nothing about this method prevents the input of a custom number of rounds. The list of preset number of rounds with varying depths can be there for those that do not want to fear forgetting how many rounds.

It all depends on how long the hacker is willing to spend hashing each password in his dictionary. They might spend 1 second on each word(a very long time) but will they spend 10 seconds, 100 seconds? Surely they won't spend 20 minutes per word to create their rainbow table. If you don't plan to take your private key out very often then waiting a day for it to be calculated might be reasonable.

If the attacker knows your passphrase it will be trivial to crack just by creating the address every iteration until it found one in the block chain. The keyspace defined by the number of iterations it is reasonable for someone to actually accomplish at a home PC is far too small to act as an added secret. However long it takes you to decode your key, an attacker can do in just a bit more time(he has to produce the addresses) or faster if they have a better computer than you.

The number of iterations is not meant to be an added secret, if you want to add another secret number just put it in your passphrase and it will add the same amount of challenge to the attacker. The number of iterations is to force work on someone making a rainbow table of addresses based on a dictionary.

A good deep number of iterations would have too many digits to be easily remembered alongside a passphrase. People would choose small ones. The place for secrets is in the passphrase, not proof of work hash iteration.

Interesting idea in looking for a magic hash with 1 in a million properties so as to not know the number of iterations in advance, but wouldn't both the user and the attacker suffer the exact same costs? Seems like a zero sum game, each word still only has one answer. You could also have no control over the depth of your password, it could be very shallow or so deep it takes days to make. You will have no idea if you are almost done making the key or not even close. No progress bar that is for sure.

As Casascius pointed out, you loose entropy with every round. So you might want to choose a hash with more bits and do the sha256 for the last round only.

I think it presents a more difficult problem to crack it if the number of rounds is not known in advance:

do {
  $hash = sha512( $hash.$phrase );
while( hash % 100_000_000 );  # This will really have to be gmp, I guess.
$hash = sha256( $hash );

Standardization is a good idea for many reasons. I have come up with this for myself:


I am going to print out a card with the public key in text/qr and on the back of the card I will put the above source code.


I think it is slow enough to resist brute force. I put the password back into the hash every iteration so that if you have one private key compromised they cannot get the rest without the password.

This can also be used for deterministic wallets. I think it is better than sha256('') because it does not allow an attacker to skip keys along the way.

The output of this script can be directly imported into a blockchain.info wallet

I am not certain, but I think reintroducing the password in every iteration may mitigate(solve?) the issue with entropy being lost from repeated hashing. Can anyone who understands hashing better than me confirm this?

Regarding how many iterations, I was thinking upon generation you could choose from 1, 100, 1000, etc... Then when recovering the user could provide what they entered, or if they forgot the program could just recover all of the predefined checkpoints. This would allow the user to choose between fast or difficult to brute force, but still not require them to remember the number of iterations.

That makes sense, but whatever Bitcoin itself is based in should suffice. I would plan to update the wallet if Bitcoin changes to a new algorithm. I'm just afraid I would forget which I used unless there is also a standardized one for brain wallets. Scrypt might be a good choice.

Scrypt looks like a good choice.

Wouldn't it be the best to nest multiple hash-algorithms to compensate for attacks on a single one, which could be found in future?

Scrypt seems to be very new, and not as well analyzed as Bcrypt or PBKDF2. SHA is very well tested, but too fast (to prevent brute-force) on its own.
So if you nest for example Scrypt, Bcrypt, PBKDF2 and SHA you should be on the safe side. Even if a flaw in Scrypt is discovered, which allows a speedup to levels of SHA, you would still be protected by Bcrypt (and the others). Or do I make a mistake here?

Salt != Password != Secret :-P

But yes, of course you are right, the passphrase would be written down for heirs anyway. No problem to write down salt/email/pin as well in that occasion.
Nevertheless, I prefer to only have to remember as little as necessary, for a brainwallet.

Ente

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.

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

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.

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.

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.

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.

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

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