3 ms·

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,

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]
nix0n 10y ago
> Even if the hashing algorithm is super fast, testing all combinations up to dozens of characters should still be impossible. It's just time consuming, and compute time has gotten a lot cheaper. Advancement in GPU computing, cheap clouds, etc have really changed the game on this one since the invention of MD5 (which is why unsalted MD5 is such a bad idea now). It's important to note that brute force is always technically possible, and the best hashing algorithms just consume more time. When we say "impossible" we really just mean "impossible to bruteforce before the heat death of the universe". > 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? That's correct, but if the hash is what's stored then the server is checking hash vs hash and a collision will result in login. This is all coming from one computer security course, but I'm sure someone on HN can correct me if I've got any of this wrong.
snowwrestler 10y ago
The ArsTechnica coverage of password cracking is eye-opening and informative about how high-speed password cracking is done. And this was 3 years ago! http://arstechnica.com/security/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/ http://arstechnica.com/security/2013/05/how-crackers-make-mi...
stouset 10y ago
> 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? Not really. 2^128 is a stupefyingly big number. We'll likely never find a random collision in MD5. We know how to generate collisions in MD5, but this requires knowing the preimage (e.g., the m in `h = H(m)`).

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]

nix0n 10y ago

> Even if the hashing algorithm is super fast, testing all combinations up to dozens of characters should still be impossible. It's just time consuming, and compute time has gotten a lot cheaper. Advancement in GPU computing, cheap clouds, etc have really changed the game on this one since the invention of MD5 (which is why unsalted MD5 is such a bad idea now). It's important to note that brute force is always technically possible, and the best hashing algorithms just consume more time. When we say "impossible" we really just mean "impossible to bruteforce before the heat death of the universe". > 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? That's correct, but if the hash is what's stored then the server is checking hash vs hash and a collision will result in login. This is all coming from one computer security course, but I'm sure someone on HN can correct me if I've got any of this wrong.

snowwrestler 10y ago

The ArsTechnica coverage of password cracking is eye-opening and informative about how high-speed password cracking is done. And this was 3 years ago! http://arstechnica.com/security/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/ http://arstechnica.com/security/2013/05/how-crackers-make-mi...

stouset 10y ago

> 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? Not really. 2^128 is a stupefyingly big number. We'll likely never find a random collision in MD5. We know how to generate collisions in MD5, but this requires knowing the preimage (e.g., the m in `h = H(m)`).