Cryptographic Hashes and salt values

[Chronicator]

I understand that encrypted passwords run through an algorithm to produce a hash, that is stored in the password database. Also, with salting, a salt value is added to the original password, which produces a hash and is stored in the database along with the random salt value.

This method is used to combat rainbow attacks, which can convert hashes into plain text passwords.

However, if you used a rainbow table to convert the hash into a "password"(which would actually be the password + the salt), couldn't you just remove the salt value that you found with the hash in the database? If that were the case then salting wouldn't really make a password much more secure, which is why I'm confused. If someone could explain this in detail that would be great.

 

[Mark R]

Rainbow tables are essentially compressed reverse-dictionaries which contain most of the passwords with specified parameters (e.g. 7 characters A-Z + 0-9). Using the rainbow table, you can take a hash to see if a password exists that produces it.

By adding a salt to the passwords prior to hashing, you make the password domain more complex - so if you have a 16 character salt using the range A-Z, a-z, 0-9 + symbols; then suddenly the "password range" that you need to search is in the 20+ character range, which is so large that it is impractical to build a rainbow table which covers that range.

Rainbow tables for limited ranges of 8 and 9 character passwords are commercially available, but the file sizes are in the multi TB range, and purchase prices are in the multi $k range, representing the enormous amount of computational effort involved in building these tables.

If you use a single salt for an entire database, it may be possible to build a custom rainbow table for common passwords, taking the salt into account when building the table. However, you would have to build a whole new rainbow table for each salt. It each password has it's own salt, then a rainbow table approach becomes pointless.

 

[jvroig]

I understand that encrypted passwords run through an algorithm to produce a hash, that is stored in the password database. Also, with salting, a salt value is added to the original password, which produces a hash and is stored in the database along with the random salt value.

This method is used to combat rainbow attacks, which can convert hashes into plain text passwords.

(Before I start: minor nitpick - passwords are not "encrypted", they are "hashed". This distinction might be helpful later on).

I think I see where your confusion is, so I quoted the relevant portions of your post above.

Rainbow attacks don't "convert hashes into plain text", at least not in the way we normally imagine when we encrypt something then decrypt it later on. Encyption+decryption follow an algorithm to transform something from an original state to an encrypted state, and then from the encrypted state back to the original state. Hashes are one-way, and for good reason: there is a loss of information (hash algos produce fixed-length hashes, and that right there shows you it cannot possibly account for all possible inputs, therefore information is lost, and collisions are possible).

Going back to Rainbow attack, this is just trying to "crack" a password using a "rainbow table": just imagine it is a big lookup table like a dictionary - it lists words (passwords) along with the corresponding hash, like so:
"dog" --> abc1236575ef
"qwerty" --> 12335bcf3212
"secret" --> 30654fffab768

Of course, it will have millions of words in them.

The way you can "attack" a password using a rainbow table is simply to see if the password hash (you don't actually have the original password, all you have is the hash(es) retrieved from a database hack) in question (or hashes in question) are listed in your rainbow table, and this is a straightforward lookup operation. For example if I examine a hash "30654fffab768", it will result in the word "secret", which means I've 'cracked' this hash.

(Technically, I am describing a plain dictionary attack. Rainbow tables are a refinement of the plain old dictionary that saves an incredible amount of space using hash chains. However this distinction is not important in figuring out how a salt will save you from either a dictionary attack or a rainbow table - both of these attacks are technically obsolete already, in the sense that if only everybody stored passwords correctly, none of these attacks would be in the least bit useful).

From the mechanics drawn above, you can see that rainbow attacks are powerful in that it seems to be able to "convert" hashes into plaintext, but only because it actually does a plain old lookup operation (like a "SELECT * FROM rainbow_table WHERE hash='30654fffab768'" in SQL terms if that helps you imagine it better). But in reality, there is no algo behind it that can reverse a hash (remember what we said earlier - hashing is different from encryption, and a notable difference is there is a loss of information when hashing due to any input being transformed into a fixed-length hash; therefore it is impossible to reverse a hash due to several inputs actually possibly resulting in the same hash - but this is an issue for a different day). Therefore, if there is a hash that is not listed in the rainbow table, the rainbow table is powerless to "crack" this hash.

This is where a salt comes in. If my password is "secret" (just to continue with the example) and it's hash is "30654fffab768", and it is listed in the rainbow table, then the attacker will immediately be able to determine my password. But what if it is salted? If the salt is, for example, "96bvbkf876274234", then my password would effectively be "secret96bvbkf876274234", and the resulting hash would be very different from the original "30654fffab768". Let's just say the hash is "aaaaaa99999" for the sake of discussion.

It is now unlikely that the rainbow table has an entry for "secret96bvbkf876274234", because the salt effectively made it into random jibberish. Rainbow attack foiled.

But the salt is not secret, what's stopping the attacker from using your salt to hash all of his millions of words and creating a new rainbow table out of it?
Nothing. But that already defeats the purpose of a rainbow table - it's precomputed (pre-built, you might say) to save you the time and effort to produce one in the first place, so you don't have to resort to a brute-force attack. If you force the attacker to go this route, you've stopped him from gaining any advantage through a rainbow table, and instead has resorted to plain brute force.

Even better, if your salts are unique per user (and they should be), then generating a new rainbow table using your salt is completely out of the question, since such a dictionary would then be useful for only 1 user, and another will need to be done for the second user, and then the third, and so on.

For proper password storage, see this post I made last year.