Are Brain Wallets really a good idea?

[Kevlar]

It seems to me Brain Wallets are a terrible idea because they are susceptible to brute force attacks.

Here's what I would do if I wanted to hack brain wallets: I'd grab a dictionary or password file, SHA-256 these, multiply by the secp256k1 ECPoint G, SHA-256 and RIPEMD-160 that, and compare it to all the outputs in the block chain. I'd build this as a map-reduce function, and I'd farm it out. The list of all outputs wouldn't amount to more than a couple hundred megabytes, and for added interest, the map function could generate random permutations of combinations of the words, and the reduce could compute the hash and compare it to the list of outputs. Anything which resulted in a hit would be would be of potential interest.

Of course this is all hypothetical... Anyone interested in the results of having actually done this? And the code I used to do it? I'll let ya have it for the price of getting out of the Newbie section...

-Kevlar

[Kevlar]

Well it seems my bluff has been called! Anyone actually interested? Just say yes, and I'll write up a big post tonight.

[biosupdate]

Gavin Andresen recommends against using brain wallets here:

https://gist.github.com/gavinandresen/3840286


You also have to be very careful how you create and use a brain wallet. There have been many "brain wallet victims". One lost most of their balance by not specifying the change as a separate output in a hand crafted raw transaction and therefore turned it into a fee sent to the miners. One lost their balance by not realizing that the standard client sends the change to a new address, not the original. They then deleted the wallet.dat thinking that the change was safe back in their original brain wallet address. One lost all of their balance because the site they used to generate the brain wallet turned out to be keeping the private addresses.

[uberduber]

seems weird

[Anon136]

So long as you include a few made up words you should be protected against such an attack correct?

[Kevlar]

Ok, as promised.

So first of all: Why? Why pick on Brain Wallets?

I find large data problems and their solutions fascinating. I also love the design of the Bitcoin network, because it relies on the fact that randomly generated numbers are 'good enough' for a public addressing scheme. Brain Wallets are a kink in that otherwise unblemished idea, and while there's been people who have experimented with these techniques before, I wanted to take it to the next level and really see what could be done in terms of exposing weaknesses so I would have a better understanding of what would be required to actually hack random brain wallets. I can tell you that despite finding a few, I didn't take any of the coins. The amounts were small and they're probablly someone's mining earnings, and the amount you would get by taking them is about 1/100000th the cost of repeating the process here yourself. I've only provided the code, actually performing the experiment as described is left as an exercise to the reader.

So, without further adieu, here's the code: https://github.com/TSavo/BitKeyGrinder

What this code does is uses Hadoop to break down a large list of possible brain wallets into smaller chunks, and distributes those chunks for transformation into their equivalent brain wallet public key. There's another function for loading the block chain and scanning it for outputs that match from the resulting map/reduce job.

This is necessary because the function to compute the public key from the private one is prohibitively expensive... much more expensive than any of the hashing functions involved. On my Intel i5, I could get about 130 keys a second crunched, which meant I could do a 100 megabyte dictionary file in about a day and a half. Using Amazon's Elastic Map Reduce and the code linked above, I searched 15 gigabytes worth of public ally available dictionary files in about the same amount of time. Finding the keys in the blockchain took less than an hour on my i5 once everything had been downloaded again.

So, did I find anything?

Yeah, I did. It wasn't much though. Less than 1 BTC total. I left them there. And if you want to spend the money to go crunch 15 gigabytes of dictionary files to find that less than 1 BTC, good luck.

But let this be a cautionary tale: I churned 15 gigabytes of dictionary files in one day without exceeding my EC2 limit of 20 instances. If someone wanted to, they could start doing this full time, permuting 3 and four word combinations, and looking for brain wallets. Would it be economically viable? Nope. Would it potentially yield results? It would depend on how much CPU power you had... Food for thought.

Questions, comments, bit tips, and screams of agony are always welcome. I am a starving artist, and all tips will go to destroying my liver faster, and the occasional Bitcoin coding frenzy.

-Kevlar

[metraX]

I'm not clear - how do you check if an address has a balance? seems like you would have to rescan the whole blockchain, or query blockchain.info each time

[Kevlar]

I'm not clear - how do you check if an address has a balance? seems like you would have to rescan the whole blockchain, or query blockchain.info each time

What the second program, BitKeyChecker, does is scan the Block Chain and build a set of all Transaction hashes, ever. It then checks the hashed password against that set to see if the set contains it. If it does, it's considered 'interesting'. I was getting upward of 400,000 checks per second on my i5, and I suspect the problem is IO bound, not the custom hashmap comparator I wrote.

Once you found something interesting, you'd have to go rerun the blockchain yourself to see what the balance was... an exercise left up to the reader.

[Peleus]

Yeah already did this. But I just made a bitcoin address generator like vanitygen but used a password dictionaries as the seed rather than randomness. Created a long list of addresses. Using a block explorer you can extract every address with a balance in it. Compare the list.

Lesson - don't use brain wallets.

[astor]

It is actually not that hard to make a secure password.

What you need to do is use muscular memory.  That is, you type the password 100 times on your keyboard, and use it relatively often, and you will magically remember it.

If you have played an instrument like the piano, you know how a song can be "remembered" by your fingers.

How do I know this?  Well I created my passwords like this for many years.

On Linux, the command to use is this:

$ tr -dc 'a-zA-Z0-9,.' </dev/urandom | head -c 100
PSZ0pF64Mj4LYp7yIHcJixvRKLf5UcoMcCKM3S9Rryj.nL4Xnugbu1UNoIVHR63oBFssMfqI6UlfKQV CDTCNyWZCvFtTiUPVU78y

(it might give different results on your machine ;-)

In this case, the password will consist of the characters a-z, A-Z, 0-9, and '.,'.  You might want to include other special characters like ;,.!@#$&*()_.., or you might want to remove some to make typing easier.  It's up to you.

Anyways, we can calculate the entropy in the above passwords.  I conveniently chose 64 symbols so the entropy is 6 bits/character.

Thus we need around 20 characters to make a truly secure password.  This is actually not that hard to do, it just requires some practice, like playing the piano.

First, choose a part of the string above that you "like".  This reduces the entropy of the password by some bits, but the loss is bounded, so this is not a problem.  Then divide the password into sections and start practicing on the keyboard.

For example the first 20 characters can be divided like this:
PSZ0p F64Mj4LY p7yIHcJ

Then you practice the individual sections until they "stick".  Practice every day, like you are going to play a piano concert.

Good luck.  Being able to remember hundreds of bits of randomness is a skill that has great benefits.

[metraX]

What the second program, BitKeyChecker, does is scan the Block Chain and build a set of all Transaction hashes, ever. It then checks the hashed password against that set to see if the set contains it. If it does, it's considered 'interesting'. I was getting upward of 400,000 checks per second on my i5,

so how many seconds to check the set of all transactions?
(400k/sec, how many total are there?)

[Tal1m0n]

I take a phrase out of a book of poetry then add a series of numbers + capitalization on every other digit. Makes it very easy to remember and gives me a very hard to crack password.

The majority of the people losing their wallets however are due to being infested with malware. A fresh install of Windows, second partition for all your programs, then Deep Freeze the whole thing and you getting hacked is very unlikely.

[Kevlar]

What the second program, BitKeyChecker, does is scan the Block Chain and build a set of all Transaction hashes, ever. It then checks the hashed password against that set to see if the set contains it. If it does, it's considered 'interesting'. I was getting upward of 400,000 checks per second on my i5,

so how many seconds to check the set of all transactions?
(400k/sec, how many total are there?)

To check the set of all transactions for a given hash? I was able to do so against 400,000 random hashes a second. So how long does it take to check ALL transactions to see if a hash is interesting? Less than 1/400,000 of a second, after having loaded them all into memory.

[lostmyshit]

To check the set of all transactions for a given hash? I was able to do so against 400,000 random hashes a second. So how long does it take to check ALL transactions to see if a hash is interesting? Less than 1/400,000 of a second, after having loaded them all into memory.

are you saying, if I had a text file with 400,000 lines of text (guesses), you could turn them all into public addresses and know in 1 second if any of these 400k  are interesting?

[Kevlar]

To check the set of all transactions for a given hash? I was able to do so against 400,000 random hashes a second. So how long does it take to check ALL transactions to see if a hash is interesting? Less than 1/400,000 of a second, after having loaded them all into memory.

are you saying, if I had a text file with 400,000 lines of text (guesses), you could turn them all into public addresses and know in 1 second if any of these 400k  are interesting?

Well the whole point of the map/reduce thing was to first transform those 400,000 lines of text (guesses) into public addresses. This is what takes the time and computational power, and is by no means fast.

Once that work is done, and all the guesses have been transformed into public addresses, I can tell you in 1 second if any of those 400k guesses are interesting by scanning the block chain for all 400,000 of them in about 1 second.

That's what the code that I liked to does. BitKeyGrinder Map/Reduces the guesses into public keys, and BitKeyChecker checks them.

-Kevlar

[astor]

Isn't converting passphrase -> address just public key crypto?  That's at around 10k/s isn't it?

[molecular]

Yeah already did this. But I just made a bitcoin address generator like vanitygen but used a password dictionaries as the seed rather than randomness. Created a long list of addresses. Using a block explorer you can extract every address with a balance in it. Compare the list.

Lesson - don't use brain wallets.

no, that's not the lesson. "Use passphrase with high enough entropy for brainwallets" is the lesson.

[Dougie]

I like this! Interesting reading. Also amazing that you found some bitcoins using it since I was sceptical.

I don't think they're a good idea because I know how unreliable my brain is!

[CapnCrypto]

Wow, that's a very educational and interesting post, thanks for that Kevlar.

Sorry if these are newb questions but am I understanding right that once given a public key you can search through the block chain to find the holdings of the wallet associated with that key? Also, is it possible at all to find the public key associated with a certain BTC address? Just curious to understand the limitations of the BTC network.

[psylence]

Not the best idea