Bitcoin Forum

Online and paper Bitcoin keys can be generated any which way, just as long as they are compatible with the blockchain. Many of the clients will now even import private keys in various formats. Brain Wallets are another story. The private key is dependent on the client that generated it. If the point of a Brain Wallet is to go dark, then you'll need assurance that generating your key is not traceable to a particular client. If you use your pass phrase in a different client, it will generate the wrong key to your cache. Is there a way to address some sort of standardization of the encryption method of Brain Wallets?

It depends on your approach. If all you want is a "one passphrase --> one privkey" approach, the original way was/is to simply hash the phrase with sha256.
The output is automatically a valid privkey. The pubkey can be calculated from that privkey.
You could use different hashing algos, or a combination of them (bitcoin uses at least ripemd160 and sha256), This would not generate more security, though. Sure, if someone knew the phrase (or has a wordlist), the exact combination of algos is an additional security, but computers have no big problem to test a dozen combinations of algos per phrase. The problem, of course, is to not only remember "mY Beetcoins are oh-so-safe!!1!" but now "mY Beetcoins are oh-so-safe!!1!" "sha256-ripemd160-sha256-sha256-ripemd160".
Now if your approach is to have one passphrase which generates more than one key, without compromising all keys when one key becomes public, I dont know. Clients already are able to do this, but I didnt read how they do it and if its the same way for all of them.

I am all for a standart! At the moment it should be relatively easy to have, there arent too many clients around and the community is quite centralized. So maybe its as easy as create a draft, find a good standart, ask client-authors and exchanges to implement it?
Oh, then get a standart of both (single-key and multi-key) approaches, and give them a name too! :-)

Ente

openssl passwd -1 -salt "long phrase" | sha256sum

You suggest using both a salt and a password there? If people have to remember both (and keep both secret), bitcoins will (more likely) be lost. The alternative, which is how I read your command first, would be to use the same salt for everyone as a default. Which would then be vulverable to rainbowtables.
So.. I think I prefer a passsword only. Or a salt only. Either way, just one string to be remembered.

Ente

Why use salt in this case? Just include the salt in the phrase. :)

Do you think we need a measure against brute force attacks? If not, sha256 should be fine, IMO.

Yes, a standard deterministic wallet generation scheme would be very useful. Are there any shortcomings of Electrum's?

f you are going to rely upon using a computer to turn the passphrase back into a key anyway, then mightn't it be nice to make it take a bit of computing to do, like maybe take the hash of the hash of the hash, 10,000 or more deep? You'd memorise the phrase and also remember a favourite number or something, which, multiplied by 1000, or 10,000, or 100,000 or whatever, will be the number of times to iterate the hashing. This kind of multiple hashing is handy in general anyway for passwords, to make sure it takes a while per attempt. In act Unthinkingbit's bounty for a DeVCoin exchange explicitly requires the passwords have to be hashed at least 10,000 times (I think it was?) just so as to add this little bit of extra work anyone trying to brute force attack them will have to do.

-MarkM-

Yes, I agree to "do 10000 hashes of the phrase", but only if the number is given by the standard. Make it changeagle in "expert mode", if you like. But its trivial for a computer to generate 100000 times the hash of a phrase, and stop when one of the hashes matches a known address. It would not add security, but be another thing the user has to remember.

Ente

One way to do this (but does require you to remember 2 things) would be to have a pass phrase and a "pin" number (say 6 digits) where the pin is actually the number of times to hash the pass phrase.

As the main point of the PIN is just to harden the pass phrase from a brute force attack (where it is perhaps expected no information is known about whose pass phrase you are trying to crack) it doesn't really need to be so "random" (so could perhaps use birthdate or some other easily remembered number).

You could've put those digits in the passphrase itself, which would increase the required iterations much more.

gmaxwell convinced me that it is not safe to let users chose their passphrase.
this is why the passphrase used by Electrum is generated by the software.
it has 128 bits of entropy plus key stretching.

Good point - so perhaps the idea could just be to use something like name + bithdate + "x randomly chosen words" for the pass phrase.

This adds almost no security.


This adds security.


I dont believe it is that bad. Display how any bits are used in the user's passphrase, maybe with an estimate of how quick it could be cracked.

I, however, would be very sceptical of a program/service where the passphrase is generated for me, and that passphrase gives immediate access to substancial value. I would either skim through the sourcecode, or drop that program right away.

Ente

exactly. And then you are at the beginning, again, where the user is responsible to create a secure passphrase, by which means he chooses. If everyone uses the same (given) scheme to generate the passphrase, it gets substantially more insecure..

Ente

yes, such "displays" exist. they are all wrong.


do you trust a program just because it lets you chose a passphrase?

btw, Electrum uses two secrets: a key generation seed (generated from the 128 bits passphrase) AND an encryption password chosen by the user

Well, apparently Electrum accepts a longer seed, so it's possible to sha256sum some pass phrase and create a deterministic wallet using that (edit: I used the "restore wallet from seed" function). Is Electrum's deterministic wallet generation algorithm documented somewhere? I'm sorry if this question is redundant.

I've been working on a specification for deterministic wallets, to be included in the reference client (and Armory might adopt it as well). It is a bit more complex as it (optionally) supports multiple independent keypair chains, for different accounts and for public and non-public addresses.

It uses a 512-bit master key, but could very well be generated from a seed of only 128 or 256 bits of entropy (this is not yet specified). My preference would be having this part be generated randomly, to prevent weak user passwords resulting in entire wallets being exposed.If a nice standard can be agreed upon for converting such an amount of entropy to a human-readable (and hopefully rememberable) string, it could function as a very nice brainwallet.

The current draft can be found here (https://raw.github.com/gist/1799467/4a36177cb03792c046ac3f4f4be9f004d1d8865e/gistfile1.txt).

All wrong? So you say it is not possible to calculate the "strength" of a passsphrase in bits? Easy way: calculate the bits for a brute-force case, from length and keyspace. More clever way: Let the user enter a few additional infos, like "there are three real-world words in that phrase". I am not saying this is a must or necessarily worth the effort, but I don't agree "they are all wrong" at all.


Of course "I can choose my passphrase" is not enough by itself for me to trust it. But in such a case I could (and might) skim through the sourcecode. If there is nothing hinting it transfers data through the internet as well as it seems reasonable it does what it states (i.e. use the installed openssl libraries to make hashes), I am reasonably sure. If then I dont find any warnings online, find some recommendations, and use it on a live-cd, I feel safe enough to trust it with some value.

If said program creates the passphrase (or a list of words), it doesn't have to transfer any data online. If there is a backdoor which makes the combination of the words non-random, it is close to impossible to find in the sourcecode as well as close to impossible to detect in the created passphrase. I would (and did) read through sourcecode. But I will definitely not make a statistical analysis of so-called random passphrases a program generates for me.

I will not trust any program/service/page/algo if I can not reproduce the output with a different method. Easy with pywallet and the like, I verify its working as intended with online sha256- and Hex/Base56 generators. If both ways lead to the same privatekey, I use the program in a secure (offline) way to create the privatekey I finally use for funds.


Does that mean the user chooses a password and the seed is generated from this as well, or
the user chooses a password and gets an additional passphrase from the program?

Ente

Nice to hear you are on this as well!
Create a human-rememberable output from 256- or even 512 bit randomness? I dont believe this is doable in that way. The human-languages-keyspace would be too small or the resulting token ridiculously long. You could brute-force many random keys until you find one which has a corresponding rememberable token. But this would be no different to, for example, hash a human-rememberable token and use the hash as a pseudo-random key..

May I suggest KISS? :-)

Ente

indeed, Electrum accepts any seed if you chose to use the "restore from seed" function;
this method lets you bypass its 128 bits generated seed.

sorry but there's no documentation. the code is simple to read, though

no, the seed is not generated from the password.
the encryption password is only used to encrypt your wallet.

To access your money, you need :
seed OR ( wallet file AND password )

I think you misunderstood me. Internally, the scheme uses 512-bits keys (so its master is this large), but as secp256k1 (the elliptic curve used by bitcoin) has only (a bit more than) 128-bit security anyway, there is no need to use (much) more entropy for generating the master. One possibility is using master=SHA512(seed), where seed is a randomly generated 128 to 256 bit value. This seed could be converted to (or generated from) a human-readable string, if a nice standard for such a conversion can be agreed upon.

I don't think standardization is required because things like the key derivation function, parameters, rounds, and salt AREN'T SECRETS.  The important thing is to make sure they are well documented and stored in a variety of locations.

There should be sufficient documentation that the wallet could be recreated from scratch as summing the author, all his files, and all his work product are all lost.

Standardization is not intended to make public parameters implicit... it is intended to make its format compatible between different implementations.

However, it might be a good idea to write down how exactly the wallet was created. So the wallet could be recreated later, or even the program could be recreated to create the same wallet with the same passphrase.

Of course, the whole point is to not have a wallet, but a passphrase in memory. No idea where to write the instructions "how to recreate the wallet" in that case ;-)

Oh, I know! If its a standard, and all clients/services use the same way to create the wallet? duh!

Ente

Take a step back.  The reason for a brain wallet isn't just to avoid writing "something" down.  It is to avoid writing a SECRET down.  Once a secret is written down it can be compromised or lost.  

The implementation isn't a secret and having that "written down" (as in drop a copy in your google docs folder, drop box, filing cabinet, email it to yourself, etc) doesn't represent a risk of compromise.

A universal standard is like a utopia.  It probably will never happen.

I have used this cartoon before but it is (sadly) accurate.
http://imgs.xkcd.com/comics/standards.png

Maybe a universal standard will happen but I honestly doubt it.  There will always be differing opinions between authors on implementation aspects.  An interim goal would be to push that all deterministic wallets provide specific details (not code) on the entire process ("secret" -> set of private keys) in plain text format for archiving which would make reconstruction without any access to current code possible.  That would provide at least some level of disaster recovery in the event no existing wallet is compatible.

watching...

A kid's question:

A kid (9 years old) asked me why he can't make a long passphrase just repeating one letter, and I coudn't answer properly.

Example: kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkbitcoin
(30 k's and the word bitcoin)

As long as noone knows this "password generation scheme" (because it is the standard or someone watched me typing one key three dozen times and counting to 30) it doesnt make a worse password than another 37 random small-letter password.
You can either attack with a dictionary, permutations of words from a dictionary, or every combination through bruteforce. 30*k+bitcoin will only be found with brute-force, I would say.
Oh, but there may be funny details in your *implementation*. Like the old windows passwords as well as icq passwords would truncate after 8 letters.. ;-)

And, to add another heresy: I prefer to choose a long, strong password, and barely change it at all. Some of them I use for years now. If its only used for one login/website, I see no reason to change it at all, ever.

edit: I like that kid. Please buy it icecream and give it a hug.

Ente

But I do know the generation scheme:  Ask a human to generate a secure password.

This is something humans are not good at and so they are prone to doing things like ... picking passwords with a repeated character (or, alternatively completely avoiding repeated characters). For example, here are some of the cracked mtgox passwords (all except the Us were using the more secure freebsd crypt scheme): uuuuuuuuu, ggggggggggg, 999999999q, qqqqqq123, 111111111a, 999999999, 88888888, 99999999.

Uniformly probable uncertain length between 1-33 adds only 5 bits of entropy to the repeated character model.   Meaning that if you're already doing "every character repeated" (which is obviously a useful model which cracking tools already include) searching all of those lengths only increases your workfactor by 32.

WARNING
A new website popped up, that lets users generate addresses from their Electrum or Armory seed: http://brainwallet.org/

It is not clear who created that website.
I previously thought it was Joric, but he said he is not the author.

After a quick inspection, the javascript does not send your seed to a remote server.
However, nothing guarantees that the server will always send you the same javascript

In other words: this could very well be a phishing attempt.
If you ever used that website, move your funds to a new wallet immediately!

addendum to my previous post:
there is evidence that some people are "mining" for password-generated bitcoin addresses;
in other words, they are using the brute force of their computers in order to discover passwords.

if you use a deterministic wallet such as Electrum, do not trust yourself for inventing a seed that is complex enough; use the seed provided by the software.

One good little piece of standardization I'm seeing that has developed is that both brainwallet.org and bitaddress.org use SHA256(passphrase) for their single address generation. Now we just could use some standardization for the deterministic wallet idea. I really don't like how Electrum won't let you make your own passphrase.

Is the argument really along the lines of "You're too stupid to create your own password."?

Yes, because entropy is hard for most people to understand.

My approach:

PrivKey1: sha256 x5 "my long passphrase"
PrivKey2: sha256 x6 "my long passphrase"
PrivKey3: sha256 x7 "my long passphrase"
PrivKey4: sha256 x8 "my long passphrase"
etc.

I might forget that I started at x5 at some point, but it doesn't matter much.

Coincidently, I "tested" my passphrase some days ago, and could not come up with the details. Which order? Capitals? All capitals? Spaces in between?
I finally wrote down all combinations and tried them in a script. Yay for linux scripting. Not yay for how difficult it is to esthablish a secure solution intended for years and decades.. ;-)

Ente

PrivKey1: sha256("my long passphrase1")
PrivKey2: sha256("my long passphrase2")
PrivKey3: sha256("my long passphrase3")
PrivKey4: sha256("my long passphrase4")

anything wrong with that?

This is probably a bad solution, because as soon as sha256 x5 "passphrase" is known to the attacker, he gains knowledge of the other private keys, too.

In general I agree to what is said here: It's bad, if the software generates the password for you, for this reasons:

• Hard to remember
• User can not be sure, that the password is really genrated randomly: If it were, the software could take the self invented passphrase as (part of the) input as well.

The question is: How much bits of entropy are needed for a password to not be easily crackable by brute-force? How long does it take to try one possibility?
If you "mine" for private keys (by choosing random), there is always the chance to find one. But this chance is equal for all schemes for generating the private key.

Btw.: Entropy is not everything. If you generate your password from many words, which occur in a dictionary and the attacker knows that, all the entropy of single characters is worthless, because the attacker can guess your password with a wordlist.

You surely know "correct horse battery staple":
https://xkcd.com/936/

The there calculated 550 years (instead of 3 days) do *not* come from "attacker tries every possible combination of small letters up to 25 letters (that would be much much more than 550 years), but precisely assuming what you did, that the attacker has a dictionary with one-, two thousand words where he shuffles them to different combinations of four words.

I couldn't really believe it when I first thought about it, and found much more detailed calculations to exactly this example somewhere.

Ente

BTW entropy is everything you are just calculating it wrong.   If the passphrases comes from a dictionary list (and the person designing it will ASSSUME the attacker knows it) the entropy is (words in list)^(number of words)

i.e. if you have a word list of 5,000 words and generate a passphrase which consists of 10 of them randomly it would have

5000^10 ~= 2^122 or 122 bits of entropy.  (that assumes selection with replacement, too lazy to did the more common selection w/o replacement).

You are right, I thought only of entropy of single characters. What i meant was: Entropy of single characters is not everything.
Nevertheless, it maybe easy to remember 4 words, but to reach entropy levels of 128+ bits you would have to remember at least 12 words (assuming an alphabet of 2000 words). Remembering 12 words (randomly chosen, without grammar) is far more difficult.

Maybe instead of using 10000 rounds of SHA256 it would be better to use something like scrypt, to slow down the attack.

agreed however even a 6,000 word list has pretty common words.  Increases the size of the word list decreases the number of words required for a given strength.  I would also point out that key hardening can be used.  Most passwords have only 30 bits of entropy. 

60 bits of entropy in a 6,000 word list requires 5 words.    Using a chained iterative function (like PBKDF2) one can make it computationally in-feasible to brute force that 60 bit passphrase.  The downside (yes there is no free lunch) is the need to use salt to prevent precomputation attacks.  This will have to be recorded by the user.  Remember salt isn't a secret so it doesn't need to be safeguarded (use could email it to himself, print a copy and put it in a safe, put it in his drop box, and leave it in plaintext on his computer) but it does need to be recorded.

I haven't tried importing private keys into bitcoind(-qt) yet, but its pretty easy to sha256sum a phrase & feed it into brainwallet or bitaddress to get the private & public keys.  There's also a few transaction makers out there that will even give you the raw transaction (most only support sending the full balance tho - be careful or you might end up giving the miner a huge fee).  Now I just need to figure out how to send that transaction out.  I think bitcoind(-qt) is working on it since I saw they have a sendrawtransaction method.  I also heard electrum will do it.  I think blockchain will send it for a fee.  Then you don't even ever have to import or create a wallet & the private key can be stored on an offline computer the whole time.

All that stuff is bread&butter of Armory! :-)

Ente

Didn't think about that, but not too worried. I only use this for a cold storage/long term savings wallet that I don't plan on spending from any time soon, and the passphrase was hashed and bitcoind addresses generated on a livecd. I'll probably switch to this approach some day.

This sounds pretty good.  I might use a variant on that at one point.

To address the criticism that using one passphrase means the whole wallet is lost once the passphrase is gained, there's no reason you can't have multiple passphrases.  It seems to me that any deterministic wallet generation scheme is vulnerable if the seed is compromised.

Is there a tool that can be used offline that generates a public key from a sha256?  Preferably in javascript or shell script?

Bitaddress.org

You have the javascript from bitaddress.org (https://www.bitaddress.org) available, offline if you save the page to your pc


The Bitcoin-Address-Utility
https://github.com/casascius/Bitcoin-Address-Utility


Or Casascius-compatible address tool for Android
https://bitcointalk.org/index.php?topic=86128
http://codinginmysleep.com/apps/
https://play.google.com/store/apps/details?id=com.CIMS.BitcoinAddress

check out the strongcoin offline tx stuff, which is in js.

Why are people so obsessed with dictionary attacks. It's so easy add something into the passphrase which is not in a dictionary. Just missspell a word. If you speak a local dialect, use some words from that. I doubt it is easy to run a dictionary attack on a passphrase containing bits of Bavarian, Southern Thai or Islay Gaelic.

Or Igpay Atinlay  ;D

The Brain Wallet tab on bitaddress.org v1.6 uses SHA256(passphrase) as the algorithm.

I've kept it simple for the reason others have stated:
SHA256(SHA256("a")) is easier to brute force than SHA256("a2")

I'd like to make a FAQ with advise on choosing a good passphrase. But I don't know what IS the best advice. There are two threats that can cause loss of bitcoins with respect to Brain Wallets.
1) Hacker brute forcing the passphrase
2) Forgetting the passphrase

Does anyone have good advise?

I acknowledge what gmaxwell and others have said about the challenge of choosing a passphrase with sufficient entropy. However, there are valid use cases for Brain Wallets and I received bounties and requests for these features.

I think you misunderstand.   When we talk about dictionary attack we aren't talking about Webster's English dictionary.  We are talking about lists of passwords which have been collected over the years via a variety of methods (stolen password list, old brute forced password hash tables, major hacks, social engineering, keyloggers, phishing sites, etc).  I would provide some links but not sure if the mods would approve.  A password cracker will use a database of 2 to 14 million passwords which includes misspellings, brands/names, slang, common substitutions (p@ssword), prefixes/suffixes (password123).

14 Million is not nearly enough to cover even a few languages. I think your 14 million words pw cracker will not even crack something as ridiculously trivial as
"Casascius says: `vires in numer1s`"

Now do the  sha256 * YYMMDD hash of that to make it a bit of a computational challenge. (YYMMDD) being a date of significance for you.

In fact I think something like this is the best protection of even weak pass phrases: Going through an unknown, but very large number of re-hashes.

like trying to misuse a secret salt to add entropy, I think using multiple rounds of sha is just an excuse for (fear of) low entropy in the passphrase.

Just put enough entropy into your passphrase and all is good. Easiest way to do it: make it very long. Even a gramatically valid sentence constructed from 10 webster dictionary words wont be bruteforced easily (1E5^10 = 1E50). Even if the cracker uses grammar rules (unlikely), I bet there's still 1E40 gramatically valid sentences with 10 webster words.

The moment you put something personal into the passphrase, an attack that can crack your passphrase becomes an attack on *your passphrase exclusively*. Unless you have a very well funded brain wallet, the whole cracking enterprise is no longer economical. [EDIT:] using many rounds of hashing plus conditionals after each round pulls the teeth of SIMD & friends to an extend.

But I think a passphrase should not only be long, it should also force the attacker to use a vast dictionary of many Billion entries to even have a chance to crack it. I think most dictionary attacks completely loose their teeth if you mix languages like ລາວ, 中文, ไทย, or even Eλληνικά, particularly if the passphrase contains local slang in these languages.

So if everyone just makes good use of their native language this only leaves those out in the rain who speak only English. Fine.

+1 totally agree to this, using local slang with my passwords since 2000

Just downloaded some of these dreaded dictionaries. None of them would crack "Vires in Numeris",  even. Even if you use the very first sentence of a piece of world literature like:

"Uns ist in alten Mæren wunders vil geseit
von Helden lobebæren, von grôzer arebeit"

you're safe. Seems like dictionary designers have no knowledge that other languages exist.

I'm not sure you're looking at the same dictionary that "professional" password crackers use.

From the many password database leaks that have already happened in the past, there are known passwords of over 10 random-looking characters that have been cracked, presumably just from the leaked SHA hash. I don't have an example myself, but please don't just assume that because you can't crack something yourself, nobody can. Everyone is smart enough to devise a system he can't crack himself. Realize that the bitcoin network itself has done almost 2^70 SHA256 operations already, enough to traverse the entire space of up-to-11 characters alphanumeric passwords.

If you're really creating a wallet based on a passphrase, do the math. A word chosen randomly from a 5000-word dictionary provides 12 bits of entropy. Say you include randomly some words from one other language, given that there are 500 other languages and dialects, gives you 13*n+9 bits of entropy. I wouldn't advise using less than 128 bits to create a wallet, so that'd mean 9 words if you include foreign ones, or 10 if you don't. Please note that this calculation is assuming random words, and not existing text.

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


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.

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.

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.

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.

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.

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 (https://gist.github.com/2731997), but there is little explanation.

With a dictionary of 850 Basic English words (http://en.wiktionary.org/wiki/Appendix:Basic_English_word_list), 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.

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.

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.

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?

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

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.

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.

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.

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.

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

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.

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

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?

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.

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('<password><number>') 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.

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

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.

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.

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.

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

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.