How does using a salt make a password more secure if it is stored in the database?

Question

I am learning Rails, at the moment, but the answer doesn't have to be Rails specific.

So, as I understand it, a secure password system works like this:

• User creates password
• System encrypts password with an encryption algorithm (say SHA2).
• Store hash of encrypted password in database.

Upon login attempt:

• User tries to login
• System creates hash of attempt with same encryption algorithm
• System compares hash of attempt with hash of password in the database.
• If match, they get let in. If not, they have to try again.

As I understand it, this approach is subject to a rainbow attack — wherein the following can happen.

An attacker can write a script that essentially tries every permutation of characters, numbers and symbols, creates a hash with the same encryption algorithm and compares them against the hash in the database.

So the way around it is to combine the hash with a unique salt. In many cases, the current date and time (down to milliseconds) that the user registers.

However, this salt is stored in the database column 'salt'.

So my question is, how does this change the fact that if the attacker got access to the database in the first place and has the hash created for the 'real' password and also has the hash for the salt, how is this not just as subject to a rainbow attack? Because, the theory would be that he tries every permutation + the salt hash and compare the outcome with the password hash. Just might take a bit longer, but I don't see how it is foolproof.

Forgive my ignorance, I am just learning this stuff and this just never made much sense to me.

Answer 1

The primary advantage of a salt (chosen at random) is that even if two people use the same password, the hash will be different because the salts will be different. This means that the attacker can't precompute the hashes of common passwords because there are too many different salt values.

Note that the salt does not have to be kept secret; it just has to be big enough (64-bits, say) and random enough that two people using the same password have a vanishingly small chance of also using the same salt. (You could, if you wanted to, check that the salt was unique.)