So, as I understand it, you prepend a password with salt before you hash it so that the resulting hash can't be used with a rainbow table to find the original password, as you could if the password alone was hashed. But what's to stop someone from recomputing a new rainbow table with the salt prepended if the salt is known? I thought knowing the salt wasn't supposed to matter security-wise?
One word: cost.
It is much more costly to built the table than to directly try to break the password. Trying to brute-force the password requires only a trivial amount of memory; a rainbow table requires a huge storage space.
The only point of a table is that someone else has computed it and you can now use it. Many people using one table (or the same person using the table several time) pays up for the cost of building that table. If you are going a table once (for one password), there is just no point.
If every password in a given (really big) password database was using the same salt, that would be a different story. But would be a gross misuse of the salt: the point is that every password uses a different salt, so a rainbow table can never pay up.
Salting does not imply that you cannot try to break-force the password directly. Not only you can, but it is not more difficult when there is a salt. What you cannot do is reuse previous computing efforts (unless the system so broken as to not be able to generate a different salt each time).
|show 12 more comments|
Absolutely nothing: you can calculate a rainbow table for each salt just like you do for an unsalted hash. The rainbow table is a space/time trade-off, and the purpose of the salt is to make that more costly.
Every bit of salt you add doubles the storage requirements. So, one bit of salt means twice the storage space. 8 bits of salt, 2^8 or 256 times the storage requirement. 32 bits - 4 characters - of salt, 2^32, or 4,294,967,296 times the storage space to fully calculate the rainbow table.
When you build a rainbow table, you compute the attacked hash function on many inputs. Any input value which you did hash during table building will be attacked successfully; and the table will not break any other. Due to some unavoidable quirks in the building process (that's a byproduct of the rainbowness of the table), you will hash some input values several times. Taken all together, a rainbow table which can break N possible passwords has a building cost of about 1.7*N, i.e. 70% more than simply hashing all these passwords in a basic brute force cracking.
So table building is worth the effort only if the table can be used at least twice, to (try to) crack two passwords or more. Salts prevent that. With salts, each table would be specific to a single hashed password (strictly speaking, to a single salt value).