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

First of all, what you've described isn't a rainbow attack, it's a dictionary attack.

Second, the primary point of using salt is that it just makes life more difficult for the attacker. For example, if you add a 32-bit salt to each pass-phrase, the attacker has to hash and re-hash each input in the dictionary ~4 billion times, and store the results from all of those to have a successful attack.

To have any hope of being at all effective, a dictionary needs to include something like a million inputs (and a million matching results). You mentioned SHA-1, so let's use that for our example. It produces a 20-byte (160-bit) result. Let's guess that an average input is something like 8 characters long. That means a dictionary needs to be something like 28 megabytes. With a 32-bit salt, however, both the size and time to produce the dictionary get multiplied by 2³²-1.

Just as an extremely rough approximation, let's say producing an (unsalted) dictionary took an hour. Doing the same with a 32-bit salt would take 2³²-1 hours, which works out to around 15 years. There aren't very many people willing to spend that amount of time on an attack.

Since you mention rainbow tables, I'll add that they're typically even larger and slower to start with. A typical rainbow table will easily fill a DVD, and multiplying that by 2³²-1 gives a large enough number that storage becomes a serious problem as well (as in, that's more than all the storage built in the entire history of computers, at least on planet earth).

Answer 2

The attacker cannot do a rainbow-table attack and has to brute-force which is a lot less efficient.

Answer 3

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.)