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.

Subscribe to Kavoir: blog feed

You should also read:

EllisGL March 5, 2010 at 4:53 am

I usually try doing
$salted = hash(‘sha512′, $password.$userid.$username.$email.$joined.$lastLogin);

Each time they logged in the password would be re-saved with a fresh saltyness

Yang Yang March 5, 2010 at 8:41 am

Thanks Ellis, that’s a nice tip!

cyberRoze March 15, 2010 at 3:05 pm

that was great tip EllisGL, tnx

Imb April 28, 2012 at 10:14 pm

I must commend you for that really, I mean REALLY good idea right there.

Josh Johnston March 10, 2010 at 7:01 am

In the end, no amount of salting will keep a hashed password safe from a sufficiently powerful brute force attack. Your best bet is to prompt a user to reenter their password or some other identifying information whenever they are about to view or make any changes to sensitive information.

Yang Yang March 10, 2010 at 12:06 pm

Thanks for the comment, Josh.

However, random salting with lengthy salts can make the reverse-hashing so painfully time-consuming that 99.99% of the applications out there should have a good security bet with it. Because it’s just not worth it to spend so much time on cracking them.

No one nor any security approach can completely prevent cracking once and for all. We just increase the cost of cracking to an unbearable point. That’s what we do.

MichielH March 10, 2010 at 11:38 pm

It might be worth looking into PBKDF2 (RSA lab’s password based key derivation function). The function combines a good “salt function” (like hmac) with key strengthening. Add a strong hash function like Whirlpool and you’re good to go for a while :-). Someone posted an implementation of it on php.net at http://www.php.net/manual/en/function.hash-hmac.php#92684 .

Yang Yang March 11, 2010 at 9:09 am

Awesome tip, thanks, Michiel!

matth March 11, 2010 at 5:38 pm

Hey guys seriously,
I don’t think saltiness is that safe. What about adding a captcha after 3 login mistakes?
This way is much simpler, faster on server side and nobody is gonna crack your password .
But well, maybe I’m missing the point.
Yes? No?

ralbon March 15, 2010 at 11:01 pm

The problem is that if someone steals the database or somehow gains access to it, then application-level security measures (like a captcha) becomes totally moot.

y0 August 12, 2012 at 8:25 pm

Great article, and EllisGL great idea with resalting with the last login each time.

MichielH is completely right PBKDF2 with a whirlpool hash is the right path imo. I found the article over at http://crackstation.net/hashing-security.htm to be a little bit more thorough and touch upon a few things in more detail. It also discredits this paragraph completely:

“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.”

As quoted from the other article:
“Here are some examples of poor wacky hash functions I’ve seen suggested in forums on the internet.

md5(sha1(password))
md5(md5(salt) + md5(password))
sha1(sha1(password))
sha1(str_rot13(password + salt))
md5(sha1(md5(md5(password) + sha1(password)) + md5(password)))

Do not use any of these. None of the wacky combinations provide any additional security.”

Regardless both of these articles have provided great insight to my question “How do I securely secure my users passwords in my database?”

Cheers

Rob October 19, 2012 at 12:47 am

I’ve implemented a sleep function to be called for each login attempt:

if (isset($_SESSION['TIMEOUT_SLEEP'])) {
$_SESSION['TIMEOUT_SLEEP'] = $_SESSION['TIMEOUT_SLEEP'] * 2;
}
else {
$_SESSION['TIMEOUT_SLEEP'] = “0.2″;
}
$sleep = $_SESSION['TIMEOUT_SLEEP'];
sleep($sleep);

By the 8th try, the lag becomes so long that frustration would be sure to set in. Obviously this can be reset by restarting the browser, but it still adds a layer of inactivity to the login attemps.

Rob October 19, 2012 at 1:00 am

Also, using a honeypot method may work as well. For instance:

So just use password2 as the legitimate password and ignore the login if a value is entered for password.

Comments on this entry are closed.

{ 2 trackbacks }

Previous post:

Next post: