How does a salt protect against a dictionary attack? [duplicate]_问答_开发者

This question already has answers here: Closed 11 years ago.

Possible Duplicate:
What is the purpose of salt?

I've just been reading up a bit about the use of salts, and the example I've been reading gives that of adding a salt to a password before hashing to protect against a dictionary attack.

However I don't really see how that helps - if the attacker has acc开发者_JAVA技巧ess to the hash of the password (as they do in the example I've been reading) they most likely they will also have access to the salt. Therefore can't an attacker just prepend and postpend the salt to each item in a dictionary before running through the dictionary to see if it matches the hash? So they have to iterate through the dictionary more than once, that's doesn't seem much of a protection enhancement?

A dictionary attack is an attack where the attacker takes a large list of passwords, possibly ordered by likelyhood/probability, and applies the algorithm for each of it, checking the result.

In case of a salted password, such an attack is still possible (and not significantly costlier), if the attacker has the salt (what is normally assumed): Simply input the salt in your algorithm, too.

What a salt protect against, is a rainbow table. A rainbow table is a table containing pairs of plaintext (e.g. passwords) and the corresponding hashes, ordered by hash. Such a table allows a simple lookup of the password, given the hash.

Producing a rainbow table is a costly step (depending on the size of the dictionary used as input), but then you can use it without any cost later to lookup as many passwords as wanted.

As salt protects against this, since you now would need a separate table for each salt. Even with the simple Unix crypt's 2-letter salt, this already is a factor of 3,844. Modern password hash algorithms use a much larger salt (for example bcrypt uses a 128-bit salt, which gives a factor of 2¹²⁸.)

To protect against dictionary attacks, too, you'll use a slow hash algorithm instead of a fast one like simple MD5 or SHA1/SHA2. Bcrypt is such an algorithm (with a configurable work factor), and the same author later proposed scrypt (which not only takes much time, but also needs lots of memory, which attackers often don't have as much as processing power).

1- You can't use rainbow tables to crack the hashes

2- If two users have the same password the hash would be different if salted (so it's harder to catch common passwords)

It does increase the work they have to do by increasing the amount of possible answers in the password file.

One means of doing a dictionary attack is to scan the password file. If there is no salt and you see "DFGE$%$%£TEW" then you know the password is "PASSWORD". Adding salt means you'll have to use either a much larger dictionary containing all the values for "PASSWORD" with all possible salts, or you have to spend the effort to read the salt and do the encryption which slows you down. It's no longer a simple search.

Salt also helps in situations where more than one user chooses the same password. Especially in the old days when the password file was readable by all users, it makes it not obvious if another user has the same password as you, or the same password as one you know.

Actually a salt doesn't protect against dictionary attack. It has the following benefits:

Increase the computational cost of breaking it, because for each password in the dictonary the attacker need to try hash it with all possible salts.
Prevent two users that have the same password to have also the same hash. This way an attacker has to explicitely break all the passwords even if there are identical passwords in the same file (the hash of password is always different).

Dictionary attacks are based on words from the dictionary. By adding a random salt, you no longer have dictionary words. Thus a password hash table based on dictionary words will not be helpful in cracking a password.

Each salt value requires a different dictionary, so every database that doesn't use a salt can be attacked with the same dictionary.

Without any salt an attacker can just use an off-the-shelf pre-computed dictionary, of which there are plenty.
If you have one salt for your entire database then they need to create a dictionary specific to your database.
If each user record had it's own salt, now they need to create 1 dictionary per user.