I could really use some clarification as to how using a random salt protects against rainbow table attacks. It just isn't clicking for me.
Suppose there is a dumb application that requires passwords to be exactly five characters or less, and that salts those passswords with a nine-character random salt. If I have a rainbow table that has precomputed hashes of all character combinations 14 characters or less, how does the random salt provide any additional security? In this case won't the hashed value of the random salt + password combo. be present in the rainbow table?
I have read multiple places that using a salt would force the cracker to generate an entirely new rainbow table; similarly, a random per-password salt would require a new rainbow table for each salt. Why?
If someone truly has a rainbow table containing the hash of all possible character combinations, then no, salting is of no help. But even assuming just A-z, a-z, 0-9 as valid characters, that's 6214 = 1.2x1025 14-character passwords. So that's 170 billion petabytes of storage required.
Given that that's not feasible, the attacker must have a much smaller table, containing only the most likely character strings (e.g. all the words in a dictionary, intermingled with numbers, etc.). If you add a salt, then this table becomes useless. If the salt is fixed (and known), then the attacker could recompute a new table. But if each password has a different salt, then that won't work either.
One of the faster yet to some extent effective ways to see what a password is by creating a hash on all words in a dictionary, for example. People who try to crack passwords know what they're looking for and due to limited computing speeds they narrow their search down to often used passwords. By using a salt these often used words will never truly be used as a password.
