Quote from: BubbleBoy on September 23, 2011, 09:43:13 PM

It's quite possible, depending on the algorithm used and the size of the attacker. The key-space for 9 characters is 6.37 x 10^17 so assuming it's a SHA256 salted hash then the current bitcoin mining network at 15THash/sec will exhaust the keyspace in 12 hours. The US government can probably do it in minutes. You could rent the current mining network for a small multiple of t 6*50BTC*5$ = 1500$/hour, assuming a market for cracking SHA256 hashes would exist.
To escape even the US government use a 16 character random password not generated by a human (no inter-character memory, characters are statistically independent). That is indeed hard to remember.

You obviously haven't heard of key strengthening. Nobody (including the bitcoin client) simple takes password -> SHA1 -> key. That would allow the average GPU to attempt 100 million to 1 billion passwords per second. An obvious an huge security flaw.

Instead you take password -> SHA1 -> output -> SHA1 -> output .... 10K iterations -> key. Now the number of permutations is limited by how fast you want the client to respond. An excel file for example does 17,500 permutations. The bitcoin client picks a permutation count that is dynamic depending on how fast the owners computer is. The goal is to increase the length of time to hash one password. The user isn't hindered. Do you really care if it takes bitcoin client 1.2 seconds to open instead of 0.00000000000000000000000000000000000000001 seconds? However by increasing the computation load to try one password you vastly reduces the effectiveness of attacker's hardware.

So your hypothetical example of 15TH/s exhausting the keyspace in 12 hours. that is for 1 hash = 1 key. If it is 10K hashes = 1 key then it isn't 12 hours it is 120,000 hours = 14 years. If it is 100K hashes per key it is now 140 years. Even if the govt had 100 TH of computing power it would take them over a year to crack. Here is the great thing .... adding a single digit would increase size of keyspace by a factor of 94x. So now 100TH would take almost a century. Even 1 PH would take a decade.

The bitcoin implementation goes a step even further by using dynamic key strengthening. Every time you set or change the password it sets the permutations of key strengthening based on current hardware. So as computer hardware gets faster your passphrase gets more difficult. Everytime you change your passphrase it changes the permutation count based on how powerful your hardware is.

If someday a bitcoin client uses GPU to hash the password well then the permutation count could be in the millions. In that scenario even a 15 TH network could only try 1.5 million passwords per second. Sounds like a lot but to exhaust a 9 random digit password would require over 12,000 years.

More info on key derivation functions:
http://en.wikipedia.org/wiki/Key_derivation_function
http://en.wikipedia.org/wiki/PBKDF2