4 ms·

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 construct

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.

goldenthunder 16y ago
Actually brute forcing is exactly what he is going. But grabbing people's password hashes isn't really 'easy' w/ a well designed system.
- pilif 16y ago
  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.
markpercival 16y ago
It turns out the 10 passwords he 'hacked' were in the range of 1-6 characters. More details here: http://www.theregister.co.uk/2010/11/18/amazon_cloud_sha_password_hack/ http://www.theregister.co.uk/2010/11/18/amazon_cloud_sha_pas...
- blibble 16y ago
  If he had just Google'd the hashes he'd have saved himself $2, considering there was no salting.
  - tptacek 16y ago
    The point is that "salting" doesn't slow down the GPU attack.
    - pilif 16y ago
      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.
      - tptacek 16y ago
        Exactly how do you think a salt defeats a dictionary attack?
      - cperciva 16y ago
        the "attack" was using a dictionary. Salting would certainly defeat that No.
      - blibble 16y ago
        (in response to tptacek below) 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.
        tptacek 16y ago
        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.

goldenthunder 16y ago

Actually brute forcing is exactly what he is going. But grabbing people's password hashes isn't really 'easy' w/ a well designed system.

pilif 16y ago
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.

markpercival 16y ago

It turns out the 10 passwords he 'hacked' were in the range of 1-6 characters. More details here: http://www.theregister.co.uk/2010/11/18/amazon_cloud_sha_password_hack/ http://www.theregister.co.uk/2010/11/18/amazon_cloud_sha_pas...

blibble 16y ago
If he had just Google'd the hashes he'd have saved himself $2, considering there was no salting.
- tptacek 16y ago
  The point is that "salting" doesn't slow down the GPU attack.
  - pilif 16y ago
    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.
    - tptacek 16y ago
      Exactly how do you think a salt defeats a dictionary attack?
    - cperciva 16y ago
      the "attack" was using a dictionary. Salting would certainly defeat that No.
    - blibble 16y ago
      (in response to tptacek below) 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.
      - tptacek 16y ago
        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.