January 06, 2012

Key Stretching

I've covered some ways to handle storing passwords before, but that was just one method of strengthening your database against attacks.  Next, we'll look into key stretching in order to slow down potential attackers.

Hashing takes time, so if a hashing algorithm k time to perform, then hashing n times will take nk time to perform.  This helps a bit since hackers can test around 9.8 billion passwords per second. Yup, you read that right.  With the ability to test 10 billion passwords per second, we need all the help we can get by slowing down an attackers brute force method.

This baby can probably crack passwords faster than you can say "O GOD, HOW MANY CUDA CORES DOES IT HAVE?"
This is where key stretching comes in handy.

Key stretching is the process of making a key more secure against brute foce attacks by increasing the time it takes to test each possible key.  One such way of increasing the time is my hashing multiple times, like so:

key = hash(password)
for (i = 0; i < 65536; i++) {
  key = hash(key)

However, that method may be collision prone since if two keys hash to same value at any point during the loop, they will have the same output hash.

A better method is to use the key, the password, and the salt:

key = hash(password + salt);
for (i = 0; i < 65536; i++) {
  key = hash(key + password + salt);

And that's pretty good: we've just increased the time it takes to generate a hash of the password by 65535 times.  But that still means hackers can test around 150,000 passwords per second.

In my next password oriented blog post, I'll cover different hash algorithms that you can use to store your passwords.


Post a Comment