Slow Hashing

The majority of the Coding Horror: Speed Hashing post talks about speed based on MD5. It isn’t until the very bottom that you see this:

If you are a developer:

Use bcrypt or PBKDF2 exclusively to hash anything you need to be secure. These new hashes were specifically designed to be difficult to implement on GPUs. Do not use any other form of hash. Almost every other popular hashing scheme is vulnerable to brute forcing by arrays of commodity GPUs, which only get faster and more parallel and easier to program for every year.

I’m not sure why that wasn’t at the very top.

If you are still using MD5 to hash passwords (or worse, aren’t hashing passwords at all) then please stop and go use bcrypt. For those using PHP phpass is a great option.

For password hashes you want the process to be slow. There is of course a trade off. Here is a PHP example:

[sourcecode lang=”php”]
crypt( ‘password’, ‘$2a$12$usesomesillystringforsalt$’ );
[/sourcecode]

The $2a tells crypt to use CRYPT_BLOWFISH. The $15$ is the cost parameter, ranging from 04 to 31. Running this on my Core 2 Duo laptop takes 0.4 seconds. Increasing the cost parameter increases the amount of time it takes to compute the hash. For my Core 2 Duo it looks like:

Cost 12: 00.4 seconds
Cost 13: 00.7 seconds
Cost 14: 01.4 seconds
Cost 15: 02.8 seconds
Cost 16: 05.5 seconds
Cost 17: 11.1 seconds
Cost 18: 22.1 seconds

While having a cost of 18 might sound exciting from the point of view of making brute force attacks more difficult it would make for a horrible user experience. Remember that each time a use fills out the log in form on your site you have to hash the password they entered to see if the matches the one your in your database. Waiting 22 seconds per log in attempt would drive your users nuts.

So how high should the cost be to make brute force attacks impractical, but low enough to still provide a good user experience? Some of that is going to depend on the power of your servers, but for now lets stick with my Core 2 Duo example. If your possible password combinations were lower case letters, upper case letters, and numbers for a 7 character string then you’d be looking at 62 ^ 7, or 3,521,614,606,208 combinations.

The speed hashing post indicated that for MD5 all 7 character passwords of that type could be calculated in 4 minutes. If we choose a cost of 13 (meaning 0.7 seconds per password) and I’ve done my math correctly, it would take 159,528 years to do the same thing on my Core 2 Duo.

If your server is 10 times faster than my Core 2 Duo then a cost of 13 may still be fairly reasonable. A single hash would take 0.07 seconds and computing hashes for all 7 character passwords would take 15,952 years. Even another 100x increase in speed would still mean 159 years.

None of this takes into consideration the possibility of spreading the brute force attack across multiple servers of course. But the concept is still the same. Slower hash techniques mean you’ll need a larger number of servers to compute all of the possible combinations in a reasonable amount of time compared to a very fast hash, like MD5.