torstai 7. maaliskuuta 2013

Small (con)test: hack my bitcoins and keep them

EDIT (2013-03-08 09:00 UTC): Extra hint 1: in the four unhacked passwords, there are no spaces, just words after words. Example: "juicestoryfootball".

EDIT (2013-03-08 11:35 UTC): Extra hint 2: all the passwords contain only Finnish or English (no mixing of two languages). And there is 3-4 words. Now, this is easy - maybe too easy :-). And the words are not very strange - I believe even every 14-year-old knows them.

On 20th of February 2013 I started a little test: I made five brain wallets with very stupid passwords. Their addresses are:
16XEzVyc34nYSQxsAjUmgY78qdAHBBKCy4 
1ECM1W1ZWtWDvTm3yWYWJA9mKn4Dwaaz1o 
14nRKoXJAUpKYYbzw6Yrqh9gW2p26zerpW 
1KRGyNbq2yM1vAXscib74Snp6AUuUHVi2g 
1Gu4VHM17SGHBN748k4ohNKy8BegySzyUF


Then, I deposited one bitcoin to each of them. My goal is to test, how fast the coins get robbed if the password is not strong. The fourth address was robbed in 7 hours - it's password was "lorem ipsum dolor sit amet". I did not tell anyone about my test - I wanted to know if there are people who scan brainwallets to steal the coins in them. Or: does it happen that some people just accidentally use same stupid password and find my coins and take them (I think this was the case with that lorem ipsum).

The rest of the addresses had not been hacked. Conclusion 1:
There are not a lot of people/scripts scanning for dumb passwords.
In order to test the wallets more I posted to Finnish bitcoin forum, to Bitcointalk and to Reddit that there are four wallets waiting for to be hacked. Now, after one and half days since posting to Reddit, the coins are still there. Conclusion 2:
Passphrase that seems stupid to me is still hard to guess or bruteforce.
I believe that if I waited for couple of weeks, all the coins would be gone. But because I'm impatient, here is a hint for passphrases:
  • they only contain English and/or Finnish words
  • only allowed characters are small letters (a-z) and spaces
  • as I said earlier, the minimum length is 15 chars
Well, now I'm disappointed if I still have my coins on next Sunday :-). Happy hacking!

33 kommenttia:

  1. It isn't that the password is hard to crack, it is trying to get the name of the identifier :'(

    VastaaPoista
  2. I didn't find your private keys but I found some other accounts which earned me so far 2btc. I highly doubt the security of the brain wallet system since a cracker can attack all brain wallets in existence at once.

    VastaaPoista
    Vastaukset
    1. Can you post the passwords for the wallets you "robbed"? Just for interest!

      Poista
    2. Just a few minutes of guessing using bitaddress.org. I don't remember the passphrase but I think it was some variant of "the quick brown fox ..." maybe with capital letters or without spaces. The address didn't have any bitcoins at first but I could see that it had been used for transfers just a few hours earlier so I added it to my wallet. A few hours later 2 btc showed up: http://blockchain.info/address/1MjGyKiRLzq4WeuJKyFZMmkjAv7rH1TABm

      Poista
    3. a few historically non-zero addresses:

      "" gives
      1HZwkjkeaoZfTSaJxDw6aKkxp45agDiEzN

      "Satoshi Nakamoto" gives
      1JryTePceSiWVpoNBU8SbwiT7J4ghzijzW

      "The Times 03/Jan/2009 Chancellor on brink of second bailout for banks" gives
      1Nbm3JoDpwS4HRw9WmHaKGAzaeSKXoQ6Ej

      "bitcoin is awesome"
      14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE

      "qwertyuiopasdfghjklzxcvbnm" gives
      17ac4moXPanV5QzuXRCiBs8uzRSjeSos3h

      Poista
  3. Pass-phrases that are gibberish are actually some of the strongest forms of security you can use. Pass-phrases such as "freely banana coats minun" are orders of a magnitude harder to crack than "WE_l0v3_L@MP" and also have the added benefit of being easier to remember. The beauty comes form the fact that it is easy to use, but hard to crack. What you must avoid is using phrases from songs books and movies, unfortunately many people are prone to do just that after ditching passwords for pass-phrases.

    VastaaPoista
    Vastaukset
    1. @SuperNatendo You're actually wrong. There are around 170,000 words in English. So the number all of combinations of 4 words is

      170,000^4 = 8.35 * 10^20

      If your password is made up of letters (lower, upper), numbers, and special characters (so 26 + 26 + 10 + 32 = 94), so the number of all 12-characer combinations is

      94^12 = 4.75 * 10^23

      So it's 3 orders of magnitude more safe to use random passwords, rather than passphrases made up of English words.

      Poista
    2. It's worse than that. Once you go over the ~30,000 most-common-word mark, you start getting some *seriously* obtuse words (especially medical terms) like "supraspinous" and "epipodiale". Using only thirty thousand words bumps you down three orders of magnitude when talking about the number of possible permutations.

      That said, your estimate for "random" passwords is also a bit optimistic, as in reality most passwords tend to just be normal English sentences (i.e. "we love lamp") with some 1337-speak variations ("WE_l0v3_L@MP"), though those changes are generally not predictable enough to bump it down below the entropy estimate for the "four random words" password.

      Poista
  4. Only 3,787,675,244,106,352,329,254,150,390,625 possible combinations(15 to the 26th power). Yep, we'll have this cracked in no time.

    VastaaPoista
    Vastaukset
    1. (15 to the 26th power) - where did you get that?

      Poista
    2. Minimum of 15 characters, and there are 26 possible characters, so there are 15^26 possible combinations. Except that we can have spaces too, so it's actually 15^27. Also, he said MINIMUM 15 characters, so this is only a lower bound.

      Poista
    3. Are you sure that wouldn't be 27 to the 15th power?

      one character with 27 possibilities would be 27^1

      two characters with 27 possibilities each would be 27*27 = 27^2

      etc.

      Poista
  5. Ok, now we have only about 5000^3 or 5000^4 different combinations to test (I'm not a linguist but I believe the words I use are in the 5000 most common words in English language). The extra hints are posted on the top of this blog post:
    EDIT (2013-03-08 09:00 UTC): Extra hint 1: in the four unhacked passwords, there are no spaces, just words after words. Example: "juicestoryfootball".

    EDIT (2013-03-08 11:35 UTC): Extra hint 2: all the passwords contain only Finnish or English (no mixing of two languages). And there is 3-4 words. Now, this is easy - maybe too easy :-). And the words are not very strange - I believe even every 14-year-old knows them.

    VastaaPoista
    Vastaukset
    1. Thanks for hint 2. My friend and I were able to build a dictionary and we're running through it now. I'm almost sure your password doesn't start with the word 'abacus.'

      Poista
    2. you probably should have calculated the odds first, theres actually quite many.

      Poista
  6. By the way: I would love to hear your performance results - how many passphrases your piece of code tried per second?

    VastaaPoista
    Vastaukset
    1. Using a pure python implementation I've been able to test around 4000 addresses per minute. This could obviously be improved. Just for fun I tried to run the same program on a dump of all addresses ever used in the blockchain until today. It seems that some people have used brain wallets generated from very short phrases ("you", "love", "very", "dog", "test", "TEST", "cat", "sausage", "QTC") but these have not been in use for months. Against this database I was able to do around 1600 tests per minute (with the slow python code).

      Poista
    2. still one left! Took me a while to get a C implementation going, I wanted to make sure it worked so I transferred some coin from mtgox to brainwallet and then brute forced and used the generated output to 'steal' my own coin back.

      I'm able to get ~120k guesses per minute with 4-cores: http://imgur.com/Lr5iTUz

      Now I'm about to lightup a 7-core system and we'll see how that does. Any more hints?

      Poista
  7. Bonus hint! One of the passwords can be cracked with this list: http://pastebin.com/anKcMdvk

    VastaaPoista
    Vastaukset
    1. Can you atleast give out how to get the identifier?

      Poista
  8. Why aren't people using a password hashing algorithm (e.g. scrypt, bcrypt, pbkdf2) as part of a brain wallet system?

    If you can remember a "magic number" of iterations to feed into these algorithms along with your passphrase, you can vastly increase the number of permutations of any given password.

    VastaaPoista
  9. Yeah! The second one (1ECM1W1ZWtWDvTm3yWYWJA9mKn4Dwaaz1o) is robbed few minutes ago ("unconfirmed transaction" says Blockchain.info)!

    VastaaPoista
    Vastaukset
    1. The password was fuckfuckfuckfuck. It's stupid, as I promised :-)

      Poista
  10. hey the story is the first one on hackernews front page:
    http://news.ycombinator.com/item?id=5349062

    VastaaPoista
  11. Short question: was the last broken address the one breakable using the provided dictionary?

    VastaaPoista
    Vastaukset
    1. If you mean that Simpsons dictionary, it was not on it. The word was very common one, though. (I'm not telling the password yet - if someone wants to take credit of it)

      Poista
  12. Great! Two more passwords hacked (passwords testingtestingtesting and aurinkoaurinkoaurinko [aurinko = the sun in Finnish - one of the most common "stupid" passwords in Finland, according to media]).

    I think that either the hacking of the password "fuckfuckfuckfuck" gave the idea to try combination with 3-4 same words or the tweet by security guru Mikko Hyppönen improvised some "real hackers" to grab the coins :-)

    VastaaPoista
  13. Hi. I got the one that was "fuckfuckfuckfuck" -- I wasn't even trying very hard to be honest, just familiar with the tendencies of people forced to pick passphrases/passwords on the spot. Not sure how to prove it, but thanks, I guess!

    VastaaPoista
  14. Got the "testingtestingtesting" after richards was disclosed, ran all common repeats for 3 and 4 words. Was running for a very big finnish dictionary too, but fell asleep before I could read the results. Looks like someone was there before me for the finnish combo...

    VastaaPoista
  15. i just found the last one (was "goatsegoatsegoatse"). really did not expect all passphrases to be of the same kind :). after spending quite a few cpu cycles on trying out random frequency-adjusted combinations of *different* words, i went for repeated words when i saw the solution to "fuckfuckfuck" here, but the other 2 addresses had already been depleted. i tried some more random combinations afterwards (figuring this is a "hard" passphrase), then repetitions again with a larger dictionary, which seems to have helped. fyi, the analysis was done on an i5-2430M with 8GB of ram using a quick-and-dirty python script based on https://github.com/willwharton/pybrainwallet/ (~1500 passphrases / second per core). not much crunching was involved in finding the actual passwords though.

    thanks for a nice challenge.. and for my first bitcoin ever :)

    VastaaPoista
  16. Hi ! I am in trouble with my personnal wallet, I lost the password :( I can remember some parts, but can't recover it.
    Do you know a software or script to brute force it ?

    Thanks in advance.

    VastaaPoista