· 3 min read · 743 words
MD5 Passwords: What Broke, and What Never Worked
MD5 collisions get the headlines and they are not why MD5 fails at passwords. The real problem is speed, and it was a problem years before the first collision.
- md5
- passwords
- history
Everyone knows MD5 is broken. Rather fewer people can say what broke, and the usual answer is the wrong one for this particular job.
Two kinds of broken
A hash function is asked to resist two different things. Collision resistance means nobody can find two inputs with the same digest. Preimage resistance means that given a digest, nobody can find an input that produces it.
MD5 lost collision resistance in 2004, and by now finding a pair takes seconds on a laptop. That is what killed it for certificates and signatures, and it is genuinely severe. It also has nothing to do with your login form. Cracking a password hash is a preimage problem, and MD5 has no practical preimage attack even now.
So MD5 would still be unfit for passwords if the collision work had never happened. The reason is more boring than a cryptographic break.
It is too fast
MD5 was designed in 1991 to be quick, and hardware since then has been extremely accommodating. One current consumer graphics card runs on the order of 160 billion MD5 hashes per second. That is the whole story.
Every password of eight characters drawn from lowercase letters and digits is about 2.8 trillion candidates. At 160 billion per second, one card walks the entire space in under half a minute. Add uppercase and you are into hours, which is still an afternoon rather than a defence.
| Search space | Candidates | One GPU, MD5 |
|---|---|---|
| 6 chars, lowercase | 309 million | instant |
| 8 chars, lowercase and digits | 2.8 trillion | about 20 seconds |
| 8 chars, full keyboard | 6 quadrillion | about 11 hours |
| A 4 word passphrase | depends on the list | still out of reach |
The same arithmetic against bcrypt at cost 12 puts the second row at roughly sixty years, on the same card. Nothing about the mathematics changed. The cost per guess did.
But we salt our MD5
Salting is worth doing and it fixes exactly one thing: precomputation. With a per user salt, nobody can look your hashes up in a table that was built before the breach, and the attacker has to run their guesses against each account separately.
Running guesses is the part that is free. At 160 billion per second, attacking one salted account at a time is a rounding error on the attacker. Salted MD5 is better than unsalted MD5 and neither of them is a password hash.
The apr1 format in an Apache password file is MD5 based but it is not plain MD5. It runs a thousand iterations, which was a defensible amount of work in 1996 and is now about as cheap as a single MD5 was then. The htpasswd generator will still write it, because some old servers want it, and bcrypt is the option to take when you have a choice.
Where MD5 is still fine
MD5 remains a perfectly good checksum for accidental damage. Did this file survive the copy, is this cache entry stale, have these two rows got the same content. It is fast, it is everywhere, and nothing is trying to fool it.
The line to hold is that MD5 must never guard anything against a person. No download verification against tampering, no signatures, no tokens, no passwords. There is an MD5 tool here for the legitimate uses and it says the same thing on the page.
Getting off it
If there are MD5 password hashes in your database today, that is the one case where waiting for users to log in is not good enough. Every one of those rows is crackable this week.
Run bcrypt over the existing digests in a batch job, mark the rows, and verify in two steps until people come back.
// Batch, no user involvement: the MD5 digest is already in the row.
user.passwordHash = await bcrypt.hash(user.md5Hash, 12);
user.hashScheme = 'bcrypt-over-md5';
// And at login, reproduce the inner digest first.
if (user.hashScheme === 'bcrypt-over-md5') {
const inner = md5(password);
return bcrypt.compare(inner, user.passwordHash);
}Then unwrap each account when its owner next logs in, since at that point you have the plaintext and can write a clean hash. The migration write up has the full version of this pattern, and it applies to any weak starting point, not just MD5.
One thing to plan for while you are in there: those passwords have been crackable for as long as they have existed, so treat the ones that appear in breach lists as compromised rather than merely weak.