2

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 access 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?

Community
  • 1
  • 1
Gruntcakes
  • 37,738
  • 44
  • 184
  • 378

6 Answers6

8

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 2128.)

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).

Paŭlo Ebermann
  • 73,284
  • 20
  • 146
  • 210
  • Does this mean that salt may not be a some random string. For example if I store users passwords I can use username for salt purpose: md5(password + username)? This will protect against rainbow table and I can keep some space by not storing the salt. – alexpods Oct 26 '14 at 14:46
  • 1
    @alexpods This works for some attack scenarios, but not for all of them – e.g. now the same username-password combination in different applications (websites) results in the same hash. (Also, please don't use MD5 for anything, ever.) – Paŭlo Ebermann Oct 26 '14 at 22:32
  • Thanks for answer! (md5 I used only for exampe purpose) But I still don't really understand: for best security salt ALWAYS must be a RANDOM, or not. For exapmle I can get hash from username and iterate it several times (pseudocode): hash(password + iterate(1512, hash(username)). Count of iteration is specific for my application. Even if attacker knows about algorithm and iterations count (he is old company employee, who was fired and wants his revenge) he can't do anything. At least this is not less secure than with random salt. Maybe I wrong? What is my mistake? – alexpods Oct 27 '14 at 09:35
  • So we're using salts to add extra security in the event when the password database has been compromised? – IcedDante Nov 29 '15 at 14:23
5

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)

ksn
  • 623
  • 2
  • 6
  • 18
2

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

  1. 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.
  2. 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).
Heisenbug
  • 38,762
  • 28
  • 132
  • 190
1

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.

Richard Corfield
  • 717
  • 6
  • 19
  • What you describe by "dictionary" is commonly known as "rainbow table". A dictionary (as used for a dictionary attack) is simply a long list of possible/likely passwords (without their hashes). You can still use such a list to attack a salted password, it just is a lot slower than a rainbow table attack (but still faster than brute-force). – Paŭlo Ebermann Aug 24 '11 at 17:04
0

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.

Teddy
  • 18,357
  • 2
  • 30
  • 42
  • If you know the dictionary content, and you know the salt, then the salt appended to the dictionary is one new dictionary, the salt prepended to the dictionary is another new dictionary. Thus you now know two dictionaries no? Or is the salt sometimes interspersed within the password? – Gruntcakes Aug 24 '11 at 16:19
  • 1
    In the case of /etc/passwd on UNIX systems it was two characters prepended to the password. The same two characters are stored at the beginning of value in the password file. When the user sets their password a random salt is used, so "PASSWORD" becomes "azPASSWORD" and the hash is (say) az12345. Then when the user attempts to log in they type "PASSWORD" and the system knows to use "az" as the salt. Even if the salt is only a-zA-Z0-9 your dictionary is still (10+26+26)^2 = 3,844 times bigger. – Richard Corfield Aug 24 '11 at 16:23
  • 1
    BiscutWoofington is on the right track, Teddy's answer is flat out wrong. You can simply modify your cracking engine of choice, practically all are open source, to append the salt value and you've got magic. The point of salting is to remove the threat of precomputed rainbow tables which can be searched through very rapidly, now that we live in the age of EC2 and GPU parallelization, everyone who needs to crack passwords today can do so for comically cheap anyway. – zetavolt Aug 24 '11 at 16:31
  • @geteipordietryin Ouch! I am flat out wrong?? You do make a valid point about cloud computing, etc as a brute force attack. – Teddy Aug 24 '11 at 16:38
  • Salts protect against rainbow tables, not dictionary attacks. – Paŭlo Ebermann Aug 24 '11 at 17:02
0

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.

Davy8
  • 30,868
  • 25
  • 115
  • 173