How does password salt help against a rainbow table attack?

by

A public salt will not make dictionary attacks harder when cracking a single password. As you’ve pointed out, the attacker has access to both the hashed password and the salt, so when running the dictionary attack, she can simply use the known salt when attempting to crack the password.

A public salt does two things: makes it more time-consuming to crack a large list of passwords, and makes it infeasible to use a rainbow table.

To understand the first one, imagine a single password file that contains hundreds of usernames and passwords. Without a salt, I could compute “md5(attempt[0])”, and then scan through the file to see if that hash shows up anywhere. If salts are present, then I have to compute “md5(salt[a] . attempt[0])”, compare against entry A, then “md5(salt[b] . attempt[0])”, compare against entry B, etc. Now I have n times as much work to do, where n is the number of usernames and passwords contained in the file.

To understand the second one, you have to understand what a rainbow table is. A rainbow table is a large list of pre-computed hashes for commonly-used passwords. Imagine again the password file without salts. All I have to do is go through each line of the file, pull out the hashed password, and look it up in the rainbow table. I never have to compute a single hash. If the look-up is considerably faster than the hash function (which it probably is), this will considerably speed up cracking the file.

But if the password file is salted, then the rainbow table would have to contain “salt . password” pre-hashed. If the salt is sufficiently random, this is very unlikely. I’ll probably have things like “hello” and “foobar” and “qwerty” in my list of commonly-used, pre-hashed passwords (the rainbow table), but I’m not going to have things like “jX95psDZhello” or “LPgB0sdgxfoobar” or “dZVUABJtqwerty” pre-computed. That would make the rainbow table prohibitively large.

So, the salt reduces the attacker back to one-computation-per-row-per-attempt, which, when coupled with a sufficiently long, sufficiently random password, is (generally speaking) uncrackable.

More Related Contents:

  1. Salting Your Password: Best Practices? [closed]
  2. How long to brute force a salted SHA-512 hash? (salt provided)
  3. Is it possible to decrypt MD5 hashes?
  4. Where do you store your salt strings?
  5. yii CPasswordHelper: hashPassword and verifyPassword
  6. How come MD5 hash values are not reversible?
  7. Is calculating an MD5 hash less CPU intensive than SHA family functions?
  8. Can two different strings generate the same MD5 hash code?
  9. Is it possible to decrypt MD5 hashes?
  10. How can I hash passwords in postgresql?
  11. Best practice for hashing passwords – SHA256 or SHA512?
  12. Fundamental difference between Hashing and Encryption algorithms
  13. Salt Generation and open source software
  14. Is “double hashing” a password less secure than just hashing it once?
  15. Non-random salt for password hashes
  16. Probability of SHA1 collisions
  17. Why is XOR the default way to combine hashes?
  18. What is the optimal length for user password salt? [closed]
  19. Is there an MD5 Fixed Point where md5(x) == x?
  20. Which cryptographic hash function should I choose?
  21. Best Practices: Salting & peppering passwords?
  22. Is it possible to get identical SHA1 hash? [duplicate]
  23. Why do salts make dictionary attacks ‘impossible’?
  24. How are hash functions like MD5 unique?
  25. Why does crypt/blowfish generate the same hash with two different salts?
  26. How do I generate a SALT in Java for Salted-Hash?
  27. Compute a hash from a stream of unknown length in C#
  28. Git is moving to new hashing algorithm SHA-256 but why git community settled on SHA‑256
  29. How to “EXPIRE” the “HSET” child key in redis?
  30. node.js hash string?

Leave a Comment