Results of dictionary attack on SHA256 hashed keys

[scintill]

I'd been thinking about trying it out of curiosity for awhile, and last night that curiosity finally overcame laziness.  I hacked together a script to SHA256-hash every password in a large (14 million) password leak, compute the corresponding address, and scan the blockchain for transactions touching those addresses (using blockparser.)  Here are the results:

Code:

    Time (GMT)                  Address                                     Transaction                                                                    OldBalance                     Amount                 NewBalance
    =======================================================================================================================================================================================================================
    Wed Dec 28 15:03:43 2011    1LdgTMX2MEqdfT3VcDpX4GyD1mqCP8LkYe    fc04ba23dbe30e16f10a327fd0df43c5d3ce9a3bbf5cd12adcc869736552a626               0.00000000 +               0.02500000 =               0.02500000
    Mon Jan  9 11:12:34 2012    1LdgTMX2MEqdfT3VcDpX4GyD1mqCP8LkYe    ed2a5ca55d9f210fb8fdef4664366a191e0bbffd3c859def4716db1f2c0eb3b9               0.02500000 -               0.02500000 =               0.00000000
    Tue Jan 24 01:27:27 2012    1CLq46YiBtXy7N3nCbKYm4hsJm4Z3Gyqvg    9ee5b2f9ad804278916978e12d81d05638edccc0c08c8f676dee7724c7096013               0.00000000 +               7.33000000 =               7.33000000
    Tue Jan 24 02:00:12 2012    1CLq46YiBtXy7N3nCbKYm4hsJm4Z3Gyqvg    1693fbe8ddffa007883fd709ef58014d8ecfd2deb81e946aa5b4c315a9de9d45               7.33000000 -               7.33000000 =               0.00000000
    Tue Jan 24 02:00:12 2012    1CLq46YiBtXy7N3nCbKYm4hsJm4Z3Gyqvg    1693fbe8ddffa007883fd709ef58014d8ecfd2deb81e946aa5b4c315a9de9d45               0.00000000 +               0.03780000 =               0.03780000
    Mon Feb 13 23:02:59 2012    1TnnhMEgic5g4ttrCQyDopwqTs4hheuNZ     b64b38be136a75a5e377ede78a11c855b954c8c8cec5c7d1059406d050921dc6               0.03780000 +               0.01000000 =               0.04780000
    Wed Feb 15 22:12:10 2012    1TnnhMEgic5g4ttrCQyDopwqTs4hheuNZ     4a2781e4a5bfee9a206969c7f4f713c35a3bf04fbe586bb21deee5d9adb3baea               0.04780000 -               0.01000000 =               0.03780000
    Sat Feb 25 05:58:07 2012    13bJBfSQwxxZdauD5XMYH9qE2JA8FJzMhb    1bab5a3485bd778411c54f814fcbf40539fe4c2e30f1b75cb3aa23b854256761               0.03780000 +               0.11881188 =               0.15661188
    Thu Mar  1 00:37:26 2012    1CwjHYsPUc4Du8dx7AkdBJj4ebWC8bxkF3    e0b603cb002b127c14d85d4122f4d8b5f716e8162006842da8a17132ed5ade92               0.15661188 +               0.09408877 =               0.25070065
    Thu Mar  1 00:52:04 2012    1CwjHYsPUc4Du8dx7AkdBJj4ebWC8bxkF3    668e7db28be3a4692eb3cd3752b1d6f377d3badbef30c309b10571b85ce9ff74               0.25070065 +               0.04082466 =               0.29152531
    Thu Mar  1 02:32:56 2012    1CwjHYsPUc4Du8dx7AkdBJj4ebWC8bxkF3    c63b68fbee149517bf791ec4ee14952147a9862dbdd21f3d7394f1169de6795d               0.29152531 -               0.09408877 =               0.19743654
    Thu Mar  1 02:32:56 2012    1CwjHYsPUc4Du8dx7AkdBJj4ebWC8bxkF3    c63b68fbee149517bf791ec4ee14952147a9862dbdd21f3d7394f1169de6795d               0.19743654 -               0.04082466 =               0.15661188
    Thu Mar  1 02:32:56 2012    1CwjHYsPUc4Du8dx7AkdBJj4ebWC8bxkF3    c63b68fbee149517bf791ec4ee14952147a9862dbdd21f3d7394f1169de6795d               0.15661188 +               0.00000343 =               0.15661531
    Thu Mar  1 03:05:57 2012    13bJBfSQwxxZdauD5XMYH9qE2JA8FJzMhb    1fb52e8dd41bad3db3411def6a6295555a891206177f05cb5c0be702882cabc8               0.15661531 -               0.11881188 =               0.03780343
    Thu Mar  1 03:05:57 2012    13bJBfSQwxxZdauD5XMYH9qE2JA8FJzMhb    1fb52e8dd41bad3db3411def6a6295555a891206177f05cb5c0be702882cabc8               0.03780343 +               0.00081188 =               0.03861531
    Fri May 25 01:04:52 2012    1GgFf35J151a8ySkFwizqcZ4CWPqRHbf8A    e929f671328644af2773d540bbdf32492bd4ba8e1b47f619e015fed4ce995b79               0.03861531 +               0.10000000 =               0.13861531
    Fri May 25 02:13:08 2012    1GgFf35J151a8ySkFwizqcZ4CWPqRHbf8A    d388fc5c76da91352e487df7130bf55109995b722607ac1a477dd0404331ffcf               0.13861531 -               0.10000000 =               0.03861531
    Sat Jun 16 20:52:19 2012    1HKqKTMpBTZZ8H5zcqYEWYBaaWELrDEXeE    db4f2348b92b4cd34675df66b49855e66869d7e98eb97141e85b558c28390fb3               0.03861531 +               0.02000000 =               0.05861531
    Sat Jun 16 20:52:19 2012    1HKqKTMpBTZZ8H5zcqYEWYBaaWELrDEXeE    d1938c391461a6cd7a4ebbd206e68ee56b7b236a9d0af9c89134d4c59d4060b5               0.05861531 -               0.02000000 =               0.03861531
    Sat Jun 16 20:52:19 2012    1HKqKTMpBTZZ8H5zcqYEWYBaaWELrDEXeE    d1938c391461a6cd7a4ebbd206e68ee56b7b236a9d0af9c89134d4c59d4060b5               0.03861531 +               0.01000000 =               0.04861531
    Sat Jun 16 20:52:19 2012    1HKqKTMpBTZZ8H5zcqYEWYBaaWELrDEXeE    8fd2a66e4256dfaf57a74d8c01a2955d2ad3937c810b43278f507c02e4834ada               0.04861531 -               0.01000000 =               0.03861531
    Sun Jul 15 08:32:40 2012    19MxhZPumMt9ntfszzCTPmWNQeh6j6QqP2    1a370da20cbc7460c44a9b9c5835a956d178924d203a3ca84bc31362db1d3e08               0.03861531 +               0.01000000 =               0.04861531
    Sun Jul 15 09:14:33 2012    19MxhZPumMt9ntfszzCTPmWNQeh6j6QqP2    73fb441cd2a889e680733e6757594706e950484d119c2cbb721387f19900501a               0.04861531 -               0.01000000 =               0.03861531
    Wed Jul 25 13:27:34 2012    1CwjHYsPUc4Du8dx7AkdBJj4ebWC8bxkF3    949be1f0dfbf50a7085ae5331c42193d817c73dde5af27707a924d7768a66738               0.03861531 -               0.00000343 =               0.03861188
    =======================================================================================================================================================================================================================

    transactions  = 24
    received      =        7.79734062
    spent         =        7.75872874
    balance       =        0.03861188

Luckily the unspent balances are small enough that I'm not tempted to snatch them (I told myself I wouldn't when I started, but even those 7 bitcoins back in January are tempting.) It's also good for everyone's security that most of the transactions are small.

Here's some stories I found on some of these addresses:

I threw a few not-so difficult pass phrases into the block chain a while back, only '1LdgTMX2MEqdfT3VcDpX4GyD1mqCP8LkYe' has lost coins.

I imagine I've found some of the other addresses TTBit made.

I recently played around with this myself and found that SHA-256("test") has been used: http://blockchain.info/address/1HKqKTMpBTZZ8H5zcqYEWYBaaWELrDEXeE

Mounting a more sophisticated attack could get interesting, but I'm afraid of what I'll find.   Just remember to use strong passwords if you go the "brainwallet" way!

[DeathAndTaxes]

Interesting.

Salt would be a good countermeasure against this type of search and so would a key derivitive function (as opposed to a simple SHA-256) to massively increase the computational requirements.
For example using PBKDF2 if someone birthday was 01/28/1977  they could perform 1,281,977 rounds of SHA-256.  The average GPU would be able to brute force maybe couple hundred passwords per second.

At say 100 keys per second a 14 million password brute force would take about 1.6 days.  Combined with a 64 bit salt would require couple billion years.

You do illustrate that without salt and/or key derivitive functions, SHA-256 is simply too fast for using in this fashion.  The same vulnerability exists for password tables hashed w/ single round of SHA-256/512.  If you spent a couple weeks you likely could exhaustively search all 8 digit passphrases.  A botnet could burn off cycles checking 9 digit passphrases over the course of months.

[TTBit]

Cool!

Wish I kept better records. I think my 'salt' was an extra carriage return by mistake for my first few addresses.

[adamstgBit]

i dont get it.... did you get control over someones btc?

who is at risk for this attack?

[scintill]

i dont get it.... did you get control over someones btc?

who is at risk for this attack?

I have generated the private keys for all of the 8 addresses listed, by taking the SHA256 hash of passwords from a password list.  I didn't really keep a log of what the private keys were since I didn't intend to spend the coins.  If I had, I could import those keys into a wallet and spend the 0.03861188 currently in these addresses, as well as any sent in the future.

Technically, anyone receiving coins at these addresses is at risk, as well as anyone with similarly easy passwords (which have been warned about by anyone talking about this type of key.)  If you're using randomized wallets (official client default), or deterministic/"brain" wallets/addresses with a secure passphrase (even "I l0ve Bitcoin soo0 very much!!!1"*), you're not at risk for what I've done here.  I believe many of these wallets implement the features such as PBKDF2 and salts that DeathAndTaxes mentioned, making them more secure.

* Edit: Well, this isn't all that secure, but it's a lot more secure than "test", which is the password for 1HKqKTMpBTZZ8H5zcqYEWYBaaWELrDEXeE (now empty, although I'm not sure why my table seems to indicate it has .03 BTC... - the NewBalance column is the balance of all the addresses)

[rjk]

i dont get it.... did you get control over someones btc?

who is at risk for this attack?

The only people at risk are those that use a known passphrase as their private key. Any user that gets his addresses automatically generated by a client will not suffer from this problem.

[caveden]

Probably a stupid question but how much space would be needed for a db of every hash and value?

I'd guess more than all Earth's matter would be able to provide, since the amount of energy to calculate all that compares with the amount of energy the Sun can produce.

But, let the professionals answer you with some good math. ;-)

[Timo Y]

Salt would be a good countermeasure against this type of search and so would a key derivitive function (as opposed to a simple SHA-256) to massively increase the computational requirements.

What is the advantage of using a salt+password over simply using a fully random private key generated by the satoshi client?

The salt needs to be stored somewhere, and if you lose the salt you lose the coins, right?

Seems more sensible to me to store an aes256-encrypted wallet or private key than a salt.

[MagicalTux]

Actually if you go on MtGox, choose funding options, "Redeem Bitcoin private key" and input a string, it'll be sha256 and tested as a private key. MtGox will provide feedback if there was any coins there and any coin found will be credited to your account now and in the future.

This shows how dangerous it is to use a simple passphrase to generate a wallet as any bitcoin there can be snatched using existing tools...

[DeathAndTaxes]

Salt would be a good countermeasure against this type of search and so would a key derivitive function (as opposed to a simple SHA-256) to massively increase the computational requirements.

What is the advantage of using a salt+password over simply using a fully random private key generated by the satoshi client?

The salt needs to be stored somewhere, and if you lose the salt you lose the coins, right?

Salt isn't a secret.   While correct if you lose the salt you will be unable to reconstruct the key since salt isn't a secret it can be sent plain text, given to other people, stored in multiple locations (dropbox, google docs, computer, thumbdrive, printed in safe, etc).

Seems more sensible to me to store an aes256-encrypted wallet or private key than a salt.

In many instances it is however then it isn't a brain wallet.  Salt is simply a mechanism to add non-secret entropy.  It prevents the attacker (like OP example) from attacking in parallel against all potential users (and if Bitcoin becomes popular enough there may be billions) simultaneously.  It also prevents a scenario where you passphrase no matter how clever or strong may be chosen randomly by another user and your access to coins compromised.

[rjk]

I would consider a salt to be a "quasi-secret" that doesn't need to be treated with extreme care, but should probably not be posted in public or something. If the attacker knows the salt, he can start building tables before he attacks you, even though it's unlikely that he could get very far with that anyways.

[DeathAndTaxes]

Probably a stupid question but how much space would be needed for a db of every hash and value?

Well "every value" is simply an infinite number.

However to store say every passphrase using printable symbol on a standard keyboard (95) up to a length of 20 would be

95^20 = 3.58 x 10^39 records

If we assume no overhead and an average of 10.5 bytes for the input and 32 bytes for the hash that would be:

1.52 x 10^41 bytes
~152,356,517,023,630,000,000,000,000,000 1 TB hard drives.

The earth has about 1.3x10^50 atoms so even storing 1 bit per atom it would take up roughly a planet sized body.  Of course if the user had salt their hash wouldn't exist in your database.  To account for every 32 bit salt would require ~4 billion earth sized planets.

[Elwar]

Probably a stupid question but how much space would be needed for a db of every hash and value?

Well "every value" is simply an infinite number.

However to store say every passphrase using printable symbol on a standard keyboard (95) up to a length of 20 would be

95^20 = 3.58 x 10^39 records

If we assume no overhead and an average of 10.5 bytes for the input and 32 bytes for the hash that would be:

1.52 x 10^41 bytes
~152,356,517,023,630,000,000,000,000,000 1 TB hard drives.

The earth has about 1.3x10^50 atoms so even storing 1 bit per atom it would take up roughly a planet sized body.  Of course if the user had salt their hash wouldn't exist in your database.  To account for every 32 bit salt would require ~4 billion earth sized planets.

So you're saying there's a chance...

[DeathAndTaxes]

I would consider a salt to be a "quasi-secret" that doesn't need to be treated with extreme care, but should probably not be posted in public or something. If the attacker knows the salt, he can start building tables before he attacks you, even though it's unlikely that he could get very far with that anyways.

Sometimes salt is used a quasi-secret but that is generally bad practice.  A good crypto system is one where you can assume the attacker knows the alogorithm, the salt, the ciphertext/hash, and other details (like number of rounds) and still never be able to crack the secret.

If the attacker knows the salt, he can start building tables before he attacks you

The purpose of the salt isn't to prevent an attack.  It is to prevent the attacker from building a general solution.

For example SHA-256 of password is:
5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8

however the SHA-256 of "password|192386633" is
dc8b776a57bff42900f4c4e345731d4c2addeae4df957c45b06a6c8450cd612a

The 192386633 isn't intended to make the passphrase stronger.  That is the purpose of the passphrase.  The 192386633 is intended to make the hashing of passphrases useless for any other purpose than a specific attack.  Even known the salt serves this purpose.

Someone who feels that the salt needs to be non-public is either:
a) uninformed
b) feels their passphrase may be weak and is trying to compensate by adding more entropy via the salt

It is possible to produce secrets which can't be brute forced even when the salt is known if the following are true:
a) an algorithm which slows the throughput of attacker is used (single round SHA-256 is not secure for protecting passphrases)
b) a random salt of sufficient length is used (at least 64 bit but 128 bit is better)
c) a strong passphrase is used

[rjk]

All good points, but unless you want to burden users with annoying password requirements,

b) feels their passphrase may be weak and is trying to compensate by adding more entropy via the salt

is somewhat the name of the game for a public service. However, this can be alleviated by even just a few simple password requirements, so it's not much of an issue, just something to consider.

[DeathAndTaxes]

Just theorizing but I think most password requirements are worthless and are checking the wrong thing.

Personally if I had a site I would
a) use bcrypt which ensures passwords of 8 characters or more can't be brute forced
b) require passwords to be 8 characters
c) lookup user's attempted password against db of known/weak/leaked passwords and reject it if found.

No need for "Th!s is my @nnoyingly l0ng password333".

"happy clown jumper" all lower case can't be brute forced if protected by bcrypt and isn't on any password list used by hackers.

[check_status]

Probably a stupid question but how much space would be needed for a db of every hash and value?

3.123 * 10^877 gigabytes (for just one type of format, the private key, add public address and your needs almost double). More storage capacity than the NSA has.

Edit: My bad. I put an 8 were there should have been a 7.

[caveden]

Probably a stupid question but how much space would be needed for a db of every hash and value?

3.123 * 10^87 gigabytes. More storage capacity than the NSA has.

If your number is right, that's not simply "more capacity than NSA has". That's more gigabytes than some estimations of the number of atoms in the known universe.

[Rygon]

Probably a stupid question but how much space would be needed for a db of every hash and value?

3.123 * 10^87 gigabytes. More storage capacity than the NSA has.

If your number is right, that's not simply "more capacity than NSA has". That's more gigabytes than some estimations of the number of atoms in the known universe.

We can't store information at the sub-atomic level yet? Scientists be slackin'.

[elena.m]

Just theorizing but I think most password requirements are worthless and are checking the wrong thing.

Personally if I had a site I would
a) use bcrypt which ensures passwords of 8 characters or more can't be brute forced
b) require passwords to be 8 characters
c) lookup user's attempted password against db of known/weak/leaked passwords and reject it if found.

No need for "Th!s is my @nnoyingly l0ng password333".

"happy clown jumper" all lower case can't be brute forced if protected by bcrypt and isn't on any password list used by hackers.

TheirChildrensMiddleNames