Just Hashing is Far from Enough for Storing Passwords – How to Position against Dictionary and Rainbow Table Attacks

by Yang Yang on March 4, 2010

login passwordIt goes without saying that sensitive information such as passwords or pass phrases should never be stored in plain text in the database in the first place. The common practice is to hash the user password and store the resulted hash string. When the user tries to log in and supplies his password, it is used to generate a hash string to be compared to the one stored in database. If they are identical, the password is matched and the user authenticated because the chance of 2 distinct strings having the same hash string is so low that it’s deemed mathematically impossible.

This approach may be secure in the 70s of the last century, but barely any more. Thanks to unprecedentedly cheap computing power now, rainbow tables, the mapping function from hash strings to any possible combinations of keyboard characters (alphanumeric, punctuations, etc.) have rendered this password storage / validation method insecure. With a mapping table of trillions of hash to cleartext pairs, it takes only 160 seconds to crack the password “Fgpyyih804423” which most of us would generally agree is fairly safe.

What can we do?

Provide a random salt when you are hashing the secret text. For instance with the PHP’s SHA1 hashing function:

$my_hash = sha1('whatever salt you put here would do,,,???'.$secret);

As you can see, the salt string can be whatever you like, in a random manner, prefixed and / or suffixed to the secret text before it is hashed into a hash string which will be stored. This way, because the cracker has no idea what the salt is, there’s no way he can create the right rainbow table to perform the crack. Even if he does, he would have to specifically build a rainbow table to crack your database which can be time-consuming. Subsequently, to make this even more difficult for the cracker, you can use different salts for each of the password entries in the database:

$salt = generate_random_salt(); // your in-house function that generates a random salt, perhaps by uniqid('some random string', true)
$my_hash = sha1($salt.$secret); // the $salt must then be stored in your database on a per entry base
// this function is the same as hash('sha1', $salt.$secret), but a better algorithm would be hash('whirlpool', $salt.$secret)

When the salt string is a per application constant, you can store it rather obscurely somewhere in your application code. However when you use random salt strings, you will have to store it correspondingly with the hash string $my_hash in the database, or otherwise you won’t be able to generate the correct hash string of the password user provides for authentication against the one stored in database.

It doesn’t even matter if the cracker gets the database and knows all the random salts, because he’d have to create and run through a huge rainbow table specific to each of the random salts to crack just one password. It’s so squarely and prohibitively time-consuming that he’d definitely give up.

A better yet approach to defend against rainbow or dictionary attacks is to be creative in generating the hash string – such as taking the username string into the generation and implementing multiple layers of hashing, in a playfully diversifying manner.

At last, it is recommended that you generate the initial hash string (the one to be stored in database) by running 1000 iterations of hashing instead of just 1. The extra computing burden on your server is negligible while it will increase the time needed to crack a single password by 1000 times at the cracker’s end. The point is to make the hashing process as slow as possible rather than the other way around. As the cracking usually makes password guesses and trial logins at a much higher paced speed, the slowness will have a much more detrimental effect on the cracker than on your website.