Topic: Are Brain Wallets really a good idea? - page 2. (Read 2812 times)

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

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,.' 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.

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.

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.

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

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

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

seems weird

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.

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

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