Password Hashing Done Right

2011-05-24T00:00:00-07:00

After reading a very informative piece by Coda Hale about the proper way to store a password, I thought i’d provide a bit of information on the topic to help drive his point home.

There are at least two important things to think about when generating and storing passwords for any application. The first is general password strength, and the other is how you store that password.

Strong Passwords

The first thing to consider when dealing with passwords is enforcing some general measure of password strength. All of the salting and encryption in the world won’t do you any good if you have users with passwords that are too short, easily guessable, etc. By enforcing a reasonable minimum length, and some rules for the composition of the password, you can introduce your first line of defence against brute force and/or dictionary attacks.

My personal stance is that the most important rule to enforce is password length. The simple act of adding a character to a password makes a brute force attack take an order of magnitude longer. 8 characters takes longer to brute force than 7, and 9 takes longer than 8, etc. I often default to 8 characters, so that’s the example I will use here.

For the purpose of this example, I’m going to build on the assumption that all of my passwords are made up of the following characters:

abcdefghijklmnopqrstuvwxyz
ABCDEFGHIJKLMNOPQRSTUVWXYZ
0123456789
!@#$%^&*()_+-=?

It is important to note that you may have more available characters, and you may have less. I’m going to base my example around these 77 characters. Again, the more characters available, the stronger a potential password is.

Your passwords are now made up of a minimum of 8 characters with 77 possible characters in each position. To calculate the number of total possibilities for this schema, the math is simple. Number of characters raised to the power of length of password, or more simply:

77 * 77 * 77 * 77 * 77 * 77 * 77 * 77 = 1,235,736,291,547,681

In plain english, that’s 1.2 quadrillion. Seems like a lot, doesn’t it? If you were a human trying to guess the password through brute force 00000000, 00000001, 00000002 etc and you could type passwords at a rate of 1 per second, it would take you just under 40,000,000 years (without stopping for coffee or bathroom breaks!)

If your computer, on the other hand, was trying to guess your password by means of brute force, it would take substantially less time. My laptop, as of May 2011, can generate roughly 1,300,000 guesses per second, and that’s based on unoptimized node.js code running on an already busy macbook pro. As Coda pointed out , there are methods available currently (for around $2,000 USD) that will allow for the generation of 5,600,000,000 hashes (not just attempts, full hashes) per second. Your 40 million human years is now broken down to 3 days before your 8 character password can be guessed.

The problem with relying on strength alone is that these numbers are going to change quickly, and leaving the onus on your users to come up with more and more unique/strong passwords is a horrible solution. Strong passwords increase the number of required guesses, but now you need to slow down the guessing.

Generating and Storing Password Hashes

Modern computers can generate hashes incredibly fast. While the example of 5,600,000,000 per second was a very specialized (albeit cheap) solution, your own computer can generate a standard MD5 hash very quickly. When you loaded this article, some simple code was run in the background, and determined that your web browser was able to generate 0 hashes per second. You would have made 0 attempts at an md5 hashed password in the time you spent reading this. As technology improves, so will the number of attempts per second. The same specialized application that attained 5,600,000,000 attempts per second a year ago may be able to do 10,000,000,000 next year.

What about SHA1, SHA256, or even SHA512

While methods like SHA512 are slower than MD5, they are not the answer. SHA512 will increase in speed on the same path that MD5 does, eventually allowing for billions or even trillions of attempts per second.

Enter bcrypt

Coda explains why to use bcrypt best with the following:

How? Basically, it’s slow as hell. It uses a variant of the Blowfish encryption algorithm’s keying schedule, and introduces a work factor, which allows you to determine how expensive the hash function will be. Because of this, bcrypt can keep up with Moore’s law. As computers get faster you can increase the work factor and the hash will get slower.

How much slower is bcrypt than, say, MD5? Depends on the work factor. Using a work factor of 12, bcrypt hashes the password yaaa in about 0.3 seconds on my laptop. MD5, on the other hand, takes less than a microsecond.

So we’re talking about 5 or so orders of magnitude. Instead of cracking a password every 40 seconds, I’d be cracking them every 12 years or so. Your passwords might not need that kind of security and you might need a faster comparison algorithm, but bcrypt

Basically, you can specify the amount of work bcrypt performs to generate your hash. As technology improves, you can increase the amount of work you do to derive your hashes, keeping up with the modern technology curve.

Until there is a massively parallel version of bcrypt that can benefit from CUDA/OpenCL, this method moves brute forcing your hashes back into the thousands/millions of years range. I’d say that is about as “difficult to brute force” as anyone can currently ask for.

Closing Thoughts

While this focuses primarily on the generation and hashing of passwords, and is meant to deal with ensuring the security of your passwords should your password database be compromised, it is not all you need to focus on when securing your password data. There are a host of other methods that can and should be used to ensure proper password handling such as lockouts, resets, etc. Other security measures can be covered in a separate post. This one covers the important thing:

Use bcrypt

Deploying Redmine on Amazon EC2

2011-05-03T00:00:00-07:00

It’s insanely easy to get Redmine up and running on Amazon EC2. I went through the process today and thought it would make sense to document it on here for others to read.

Why EC2

You may ask yourself, “Why EC2? Heroku has a free tier of rails hosting”. You’re right, they do. The difference is, EC2 gives you a full linux install with 10gb of persistent storage, whereas heroku gives you a 5mb database. Couple storage differences with the ability hook redmine up to your local git repo on your EC2 instance, upload files and documents, and do full backup snapshots to S3 out of the box, and EC2 seemed like an easy choice to me.

Start to Finish in 5 Minutes

If you don’t already have an EC2 account, go sign up for one now. You won’t be able to do any of this without an account. Once you are signed up, and in the EC2 management console, click on “Launch Instance”. A window will pop up showing 6 sections. Here is a quick overview of what to select in each section:

Choose an AMI

Click the Community AMIs tab
Set viewing to All Images
Type “bitnami redmine” in the box next to “Viewing”
As of writing this, the most recent version is 1.1.2 on Ubuntu with ebs as the root device. Find the most recent version in the list and click the appropriate “Select” button

Instance Details

Set instance type to Micro
Click Continue
Set any User Data you’d like, and click Continue again
Set any tags you’d like, and click Continue again

Create Key Pair

Create a new key pair (or use an existing set)
Download a copy of your keypair
Click Continue

Configure Firewall

Click Continue

Review

Click Launch

Adjust Security Group

Click on Security Groups in the left hand bar
Select your default group
Click the Inbound tab in the details pane
Add preset rules for SSH, HTTP and HTTPS
Click Apply Rules

Now, you can get your public dns name from your instances dashboard, and you should be up and running with a copy of redmine. To boot, this installation falls under the “free” tier of AWS, which means you won’t have to pay the hefty $0.02/hr cost of running this instance, if you’ve got no other instances running.

Happy Bug Tracking!

Warren Krewenki