What people currently refer to as a "brainwallet" is simply a passphrase run through a single SHA-256 and then the result is the private key for a bitcoin address. The problem here is that an attacker can download the blockchain and then run very fast attacks basically hashing any text they can find to see if it hashes to a key which has some bitcoins. And when they find one, they drain that address. They can do this very fast since a single SHA-256 is quite cheap. This leads to sadness.
An awesome answer is key stretching. The short version is that a function is used to make it more time complex to test a key. As a simple example, lets say rather than SHA-256 once, it is SHA-256 a million times. That means it is a million times more expensive for an attacker to test each possible password. Then you make it even better by adding in something unique to the user. This makes the attacker have to do much more work as each different salt uses a different input on its million SHA-256 operations.
Key stretching is usually discussed in terms of a user entering a password to gain access to something. In that situation, the user is only willing to wait a short amount of time (maybe a few seconds at most). For bitcoin users protecting their wealth, this isn't nessesarily a concern. If an address is used a long-term offline storage a few minutes might be a tolerable delay. That means we can get a little silly. Why stop at a million hashes when we could do 300 million and make each attack really expensive?
Also, people have computers with multiple cores. Why not use them all? The key derivation functions usually used are serial in nature. You get the output from one operation and use that in the input of the next. But there is no reason we can't construct a tree of them and use all our cores. In this proposal, a first pass PBKDF is run to give us a large key. This key is broken up into a segment to be used by each thread. Then the threads do their own PBKDF and then all the results are combined to do a final PBKDF to give us our final key. The thread work can be paralellized or even distributed to multiple computers if you are so inclined.
Our objective here is to cost an attacker as much CPU time as possible while keeping the user wall time 'reasonable'. Lets say our attacker has 1000 cores at his disposal. If each password try takes 3000 CPU seconds, it doesn't matter to him if it is parallel or single-threaded. If it is parallel, he runs it on his cores. If it is single threaded, he runs it on one core and tries 999 other passwords on the remaining cores. In either case, his limiting factor is how many cores. However, for our user who just has one password to run and multiple cores, parallelism reduces his wall time (how long he is looking at his watch waiting for this thing to finish) without making it any easier on the attacker. So parallelism is a clear win for us in terms of costs.
I've picked numbers to make use of at most 256 cores and takes about one minute on a fairly modern setup. I've specifically made the numbers not easily tunable because if you use different numbers that is one extra thing you need to remember to recover your key.
Algorithm: Scrypt
First Pass: {CPU Cost: 16k, memory: 1, parallelization: 64}
Multithread Pass: {CPU Cost: 64k, memory: 1, parallelization: 64}
Last Pass: {CPU Cost: 16k, memory: 1, parallelization: 64}
Uses about 2gb of when all the threads are running.
So a modern 12 core machine I'm using to test can do all of this in about 60 seconds. Lets say this is equivelent of an Amazon EC2 c3.2xlarge which costs $0.60 an hour. Lets also assume that someone can build their own computers or rent them elsewhere but the price will be about the same. So this gives us the nice round number of $0.01 per password try. So my challenge key below has 2.6 million posibilities, even with me giving away the exact salt, the number of words where the words from from. So it could cost an attacker on average 2.6e6 * 0.01 * 0.5 = $13000 USD to find that key and get the 0.5 BTC.
I expect someone will do it anyways but probably more for fun that profit. Two words is just too weak.
Maybe they can get that down by 10x using big FGPAs (big enough to run memory intensive scrypt. This still means that even with this weak password of only two words, most likely no one will ever bother to find it. Of course computers get faster and the price of Bitcoin changes so build in some buffer.
My recommendation would be to use something like Correct Horse Battery Staple and using 4 or 5 words.
Password: warm effort Salt: fireduck@gmail.com Salt bits per thread: 256 Please enter salt (recommendation: use your email address): fireduck@gmail.com Threads: 256 Please enter password: Starting header passes... Running threads: ................................................................................................................................................................................................................................................................ **************************************************************************************************************************************************************************************************************************************************************** Starting final passes... Completed 16809984 cost in 71.4 seconds, 235323.1/s Key: 91aa46aff3d3a8460ad1638d8f7793a2
When used as a brain wallet password: 1Gnqxg5UnmV2o7UJhG2NgnXDbsFZaj61GH
When used as an Electrum seed:
Master public key: aae15b99e855520cb77877c8cf10e51836d0c47e5479f152999db52b5c40eb43fdf05f610bd1be4a5e1722afb55bcb681a5914e33080bef7c952443141ff4c60 Seed words: dad teeth voice frustrate leaf green grin mutter much train weave everywhere
Password: steady concern Salt: jimbo Salt bits per thread: 256 Please enter salt (recommendation: use your email address): jimbo Threads: 256 Please enter password: Starting header passes... Running threads: ................................................................................................................................................................................................................................................................ **************************************************************************************************************************************************************************************************************************************************************** Starting final passes... Completed 16809984 cost in 70.6 seconds, 238239.9/s Key: e15798fb09bd7954ed01ffb034bfbcea
When used as a brain wallet password: 1PfjEX2ipzgWSPY7MTbDZhXmY8J2TV96Kk
When used as an Electrum seed:
Master public key: 4660c0a22b3080a6e92d233bf6d3a5e54c8949e0d23693d35530a523d2c24e783455e256218e1552b72e2653706b49feb1f1e281829dab26384a864678027d01 Seed words: death believe dish bag completely belong real air leave shore however creep
I have stored 0.5 BTC in an address derived using this method. The salt is 'fireduck@gmail.com' (just like the example test vector #1). The password is two words from the Electrum word list in lower case with a single space between them (just like in the test vector).
Whoever finds the password first is free to take the bitcoin. My guess is that no one ever will without using many more CPU years than it is worth. It is only 2.6 million possibilies. (1626 words)^2
Here is the address: 19aREH3jaDba1xt14zhaUvzyAhzphdAwJN
This sounds suspiciously like math. Math can't lie. You had me at 'bitcoin'. How do I use this thing already?