why salt did not help when using dictionary attack

Question

From this site http://codahale.com/how-to-safely-store-a-password/:

It’s important to note that salts are useless for preventing dictionary attacks or brute force attacks.

If salt is useless to prevent dictionary attack, why using salt?

Answer 1

For single passwords, it doesn't make that much of a difference. Brute-forcing an unsalted password is just as hard as brute-forcing a salted password. You just try out keys until you get a hit.

The difference is when there are a lot of passwords, for example in a leaked database. The basic idea is that part of the necessary computations can be re-used when cracking many passwords. This is done by constructing a rainbow table. Doing that is computationally expensive, but once done it allows the attacker to crack a lot of passwords relatively fast. Cracking N passwords with a rainbow table is a lot faster than brute-forcing those N passwords individually.

If every password is hashed with an individual salt, you can't re-use information in the same way. You could still construct rainbow tables, but they would only be usable for exactly one password in the database, which renders them useless. So in order to crack N passwords, you really have to brute-force all N passwords individually, which is usually not practical for the attacker.

For unsalted passwords and popular hash algorithms, you can simply download pre-calculated rainbow tables from the Internet, so an attacker wouldn't even have to calculate them by himself. He can just download a table and lookup the password for a particular hash. A salt prevents that.

Unsalted hashes also have the drawback that the password hash for two users with the same password is identical. So if an attacker finds multiple users with the same password hash, he only has to crack that password once.

Answer 2

If the 'attacker' has the password hash (and salt) used by your site/app they will simply brute force "salt" + "password".

However, using a salt offers more protection against rainbow tables (precalculated hash tables) so they're still worth using.

Answer 3

Salts prevent instant cracking from a dictionary via rainbow tables; the article and follow-up make the point that the CPU/Storage tradeoff is now such that rainbow tables don't make sense, and so salts don't help you. And of course, they never helped with brute-force attacks.

Answer 4

For illustration purposes, say you are using 2 character string for salts which can be a random element from the set
salts = {'00', '01', '02'...... '99'}

The formula you use is:

salt = salts[rnd(100)]      # gets a random element from the set above, say '87' 
password_hash = MD5(password + salt) # say the hash is 'dai480hgld0'

Thereafter you'll save the hash and salt in your database, something like

+---------------------------+
| password_hash      |  salt|
+---------------------------+
| dai480hgld0        |  87  |
| sjknigu2948        |  23  |
| .                  |  .   |
| .                  |  .   |
+--------------------+------+

We assume that in a compromised system an attacker has access to your code - so he knows how you calculated your hashes.
The attacker will also have access to your database, so he has all the password hashes and the salts.

Given this information, in order to do to crack your password (which has a hash: 'dai480hgld0') he'll have to do the following:

for word in dictionary_words #iterate over all the words in dictionary
  for salt in salts          #iterate over all possible salts (100 iterations)
     password_hash = MD5(word + salt)
     if password_hash == 'dai480hgld0'
       print "The password is " + word
       exit()  
     endif
  next
next

Note that if you'd have not used any salt at all, the algorithm would have been

for word in dictionary_words #iterate over all the words in dictionary
  password_hash = MD5(word)
  if password_hash == 'dai480hgld0'
    print "The password is " + word
    exit()  
  endif
next

From the above two code samples, its obvious that adding a salt to the password increases the number of attempts in the brute force attack. In our case since there are 100 possible salts, you've made the attacker try each word with 100 salts.

So, to conclude:

• Salts are good. They make your passwords tough to crack. Even if your users enter weak passwords, the salt makes sure that the resultant hashes are not googlable. For eg, its easy to google a hash '3cc31cd246149aec68079241e71e98f6' which is actually a password that is fairly complex and will meet almost all password policies. Still cracking it requires not a single line of code !

• Salts are not panacea. They just increase the time it takes for a cracker to brute force your passwords. However, if your salt address space is fairly big then you are pretty good. For eg, if you have 32 characters alphanumeric string as a salt - brute force will really take very long.
  

• Slow algorithms like bcrypt help you in this regard just because they are well... 'slow'. For a brute force attack, it will take unrealistically long to break hashes that are slow to compute.

Answer 5

Salt makes the encryption stronger. However, dictionary attacks don't try to decrypt the password hash, so salt or no salt, it doesn't matter, they will just try out many passwords until one works.

Answer 6

This belongs on security.stackexchange.com

The problem is one of compute capacity in combination with the speed of the hashing algorithm. Basically, he's pitching bcrypt which is slow.

If a hacker has both the hash and salt used as well as knows the algorithm used to hash the password, then it's simply a matter of time to crack it.

If using a very fast algorithm, then that time is pretty short. If using an extremely slow algorithm then the time is, obviously, much longer to find a hit.

Which brings us to the primary reason why we hash/salt things in the first place: to buy time. Time that can be used in order to change all of the passwords listed and time to contact all of the users to let them know in case they need to change their passwords on other systems.

The reason we use salt is to force the hacker to build a rainbow table per salt value. This way one table can't be used to crack all of your passwords. The only reasons to do this are to buy time and, hopefully, dissuade the common hackers from investing further resources in cracking all of them.

Hashed passwords, regardless of mechanism used, are not secure in the sense that most people take that word. Secure doesn't mean "can never be cracked". Rather it means "this is going to be expensive in term of time/effort to crack". For most hackers, they want low hanging fruit such as clear text only. For some, they'll go to whatever extreme is required, such as building massive rainbow tables per salt value to get them all.

And, of course, underpinning this is whether any "super" user accounts are easily identified in your user table. For most systems just cracking the sys admin type of account is good enough and therefore the fact of using a different salt value per user is immaterial. The smart ones will just bother with that one account.

Answer 7

It is not entirely accurate, as with most things it depends on your assumption.

main assumption are:

1. Attacker has salt
2. calculation of hashes "on the fly" are done pretty quick (as with salt he will need to recalculate all and wont be able to use predefined lists)
3. same salt for each user.

Answer 8

Now this doesn't seem like a programming question, so I'll just give you some info on salting and encryption:

The purpose of salting is to aid in one-way functions like Hashing, which is used widely in Cryptography, often in use of passwords because of its difficulty to guess, and time it takes for other attacks like brute-force attacks to crack them.

If you want to securely store passwords, the best way is definitely encryption. Look up encryption on Wikipedia for more info on that.

Answer 9

Two comments:

1. Regular hash algorithms can be iterated. There is no need to use a non-standard algorithm just because you want to increase the work factor.

2. Using a Salt is to be recommended even if you use a slow hash method. It might not necessarily increase the work load of the best attack, but it will stop trivial attacks in case a user chooses a password identical to that of another user, another account or to an old password.