-2

On the 2nd of October NIST decided that SHA-3 is the new standard hashing algorithm.

Should MD5 users start migrating to SHA-3? To something else (see below why SHA-3 is not recommended)? bcrypt?

Why Not {MD5, SHA1, SHA256, SHA512, SHA-3, etc}?

And, is this really critical? Even if your password is salted?

John Assymptoth
  • 8,227
  • 12
  • 49
  • 68
  • 1
    In any case, stop using MD5. It's broken. And I don't mean the "some theoretical paper showed how to reduce the complexity of an collision slightly" kind of broken. I mean "you can do things cryptographic hash functions ough to prevent with off the shelf hardware instantly" broken. And "its weakness has been used for real, serious attacks" broken (remember Flame?). Also the "there have been much better options since long before I could program, why you using a function which crypto experts told you to stop using back in 1996" broken. –  Oct 09 '12 at 16:50
  • MSDN is suggesting SHA-2 (http://msdn.microsoft.com/en-us/library/92f9ye3s.aspx#hash_values) There's also an article on Cryptographic Agility (http://msdn.microsoft.com/en-us/magazine/ee321570.aspx) that goes into supporting changing algorithms for password hashes. – Peter Ritchie Oct 09 '12 at 17:17
  • 3
    @delnan This is a bit of fear mongering, isn't it? I'm far from recommending people to use MD5, but I have yet to see a practical attack against MD5-hashed passwords. Sure, they can create a hash collision given an arbitrary file, but that's different from finding a collision for a given hash for password hacking purposes. – NullUserException Oct 09 '12 at 17:50
  • @NullUserException It is not. Yes, there haven't actually been MD5 exploits which revealed someone's salted and MD5-hashed password (as far as I know). But real, serious attacks have been conducted based on other MD5 collisions (again, see Flame for a recent, high-profile and malicious example). Given the continued increase of computing power and the continued advances in cryptanalysis of MD5, I would not bet a single penny on salted MD5-hashed passwords being impractical to crack in, say, the next decade... –  Oct 09 '12 at 17:59
  • @delnan But then it wouldn't be because of an inherent vulnerability of the algorithm. It would be like DES, which to this day has shown no weaknesses except for its short key size. It just got left behind by the times, something that's bound to happen to every crypto routine. – NullUserException Oct 09 '12 at 18:01
  • (continued) ... So I consider it irresponsible to use MD5 *anywhere* close to cryptographic undertakings. We *have* to get rid of MD5 *completely*, **now**, to make sure that no system still in use at that point is based on MD5. And I will make things sound worse than they are, if I must to convince people of this. "Broken" does not mean "people are cracking stuff using it *right now*". See http://www.schneier.com/blog/archives/2012/10/when_will_we_se.html for a (conservative! also read the comments) back of the envelope calculations for when the much stronger SHA 1 will be feasible to beat. –  Oct 09 '12 at 18:04
  • @NullUserException MD5 (like SHA1 btw) does not primarily suffer from a short output length. It's not (only) computers being somewhat faster than back then, this would be nowhere enough for the attacks which are published. Cryptanalysis has yielded enough insight to do attacks which are **way** more efficient than brute force (2^51 instead of 2^128 if if I read my sources correctly), by a margin far larger than a decade of computing advances can bring. And there is no reason to believe that the attacks we know now are the best we can ever do. –  Oct 09 '12 at 18:10
  • @delnan You'd expect a brute force attack on an 160 bit hash like SHA1 to find a collision in 2^80 even if it was perfectly secure anyways (or 2^64 for MD5 if it was perfectly secure). Any sources on that 2^51 figure? – NullUserException Oct 09 '12 at 18:15
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/17765/discussion-between-delnan-and-nulluserexception) –  Oct 09 '12 at 18:24
  • @NullUserException & delnan - what if you use the mechanism of only allowing x tries to login? Doesn't it solve the problem of being too fast? – John Assymptoth Oct 10 '12 at 03:17
  • @JohnAssymptoth Hashing is meant to protect your passwords in case the database is compromised and said hashes are stolen. – NullUserException Oct 10 '12 at 04:32
  • @delnan Convincing people to use good salts(different for each password) and slow constructions (PBKDF2, scrypt or bcrypt) is several orders of magnitude more important than convincing them not to use MD5 for password hashing. And even when using with PBKDF2 SHA-3 is a pretty bad choice, since it's fast in hardware and slow in software, exactly the opposite of what you want. – CodesInChaos Nov 01 '12 at 16:27
  • @NullUserException The issue with MD5 as a password hash isn't collisions. It's *speed*. With GPU clusters, attackers can calculate billions of hashes per second. This, combined with very sophisticated password heuristics allow attackers to typically reveal *all* 8-character or fewer passwords in a database, plus any "structured" longer passwords (e.g., `my!l1ttL3,PoNy.`) – Stephen Touset Oct 09 '13 at 15:55
  • @StephenTouset True, but this is a problem that affects every general purpose hashing function (eg: MD5 and the SHA family). Yes, I was being unnecessarily pedantic, but I was just pointing out that the broken collision resistance of MD5 isn't the problem here (ie: Gumbo's answer). – NullUserException Oct 09 '13 at 16:12
  • @NullUserException "I have yet to see a practical attack against MD5-hashed passwords." There *is* a practical attack, and an obvious example is the Linkedin password database being mostly cracked (that was SHA-1, but the exact same principle applies). Your statement *will* be used by people to justify staying on MD5 passwords as "good enough", which is in my opinion highly irresponsible. – Stephen Touset Oct 09 '13 at 17:48
  • Possible duplicate of [Secure Password Hashing](http://stackoverflow.com/questions/1841595/secure-password-hashing) – Gilles 'SO- stop being evil' Dec 31 '15 at 19:26

1 Answers1

7

The main reason not to use MD5 for hashing passwords is not the fact that MD5 is severely compromised or even considered broken.

It’s true, MD5 has known vulnerabilities. But none of them do pose a serious threat to your use of MD5. Because in your case the only threat would be a preimage attack where an attacker would try to find a preimage of a known hash, e.g. the password to a known (salted) password hash. And the probably known preimage attack against MD5 is only theoretical and lowers the effort from 2128 to 2123.4, which is no big advantage. A brute-force attack with an average of 264 is still more promising.

No, the main reason not to use MD5 is because MD5 is too fast. With a todays affordable computer you can generate and test 7190M MD5 hashes per second. All 8 characters long combinations of alphanumeric characters can be brute-forced in about 8.5 hours, no matter whether with or without salt.

In contrast to that, with the hash function like bcrypt $2a$ one can only generate and test 4085 hashes per second, so only 0.00005682 % of the number of MD5 hashes. With bcrypt $2a$ you would need 1694 years for the same attempt.

Gumbo
  • 643,351
  • 109
  • 780
  • 844
  • What about SHA-3? Is it too fast as well? – John Assymptoth Oct 09 '12 at 19:15
  • @JohnAssymptoth The SHA-3 algorithm was just announced one week ago and there is probably not much research done yet. I don’t know how it performs. But SHA are rather general purpose hashing algorithms than password hashing algorithms. – Gumbo Oct 09 '12 at 19:24
  • It's faster than SHA-2. It was designed for security, then speed. I followed the competition. bcrypt or PBKDF2 are better bets. – Maarten Bodewes Oct 09 '12 at 22:21
  • @owlstead SHA-3 is faster or slower than SHA-2? Not sure if you made a mistake or not. Does it mean it is even more vulnerable than SHA-2 (with brute force)? – John Assymptoth Oct 10 '12 at 03:15
  • @Gumbo what if you use the mechanism of only allowing x tries to login? Doesn't it solve the problem of being too fast? – John Assymptoth Oct 10 '12 at 03:18
  • @JohnAssymptoth You have to distinguish between offline and online attacks. Online attacks are way slower than offline attacks. The mentioned speed does only apply for offline attacks where an attacker has already the password hashes. For online attacks, brute force is not a viable option. You would rather try a dictionary attack with a dictionary of the most used passwords. But you can still implement some features that throttles the number of attempts of a particular client or user. – Gumbo Oct 10 '12 at 03:57
  • 2
    @JohnAssymptoth Speed is not part of the security of cryptographic hashes - the faster the hash is the better. This is why you should use a Key Derivation Function (KDF) instead. PBKDF2 and bcrypt are examples of this. They may use a hash internally, but they use a salt and a number of iterations to keep the security margin for brute force attacks. – Maarten Bodewes Oct 10 '12 at 09:47