Salts are stored with the hash - so for a single user it's no security advantage?

Question

A hacker goes into a database and downloads a bunch of hashes and salts of users with knowledge of the hashing method. Say this is one entry that got downloaded:

cbc0a790b2f28fc72ca43eb749028b9f:21022011 (hash:salt)

Without the salt, the hacker simply computes 100M common passwords and their hashes and find matches. With the salt, the hacker simply computes 100M common passwords + 21022011 and their hashes and find matches. So, what's the difference for one user?

Sure, to massively crack hundreds of user passwords, the attacker would need to compute the rainbow table for 100M common passwords for each user. But the attacker can also be targeting just one user - maybe he knows the username of the company CEO and now with the database leak, the CEO's hash and salt as well.

Answer 1

The purpose of a salt is to prevent the use of rainbow tables that are computed based on a known hash algorithm.

Back in the times, when passwords were stored simply hashed using MD5 (for example), an attacker would be able to compare all hashes against a pre-computed MD5 rainbow table and thus very quickly find the password. Plus, this one rainbow table could be used everywhere that hash algorithm was used.

If, however, the hash is computed from the password plus a random salt, the rainbow table becomes useless. Even though the salt is known, the attacker must first get knowledge of the salt, then go back to brute force and compute all password hashes in combination with that salt, which takes a very long. And since every password is hashed with a different salt, these computations must be repeated for every single password.

So, yes, it is a security advantage for a single user. You say "the hacker simply computes 100M common passwords + 21022011 and their hashes", but exactly that is what makes it so expensive for the attacker. Simple doesn't necessarily mean cheap.

Answer 2

Even for one targeted user, the salt still has the security advantage for legitimate user that in the event of loss of confidentiality of the password database:

1. The attackers can't start their attack before they got the database. Thus the salt buys times for the legitimate user, which has the opportunity to change their password during the attack. This is one of few good reasons to change password periodically.
2. The attackers can't hope amortize the computing power they spend on other attacks using the same hash. Thus the salt increases the cost for repeat attackers, which in turn makes the user less insecure.

Main problem with today's practice is that iterated hashes like PBKDF2 are commonly used, which is a dream for attackers with GPUs, FPGAs, or (hypothetically) ASICs: they can hash so much faster than the legitimate server does that they can break most passwords a user would pick at cost that makes economical sense.

To illustrate that: current cost of $2^{61}>2\cdot10^{18}$ additional SHA-256 hashes in bitcoin mining ASICs is less than one US dollars; if these these ASICs could be used for PBKDF2-HMAC-SHA-256 attack (they can't AFAIK, but they are not far), this means testing $10^{13}$ additional passwords in PBKDF2 with a $10^5$ iterations (which is the largest I have heard is commonly deployed) would cost one US dollars, and find most common passwords, including ones recommended by XKCD.

I can't recommend enough dropping PBKDF2 and using a memory_hard password hash like Argon2, with ample hardness parameters to make such attacks less likely.

Also: keeping the password database secret should be the first line of defense, and a strong one.