11

I've recently discovered that one of our (strictly internal facing - no external risk unless other systems are completely compromised) platforms is storing passwords by salting and then MD5 hashing them. According to the Wikipedia article, MD5 is very vulnerable to collisions, but only theoretically vulnerable to preimage attacks (cost being ~2123). The article cites the preimage attack being created in 2009, however - quite a long time ago! I am unable to find any significantly more recent information about MD5 vulnerability to preimage attacks.

As a result, my question is this: Have there been any vulnerabilities found in MD5 that would allow a preimage attack on a hashed password, either to find a collision or determine the password, with a cost of less than 2123?

As a follow up question, how important is it that I attempt to pressure the vendor into moving off MD5 for password hashing? Is this major and immediate vulnerability, or more of a theoretical future one (should the database be breached).

3
  • 1
    When saving a password verifier just using a hash function is not sufficient and just adding a salt does little to improve the security. Instead iteration with a random salt for about a 100ms duration and save the salt with the hash. Use a function such as PBKDF2, Rfc2898DeriveBytes, Argon2i, password_hash, Bcrypt or similar functions. The point is to make the attacker spend substantial time finding passwords by brute force.
    – zaph
    Commented Nov 3, 2018 at 20:53
  • The MD5 vulnerabilities are much less than "2^123" given they are password based. The general attack used lists of frequently used passwords ordered by frequency of use, see SecLists. Also there are readily available cracking programs, see password-cracking-tools.
    – zaph
    Commented Nov 4, 2018 at 8:32
  • 1
    To support what @zaph said above: What is the specific reason to prefer bcrypt or PBKDF2 over SHA256-crypt in password hashes? Commented May 21, 2019 at 21:16

2 Answers 2

17

MD5 should be considered completely compromised for password use, and has been "deprecated" for passwords for a long time. It doesn't even have to involve preimage attacks or explicit vulnerabilities. It is as simple as the fact that the hash rate for modern GPU stacks against MD5 is so fast that you can feasibly brute force nearly any password (okay, I exaggerate slightly)

This is an extreme setup, but it can run through almost 200 billion hashes per second. That means it can guess about 200 billion passwords every second if they are hashed as MD5. I don't have an exact translation but as you can imagine, being able to try 200 billion password guesses every second means that even strong passwords can get easily cracked. The article suggests that it can crack a 14 character windows XP password (which is slightly weaker, and has roughly double the hash rate as for MD5) in just 7 minutes.

More realistic hashing setups might hash passwords at roughly a tenth of that rate, but even still it is quite possible to brute force any realistic password that is hashed with MD5.

Edit to address the second half of your question

Is this an immediate threat? Yes and no. In practical terms it is a theoretical threat, as your passwords will only be vulnerable in the event that this internal system is breached. However, the more you read about the very involved kind of hacks that criminals go through when they want something, the more you realize how important it is to have thorough security at every level of the system. I personally believe that internal systems should be as secure as external systems. Here is a good example of a time that bad security lead to expensive breaches:

https://gizmodo.com/hackers-found-a-new-way-to-rip-off-atms-1818859798

Moreover, the other issue is that MD5 has been "out-of-fashion" for password storage for quite a long while now. I would be very concerned that the rest of their security is equally out-of-date, and that this internal system of yours is full of security holes.

Another edit

An important thought to keep in mind: with these things an important consideration is the potential damage done in the event of a breach. I don't know what this internal system does, but there is one important bit of sensitive information it definitely stores: your user's passwords. Even if that is all it stores, it is potentially dangerous. Here is a very plausible worse-case scenario. What are the odds that you have an administrator that has a user account on this internal system? If so, what are the odds that that person used the same password for the internal system as the did for the password to administer, say, your company-wide email system? If so it is a short hop, skip, and jump from cracking an MD5 password to taking control of your email system, and from there to probably any aspect of your company that is web-facing.

While you try to work things out with the people who manage your internal system, you can think through this thought process yourself and take appropriate steps: "If a malicious user managed to get a hold of the password to email account X, how much trouble could they cause?". You would be surprised how many companies out there have effectively their entire system dependent upon the security of a single email account, and that without any 2FA. If that is the case for your company you should fix that, regardless of what this third-party vendor says. Otherwise your worst-case-scenario is very bad, and this internal system is just one of many ways in which a malicious attacker may be able to cripple your company.

10
  • +1 for "I would be very concerned that the rest of their security is equally out-of-date, and that this internal system of yours is full of security holes.". Regarding the current password brute-forcing capabilities : gist.github.com/epixoip/ace60d09981be09544fdd35005051505 (8*GTX1080 Ti slighly surpassed 300 Billons MD5 hashes per second).
    – ATo
    Commented Oct 10, 2017 at 6:35
  • 1
    @Cowthulhu Sounds like a good starting point. FYI, I added a couple more paragraphs about what is (potentially) at risk. Commented Oct 10, 2017 at 19:27
  • 1
    To translate the 200 billion per second, that means that in 30 days or less, the keyspace for a lower+number, 11 character, a lower only 12 character, a lower+upper+number+number symbols 9 character, or lower+upper+number+normal keyboard symbols 8 character (and nearly all the 9 character) could be exhaustively searched. Commented Jan 27, 2018 at 5:05
  • 1
    It is not true that "MD5 should be considered completely compromised", it depends on usage. Certainly it is compromised for signing but It can still be used as a checksum to verify data integrity, but only against unintentional corruption. However it is best to choose a current hash function such as from the SHA2 or SHA3 series.
    – zaph
    Commented Nov 4, 2018 at 8:37
  • 1
    @ArneVogel So yes, it's true that I did not answer the exact question answered (does MD5 have preimage vulnerabilities), but I answered the much more important (for the OP) question: is it safe to use MD5 for passwords? Definitely not. Call it a frame challenge if you would like. Commented Jun 18, 2019 at 14:40
1

Please consider using a more modern password hash, either Scrypt or Argon2id.

GPU-based dictionary attacks are brutally effective against salted hashes, even if the hash is SHA512. PBKDF2 is a very poor hashing algorithm, with trivial collisions and poor defense. Bcrypt is OK, but you'd be safer switching to a modern memory-hard password hashing algorithm that is inefficient on GPUs. Scrypt is prevasive and still quite good, but if you have access to Argon2id, I'd use that.

Sent me a random sample of your MD5 hashes and salts, and I'll send back 90% of the corresponding passwords within 24 hours. I'll crack them without a GPU: just using my laptop. Really. Just download HashCat, and it's just plug and chug.

12
  • Keep in mind that while while Argon2id is better than PBKDF2 Argon2 is not available on all platforms. Characterizing PBKDF2 as a "very poor hashing algorithm, with trivial collisions and poor defense" is disingenuous and just plain wrong. PBKDF2 is still recommended by NIST and since it relies on strong hash algorithms is not collision prone.
    – zaph
    Commented Nov 3, 2018 at 19:31
  • Note: PBKDF2 is not a hashing algorithm, it is a Password Based Key Derivation Function. It uses a HMAC which uses a hashing function such as SHA-256, a salt, and a repetition count. A reasonable value of the the repetition count is a value that consumes ~100ms of CPU time.
    – zaph
    Commented Nov 4, 2018 at 7:59
  • PBKDF2 itself doesn't create trivial collisions. It's PBKDF2 with HMAC that causes them. HMAC has pairs of equivalent keys. Another PRF choice isn't necessarily collision vulnerable. Commented Nov 4, 2018 at 16:14
  • For password based authentication the collisions have no effect on security. With HMAC it just means that if you have a very long password then you can enter that or another long, random-looking password at a log in prompt. It doesn't make password cracking easier. It's safe for key derivation too if it's your password and your key. Maybe you can exploit a collision pair in an unusual scenario, but anyone that doesn't know your password can't. Commented Nov 4, 2018 at 16:39
  • 2
    Are you serious? I know MD5 is not collision-resistant, but a preimage attack like this? Anyway just in case you meant it, here is a few salts + MD5 hashes: pastebin.com/raw/zfSudWG5 I have included the first password for reference. I'd be very surprised if you can find any of the others.
    – RocketNuts
    Commented Feb 5, 2019 at 0:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .