I know developers who will to this day insist that salted md5 is practically invulnerable and more than adequate as long as the salt is big enough.

That's quite unfortunate. The size of the salt doesn't really matter much, so long as it can't be pre-computed before the DB leak. Once the DB is leaked, the salt could be a hundred characters and it wouldn't help much more than a ten character one.

That is very interesting, but at this late hour I'm having trouble understanding how the DB leak affects the effective salt length.

With apologies for asking, is there an ELIM (Explain Like It's Midnight) version?

(I did read the security.stackexchange.com question linked in the GP - is the answer in there and I missed it?)

Thanks!

Sure: You can try a few billion passwords per second on modern hardware. The salt gets prepended on every try, so it doesn't count towards the complexity, it only helps with not precomputimg lists of hashed passwords and just comparing. Therefore, no matter how long the salt is, you still can try the same billion passwords a second, and a seven-character password will still only take 26^7 to be brute-forced.

Also, the salts are stored unencrypted in the database, right next to the hashes.

Thanks! Between your explanation and ReidZB's, that really clarifies the issues involved. Much appreciated.

Sure. The purpose of a salt in password storage is to prevent the pre-computation of a gigantic rainbow table, which essentially acts as a lookup table. (Rainbow tables use less disk space in exchange for more time per lookup.)

Here, the salt only needs to be sufficiently long to make the rainbow table huge enough that it can't be computed in a timely or efficient fashion. So, a salt that's only a single printable ASCII character in length is rather short and probably insufficient; an attacker could build a rainbow table of the top X most common passwords (taken from previous leaked password lists) with every possible character as a salt and then use this against a leaked DB.

On the other hand, a massive salt doesn't help much in this phase either. A salt of fifteen characters is more than sufficient to prevent a rainbow table from including all possible salts, so there's not much of a point in using something ridiculous like a 100-char salt.

But once the DB is leaked, assuming a rainbow table is not feasible, an attacker instead will swap over to brute-force attacks (usually trying dictionary lookups first to find the very weakest passwords, then doing other techniques like trying common words with letters replaced with 1337 digits, and so on). Here, the attacker knows the salt (by virtue of the DB being leaked) and so the most important factor is how fast the attacker can try potential passwords. This is where MD5 breaks, of course; it's far too fast. An attacker with virtually no funding can test billions of passwords per seconds (on a GPU), and so a large Bitcoin GPU farm could be repurposed to crack salted MD5'd passwords at an extremely scary rate.

In fact, the block size of MD5 is 512 bits (64 bytes), so all strings with less than 64 bytes should take about the same time to hash. Thus, even a 40-byte salt with MD5 won't affect password cracking rates until the passwords hit 20 characters long, and a password that long is rarely cracked anyway. Even a 64-byte salt would only make the hashing take about twice as long, and when you're testing billions of passwords per second anyways, twice as long doesn't sound like much. (Actually, if you prepend the salt to the password, I can think of an attack where only the partial blocks at the end of the salt affect the brute-force attempt, which would make the salt's length not affect the cracking rate at all.)

So in sum, before the DB is leaked, the salt needs to have enough entropy to prevent pre-computing all possible salt values. Once the DB is leaked, the attacker doesn't much care about the salt length anymore because they know now all the salts used.

Thanks very much for the detailed explanation! That is very helpful - I think I understand the issue now, and hopefully other readers have a better understanding too.