5 ms·

See previous discussion here: https://news.ycombinator.com/item?id=12409530 https://news.ycombinator.com/item?id=12409530 Notably, the passwords were stored as

by jffry 10y ago

See previous discussion here: https://news.ycombinator.com/item?id=12409530 https://news.ycombinator.com/item?id=12409530 Notably, the passwords were stored as unsalted MD5 hashes, which even in 2012 was known to be a poor idea.

thatdude 10y ago
Thanks for reminder. Likely couldn't crack these in SHA-1 (or without substantially more effort), let alone some of the more new age hashing algorithms. Still, it's impressive.
- mrb 10y ago
  Unsalted SHA1 is just as easy to brute force as unsalted MD5. There is maybe a ~30% speed difference. Now adding a salt would have made it ~2 millions time harder for these ~2 million unique passwords.
  - creshal 10y ago
    On a 2012 laptop with john 1.8: • 24 million tries/second for unsalted MD5 • 18 million tries/second for unsalted SHA1 • 80,000 tries/second for crypt-md5 (state of the art… in 1995) • 2400 tries/second for bcrypt (already becoming obsolete in 2012) • And a tremendous 100 tries/second for scrypt (then state of the art) So yeah, the ~30% performance hit roughly fits. But even md5 can be used much more intelligently than just salting, and would have been available in major programming languages.
    - Sami_Lehtinen 10y ago
      Still scanning the MD5 key space 2^128 would take a while to brute force passwords. Of course it only takes time. But a lot of time. SHA1 is better, because it's 2^168 options. Also there's a problem, what if the data isn't in single block. Then you might find collision, but that collision might include something which can't be put in the password field, and therefore doesn't solve the problem. MD5 for PQKDEj52vGQVKudQaBMSewJ5MMifgaVxNYK9zsRTxMzBkyvompLMtgYCYv6SNzDE is cd5480cf1ad1cf7fab3aedbc6495609d. I would love to see someone to reverse that. Even if you find the colliding hash with sorter set of input bits. It's highly likely, it won't be in the acceptable character set. Or am I getting something wrong?
      - creshal 10y ago
        > Or am I getting something wrong? Yes, we're talking about passwords, not private keys. Virtually all passwords found in the wild have a massively lower entropy, so the amount of possible hashes doesn't really matter, only how long it takes to iterate through our much smaller password space. The longer that takes, the less attractive it is for attackers to try and brute-force people's passwords so they can try them on other services.
- nothrabannosir 10y ago
  Unsalted MD5 is not that much worse than unsalted SHA-1 in this case. Afaik the only vulnerability MD5 has over SHA-1, fundamentally, is that MD5 has easy collision exploitation. But that doesn't matter when bruteforcing passwords. * I'm not 100% on this, but let's be bold :) please forgive me if I'm wrong.
Houshalter 10y ago
This is a stupid question but how is it possible to reverse such long passwords from even a poor hashing algorithm? Even if the hashing algorithm is super fast, testing all combinations up to dozens of characters should still be impossible. And isn't there the possibility of collisions, so that even if you find a string that maps to the same hash, it might not be the original password?
- Pikago 10y ago
  They were obviously testing for combinations of words and not combinations of single characters. They might even have tested plain sentences. Still very impressive. After all, the leak dates back to 2012. I wonder how much time did the first one take for example. I think strings that maps to the same hash are just inintelligible garbage. If you find something that looks like human then it's certainly the original password.
  - kijin 10y ago
    The first one is the title of a song [1]. The attackers probably have a lot of common phrases, song titles, and other catchy excerpts in their dictionary. [1] https://www.youtube.com/watch?v=I915tOiR9sM https://www.youtube.com/watch?v=I915tOiR9sM If it weren't a song title, it would probably have been impossible to crack. That sentence has 12 words. People say that most English conversations only use 3000 words. 3000^12 is 2^138. It has quite a bit more entropy than what we can crack nowadays. Besides, "stripper" isn't part of the 3000-word dictionary.
    - nzp 10y ago
      Those 3000 words are not random in natural language. If they were your calculation would be correct, but they aren't so the actual entropy of the system is likely nowhere near 138 bits. In other words, song title or not, if the sentence was an actual sentence the entropy is much lower. To get maximum entropy out of sets of words you have to use something equivalent to Diceware.
- deleted 10y ago
  [deleted]

by jffry 10y ago

thatdude 10y ago

Thanks for reminder. Likely couldn't crack these in SHA-1 (or without substantially more effort), let alone some of the more new age hashing algorithms. Still, it's impressive.

mrb 10y ago
Unsalted SHA1 is just as easy to brute force as unsalted MD5. There is maybe a ~30% speed difference. Now adding a salt would have made it ~2 millions time harder for these ~2 million unique passwords.
- creshal 10y ago
  On a 2012 laptop with john 1.8: • 24 million tries/second for unsalted MD5 • 18 million tries/second for unsalted SHA1 • 80,000 tries/second for crypt-md5 (state of the art… in 1995) • 2400 tries/second for bcrypt (already becoming obsolete in 2012) • And a tremendous 100 tries/second for scrypt (then state of the art) So yeah, the ~30% performance hit roughly fits. But even md5 can be used much more intelligently than just salting, and would have been available in major programming languages.
  - Sami_Lehtinen 10y ago
    Still scanning the MD5 key space 2^128 would take a while to brute force passwords. Of course it only takes time. But a lot of time. SHA1 is better, because it's 2^168 options. Also there's a problem, what if the data isn't in single block. Then you might find collision, but that collision might include something which can't be put in the password field, and therefore doesn't solve the problem. MD5 for PQKDEj52vGQVKudQaBMSewJ5MMifgaVxNYK9zsRTxMzBkyvompLMtgYCYv6SNzDE is cd5480cf1ad1cf7fab3aedbc6495609d. I would love to see someone to reverse that. Even if you find the colliding hash with sorter set of input bits. It's highly likely, it won't be in the acceptable character set. Or am I getting something wrong?
    - creshal 10y ago
      > Or am I getting something wrong? Yes, we're talking about passwords, not private keys. Virtually all passwords found in the wild have a massively lower entropy, so the amount of possible hashes doesn't really matter, only how long it takes to iterate through our much smaller password space. The longer that takes, the less attractive it is for attackers to try and brute-force people's passwords so they can try them on other services.
nothrabannosir 10y ago
Unsalted MD5 is not that much worse than unsalted SHA-1 in this case. Afaik the only vulnerability MD5 has over SHA-1, fundamentally, is that MD5 has easy collision exploitation. But that doesn't matter when bruteforcing passwords. * I'm not 100% on this, but let's be bold :) please forgive me if I'm wrong.

Houshalter 10y ago

This is a stupid question but how is it possible to reverse such long passwords from even a poor hashing algorithm? Even if the hashing algorithm is super fast, testing all combinations up to dozens of characters should still be impossible. And isn't there the possibility of collisions, so that even if you find a string that maps to the same hash, it might not be the original password?

Pikago 10y ago
They were obviously testing for combinations of words and not combinations of single characters. They might even have tested plain sentences. Still very impressive. After all, the leak dates back to 2012. I wonder how much time did the first one take for example. I think strings that maps to the same hash are just inintelligible garbage. If you find something that looks like human then it's certainly the original password.
- kijin 10y ago
  The first one is the title of a song [1]. The attackers probably have a lot of common phrases, song titles, and other catchy excerpts in their dictionary. [1] https://www.youtube.com/watch?v=I915tOiR9sM https://www.youtube.com/watch?v=I915tOiR9sM If it weren't a song title, it would probably have been impossible to crack. That sentence has 12 words. People say that most English conversations only use 3000 words. 3000^12 is 2^138. It has quite a bit more entropy than what we can crack nowadays. Besides, "stripper" isn't part of the 3000-word dictionary.
  - nzp 10y ago
    Those 3000 words are not random in natural language. If they were your calculation would be correct, but they aren't so the actual entropy of the system is likely nowhere near 138 bits. In other words, song title or not, if the sentence was an actual sentence the entropy is much lower. To get maximum entropy out of sets of words you have to use something equivalent to Diceware.
deleted 10y ago
[deleted]