Security 106: The Importance of Key Stretching

One thing that you’ll find with most hash functions is that they are designed for speed. With that in mind, you would think that a hash that is both secure and fast would be good, right?

NOPE.

Computers are normally all about speed and efficiency – except for with passwords.  When creating password hashing algorithms, you should aim to make them as slow as possible (within reason).

Take a second and read that again, because it’s actually a bit weird.  There’s a really good reason to aim for a slow hashing algorithm, and it all comes back to the goal of making Rainbow Tables ineffective or uneconomical.

Let’s look at this from a user’s point of view, versus a hacker’s point of view.  If you’re hashing with a speedy hash algorithm, it might take your database 20ms or so to calculate the hash for a given string.  That means, from the time your user clicks the “Log In” button until they see their user account page, about 20ms is spent confirming their password matches the hash.  Is it going to make much of a difference to that user if, instead of 20ms, it takes 100ms to calculate the hash?  No?  What about 200ms?  What about 500ms?  Even at a whole second’s worth of hashing time, the user will only just notice the delay, because the password hash is such a small percentage of the actual page load time.

Now let’s look at it from a hacker’s perspective.  Mining software running on an unremarkable graphics card can calculate 200 million hashes per second.  Now, if we want a rainbow table of all the passwords from 1 to 7 characters long, including a-z, A-Z, 0-9, we have a total of 3579345993194 possible combinations.  At 200 million per second, that should take a bit under 300 minutes to calculate a matching rainbow table.  But if we’ve done something to slow down the hashing function by a factor of twenty, the 300 minute job just turned into a 6000 minute job for the hacker… and the user hasn’t even noticed.

One very effective way to slow down a hashing algorithm is with a process known as key stretching. Key stretching is the process of iterating over a hash several thousand times, or in simpler terms, taking the output hash and feeding it back into the algorithm as an input. What this means is that the hashing algorithm is designed in such a way that it will, under set conditions, take a set amount of time to complete (longer than it would take if only one iteration was performed). This time would be considered reasonable for most users, but when multiplied over the number of possible combinations that a password could be made of, would slow down the rainbow table creation process immensely.

So… are all hashing algorithms as good as each other?  No way.  Our next installment will have a brief look at this.

———————————————————————————-

This post forms one part of our Security series. You can find links to the other editions here:

Security 101: What is Encryption?
Security 102: What is Hashing?
Security Interlude: The real-world difference between Hashing and Encryption
Security 103: Rainbow Tables
Security 104: Improper Password Storage
Security 105: Seasonings (or Salts and Peppers)
Security 106: The Importance of Key Stretching
Security 107: The Hashing Algorithm, and why Bcrypt is your best friend
Security 108: The Other Stuff

———————————————————————————-