Notably, the passwords were stored as unsalted MD5 hashes, which even in 2012 was known to be a poor idea.
Notably, the passwords were stored as unsalted MD5 hashes, which even in 2012 was known to be a poor idea.
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.
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.
[1] 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.
http://arstechnica.com/security/2013/05/how-crackers-make-mi...
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)`).
Still, it's impressive.
Now adding a salt would have made it ~2 millions time harder for these ~2 million unique passwords.
• 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.
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?
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.
* I'm not 100% on this, but let's be bold :) please forgive me if I'm wrong.