A wish: if you have written a fast program for cracking brainwallets (C/C++, CUDA etc.), I'm glad if you share them.
In my small brain wallet hacking contest, all wallets have now been hacked. The addressess, passphrases and hacking times are:
- 16XEzVyc34nYSQxsAjUmgY78qdAHBBKCy4 2013-03-10 19:10:32 goatsegoatsegoatse
- 1ECM1W1ZWtWDvTm3yWYWJA9mKn4Dwaaz1o 2013-03-09 21:36:02 fuckfuckfuckfuck
- 14nRKoXJAUpKYYbzw6Yrqh9gW2p26zerpW 2013-03-10 10:54:16 aurinkoaurinkoaurinko
- 1KRGyNbq2yM1vAXscib74Snp6AUuUHVi2g 2013-02-20 21:04:09 lorem ipsum dolor sit amet
- 1Gu4VHM17SGHBN748k4ohNKy8BegySzyUF 2013-03-10 08:24:40 testingtestingtesting
I deposited one bitcoin to each of the addresses at 2013-02-20 about 14:00 UTC. My original idea was just to put the bitcoins in, tell nobody and take the coins out (if they are lefy) after one month and then write a blog post about it. As you can see from the list, that lorem ipsum one was robbed after 7 hours from deposit.
To test a little the ease of guessing/hacking the passwords, I annnounced in the Finnish bitcoin forum, in Bitcointalk and in Reddit that I'm running a small hacking contest. (By small I mean that the prizes are two-digit numbers in euros/dollars.) I told that the passwords are 15 chars at minimum (the default minimum in Bitaddress), they can contain only small chars (a-z) and spaces and the words are in Finnish and/or in English.
I thought the addresses would be hacked very fast, but I was wrong. I had to give a number of hints on the way:
- there are no spaces, just words after words
- English and Finnish are not mixed
- the phrases only have 3-4 words
- the words are very common
After publishing these hints, it still took over 48 hours to crack them. The reasons, in my opinion are:
- There was no ready fast program for cracking brainwallet passwords. People were running slow Python scripts. With a well-written program in C/C++ and using a GPU, the cracking would take only hours or less.
- And: because the prizes were small, no superguru programmer/hacker wasted his/her time to write and run this kind of program.
- No one guessed (except for him) that the password repeated many times. I tried to mimic a common "stupid" behavior, which people use if there is a minimum character limit for password: repeat the initial password given.
Some interesting notices:
- People reported that they had found some other wallets with small amount of bitcoins accidentally (claims only, no proof, but I can believe it).
- With a quick-and-dirty Python script you can test 1500 passphrases in one second per core. That means that to crack a four-word passphrase with 10000 words vocabulary and 10-core CPU will take ((10000^4)/1500/10)/(60*60*24*365)=21140 years. If you use C/C++, speed optimize your code and use GPU and get a 100000-times speedup [1], it's two months. Now, if you either:
- add fifth word
- use punctuation characters between words and maybe add one or two capital letters
- mix two languages
- preferably do all of the above
you have a virtually bulletproof passphrase. - I was positively surprised for the attention this small project got:
- Mention by Mikko Hyppönen in Twitter
- Being the number one in Hacker News front page on Saturday.
- Getting positive votes and buzz in Reddit
- About 15000 visitors in my blog in three days (Fri-Sun)
Thank you for all!
[1] That number is from my hat - a high-performance computing professional could tell me, what is the correct number.
Again, I think it's worth stressing that the cracker does not need to target a specific brain wallet. If your numbers are correct the cracker with the 10-core CPU will have in two months broken every brain wallet with a four-word password ever used in a transaction.
VastaaPoistaIn that case the problem is to verify if there are any bitcoins stored in that particular address.
PoistaThat is true, but you can easily 'salt' the password by adding personal information (dob,zip etc) into the passphrase. Then you're working each solution in personal space.
PoistaAlso the absolutely easiest solution is to increase the word count to 8-12 words, decreasing the chance someone accidentally finds your address.
With an extreme case 18 words and a 20000 word dictionary your passphrase is now approaching 1/(1e77) or the correct atom in the entire universe, which is far more than the number of possible addresses (2^160 ~ 1.46e48), i.e. This is why 12 words (10k^12) is typically considered sufficient (1e48) as it has the same entropy as a bitcoin address.
The Electrum client for example uses a 12 word combination as a seed for its deterministic wallet which is estimated at 128 bits of entropy (3.4e38), generally considered sufficient for now and the foreseeable future.
Thanks for adding to the perception that Bitcoin can be cracked.
VastaaPoistaI managed to write one in C which can do about 2500/second per core on a 3.5GHz i7 regardless of how many addresses you are checking against (I loaded four million and was still getting 2500 passwords checked per second). The elliptic curve point multiplication needed to derive the public key from the private takes the vast majority of the CPU cycles.
VastaaPoistaThere is a brain wallet with password 'icecream' that I was found, plus a few more. None of them ever held coins for very long.