Why do we use the "salt" to secure our passwords?

Question

i was reading this tutorial, and i encountered the following discussion about encryption. At the end there's written

In the last line, we’ve hashed the salt with the password, yielding an encrypted password that is virtually impossible to crack

But in my opinion an hacker who has both the encrypted_password and the salt could do the "rainbow" trick exactly as if we were using the salt.

So, where i'm wrong?

Thanks!

$ rails console
>> require 'digest'
>> def secure_hash(string)
>>   Digest::SHA2.hexdigest(string)
>> end
=> nil
>> password = "secret"
=> "secret"
>> encrypted_password = secure_hash(password)
=> "2bb80d537b1da3e38bd30361aa855686bde0eacd7162fef6a25fe97bf527a25b"
>> submitted_password = "secret"
=> "secret"
>> encrypted_password == secure_hash(submitted_password)
=> true

Here we’ve defined a function called secure_hash that uses a cryptographic hash function called SHA2, part of the SHA family of hash functions, which we include into Ruby through the digest library.7 It’s not important to know exactly how these hash functions work; for our purposes what’s important is that they are one-way: there is no computationally tractable way to discover that

2bb80d537b1da3e38bd30361aa855686bde0eacd7162fef6a25fe97bf527a25b is the SHA2 hash of the string "secret".

If you think about it, though, we still have a problem: if an attacker ever got hold of the hashed passwords, he would still have a chance at discovering the originals. For example, he could guess that we used SHA2, and so write a program to compare a given hash to the hashed values of potential passwords:

>> hash = "2bb80d537b1da3e38bd30361aa855686bde0eacd7162fef6a25fe97bf527a25b"
>> secure_hash("secede") == hash
=> false
>> secure_hash("second") == hash
=> false
>> secure_hash("secret") == hash
=> true

So our attacker has a match—bad news for any users with password "secret". This technique is known as a rainbow attack.

To foil a potential rainbow attack, we can use a salt, which is a different unique string for each user.8 One common way to (nearly) ensure uniqueness is to hash the current time (in UTC to be time zone–independent) along with the password, so that two users will have the same salt only if they are created at exactly the same time and have the same password. Let’s see how this works using the secure_hash function defined in the console above:

>> Time.now.utc
=> Fri Jan 29 18:11:27 UTC 2010
>> password = "secret"
=> "secret"
>> salt = secure_hash("#{Time.now.utc}--#{password}")
=> "d1a3eb8c9aab32ec19cfda810d2ab351873b5dca4e16e7f57b3c1932113314c8"
>> encrypted_password = secure_hash("#{salt}--#{password}")
=> "69a98a49b7fd103058639be84fb88c19c998c8ad3639cfc5deb458018561c847"

In the last line, we’ve hashed the salt with the password, yielding an encrypted password that is virtually impossible to crack. (For clarity, arguments to hashing functions are often separated with --.)

Answer 1

Rainbow tables are expensive to compute. Without the salt, you can build a rainbow table once that can be used repeatedly, since the password "password" will always yield the same hash (md5=5f4dcc3b5aa765d61d8327deb882cf99, sha1=5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8) and is thus easy to identify in a password database.

With a salt, you have to compute a rainbow table for each salt you encounter. A good-sized salt, say 32 bits (ideally, 128 or even more), means you have to compute a rainbow table for every password you want to crack, thus largely defeating its purpose.

Answer 2

Yes, you are right, if somebody had knowledge of your algorithm and the salt, he could generate a rainbow table. However, generating a rainbow table takes a long time the more characters are allowed.

So for example, if you have an password consisting of 10 characters, which all are numbers, you have 10^10 possibilites. If you allow lower and upper case alphabetical chars, this goes up to 62^10 possibilites, a mere 8.39 * 10^17 permutations; and that's only for 10 character passwords, you also have to take into account any length below that and above, depending on the length of password you allow.

It takes a long time generate such a table, while rainbow tables for the algorithm itself might be readily available, the salt modifies the algorithm to make it your own, and the possibility for a table existing for that is very low.

Answer 3

Salt is to stop someone from pre-computing a "reverse" lookup table that allows an attacker to quickly find a password that results in the target hash. Creating one of these tables is as much work, computationally, as brute-forcing the target password space, so it's only worthwhile if you can use the table on many targets.

Salt prevents this; the attacker would need to account for the salt when they generated the table, so the table would be good for only a single target, and the attacker is back to brute force.

Answer 4

If you use salt (even if it is public but uniqueto a site) you will get a protection from hash-dictionaries, where often used passwords are already hashed.

If your salt is secure then they can not brute-force it using supercomputers. They have to check every possible password with your server (which let's hope has some form of bruteforce-protection).