Really poor headline. This has nothing to do with hacking SHA1: it's just a dictionary attack on the passwords in question.
SHA1 (and MD5 and similar constructions) are especially vulnerable because they are fast to evaluate (OpenBSD's Blowfish scheme and cperciva's scrypt feature a scalable amount of work), but this is not a break of SHA1 per se.
Still, a nice demonstration of what GPU programming can do.
there's a difference between brute-forcing all possible key combinations and brute-forcing various passwords on a (huge) wordlist.
Brute-forcing all keys will have you check 730750818665451459101842416358141509827966271488 possible keys in average.
Using a dictionary will have you check however many words are in your list.
If course the first method will give you a 100% chance of eventually finding the key, but it will take a very long time.
Brute-forcing the dictionary will take a very short time, but you won't have a 100% chance of finding the key (if it's not on the list).
Now, there might be some mathematical problems in the SHA algorithm that lowers that astronomical number of tries you have to do for a real brute-force attack, but there are none currently known and even with all the parallel GPU power, checking all those keys would take years. Not minutes.
the "attack" was using a dictionary. Salting would certainly defeat that, so he'd have to brute-force the key-space which would take years despite the parallel GPU power.
If the observation made here was "this guy got unrealistically impressive results because he was able to parallelize across every password hash", I'd agree.
But the observation was instead "this attack worked largely because the passwords weren't salted". No, false. This attack set a price of $1.62 per password using the simplest available GPU cluster resource. In no definition of cryptographic security is $1.62 a reasonable threshold.
Scrypt, bcrypt, or PBKDF2 can increase that cost factor to many tens of thousands of dollars per password without incurring appreciable costs to the applications using it.
18 comments
[ 5.3 ms ] story [ 54.5 ms ] threadSHA1 (and MD5 and similar constructions) are especially vulnerable because they are fast to evaluate (OpenBSD's Blowfish scheme and cperciva's scrypt feature a scalable amount of work), but this is not a break of SHA1 per se.
Still, a nice demonstration of what GPU programming can do.
Brute-forcing all keys will have you check 730750818665451459101842416358141509827966271488 possible keys in average.
Using a dictionary will have you check however many words are in your list.
If course the first method will give you a 100% chance of eventually finding the key, but it will take a very long time.
Brute-forcing the dictionary will take a very short time, but you won't have a 100% chance of finding the key (if it's not on the list).
Now, there might be some mathematical problems in the SHA algorithm that lowers that astronomical number of tries you have to do for a real brute-force attack, but there are none currently known and even with all the parallel GPU power, checking all those keys would take years. Not minutes.
More details here: http://www.theregister.co.uk/2010/11/18/amazon_cloud_sha_pas...
No.
it doesn't help against a single hash, but for multiple hashes you scale up the amount of work required by the number of salts in use.
But the observation was instead "this attack worked largely because the passwords weren't salted". No, false. This attack set a price of $1.62 per password using the simplest available GPU cluster resource. In no definition of cryptographic security is $1.62 a reasonable threshold.
Scrypt, bcrypt, or PBKDF2 can increase that cost factor to many tens of thousands of dollars per password without incurring appreciable costs to the applications using it.
http://stacksmashing.net/2010/11/15/cracking-in-the-cloud-am...
If these were salted hashes or even just better passwords he'd still be calculating. And he'd STILL be calculating years from now.