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

[tumak]

OP is correct, it's just matter of double sha256 + point multiplication + sha256 + ripemd160

Some ballparks assuming your password has 128 bit entropy (default for electrum, much less for armory?):

You can check ~32Mkey/s on hi-end ATI card. Assume attacker owns lots of resources at disposal, say 131,074 of such cards:

32M*128K = 2^25+2^17, in essence you strip 42 bits of input 128 bit brain wallet. 86 bits to go. Now let's assume he's going against all addresses at once, of which let's assume 16M are brain wallets, it does not matter which one he'll crack. Checking is O(1) (hash table). Thats another 24 bits (16M=2^24).

Your wallet is secured by 62 bits now for every second hypothetical attacker is attempting. ~29 bits down if he keeps trying for a year. You're left with 33 bits of security.

This number decrements by 1 every 18 months as per Moore's law. Attacker in year 2046 will find your wallet with 100% certainty in a year.

Of course he will find *some* wallet much sooner, when we'll account for the birthday paradox.

The security margin is still there, but it's pretty thin in the long run.

[btc6000]

Come on, how realistic is that that one attacker will have 131,074 high end ATI graphics cards at his disposal?

Assuming a 7970 uses 250W, that would consume 32.7685 Megawatts of power

Even if he did, it would be more profitable to mine with them.

[Dabs]

My brain wallet is some random private key in wallet import format. Just memorize all 54 characters.

[nwbitcoin]

This is a case of blaming the tools rather than the bad worker.

There is nothing wrong with brain wallets that a bit of thinking isn't going to fix.

Firstly, don't use all your words from the dictionary. Don't use all one language.

Use spaces, dashes, caps and lower letters and numbers

Don't use any phrase that already exists in print - anywhere!

"Luke, I am your father!" is out because its too short and well known

"Das freaky latino Hound, @Nellie with de supahuge bazookas - 9021oh,oh!"

Can you remember that? - Now convert it to a brain wallet address, and search the blockchain to see if it exists before you start using it!


Its not brain wallets that are faulty - its brains!

[soonerjoe]

This is a case of blaming the tools rather than the bad worker.

There is nothing wrong with brain wallets that a bit of thinking isn't going to fix.

Firstly, don't use all your words from the dictionary. Don't use all one language.

Use spaces, dashes, caps and lower letters and numbers

Don't use any phrase that already exists in print - anywhere!

"Luke, I am your father!" is out because its too short and well known

"Das freaky latino Hound, @Nellie with de supahuge bazookas - 9021oh,oh!"

Can you remember that? - Now convert it to a brain wallet address, and search the blockchain to see if it exists before you start using it!


Its not brain wallets that are faulty - its brains!

And don't use the same password for anything else.

[Kevlar]

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.

Yes. Download the code I linked to and look at BitKeyChecker. That's what this does. It reads the block chain off disk, putting all the transaction hashes into a set, and then searches that set. You could easily enhance it to be a map back into the blockchain for really fast lookups directly into the block chain.

As for finding the public key for a given address... I think it's gotta be included in the transaction?

Someone with a better understanding of the Block Chain format would be better qualified to answer that. I know the address is the ripemd160(sha256(pubkey)), and that the output/input pairs have to be signed with the output's private key, demonstrating that the holder of the private key/outputs was the one who is creating the transaction (aka sending the bitcoins), and I know the network is smart enough to verify all the parameters of the transaction or it will be rejected (can I just tell you how many times I've gone, "Why isn't it working?" because I've screwed up the construction of a transaction in code? Watch your change addresses and square your totals kids!) including the fact that the signatures generated can be decrypted by the public key that generated them and compared against the outputs->input/amount pairs, but I don't know what the trick is to go from address to public key for that operation unless it's in the transaction itself. Can anyone jump in here?

-Kevlar

[Kevlar]

Assume attacker owns lots of resources at disposal, say 131,074 of such cards:

Let me just stop you right there and let's do the math on that. Have you multiplied 131,074 cards by $600 dollars? I have... to the tune of 78.6 million dollars. Did you account for inflation? Or even consider the fact that this guy already spent the 78.6 million dollars back in 2013 trying to do this the first time, and now he's poor and old, and his liver is failing from him drinking too much when he was in his 30's?

Please... think of the Hugh Manatee! Guys, I'm never going to reach 78.6 million dollars by 20XD at this rate if you don't tip. Like my code? My address is in my sig...

[metraX]

"Das freaky latino Hound, @Nellie with de supahuge bazookas - 9021oh,oh!"

 

Aww, no coins in there

[ATC]

I dont' think brain wallet is so good. The brain randomness maybe doesn't have so big entropy.

[MiningUnited]

Just saw this "brain wallet" reference on the News. To the average Joe, they are even more like wtf? 

[zzz321]

If you aren't using your grandma's name or mother's maden name, or you dog's name etc. You can come up with a solid Brain Wallet. When it comes to procedures for any form of security, especially if it is of some value to you, you should put in the effort to come up with abstract parts to protect your assets.