Wednesday, February 9, 2011
Are you sure SHA-1+salt is enough for passwords? Posted by Jarno @ 08:39 GMT

The anarchic Internet group called Anonymous recently hacked HBGary Federal and rootkit.com, an online forum dedicated to analyzing and developing rootkit technologies. All user passwords at rootkit.com have been compromised.

Given this compromise, I'd like to point out one of my favorite topics in application security — password hashing.

I've forgotten your password again, could you remind me?

It's all too common that Web (and other) applications use MD5, SHA1, or SHA-256 to hash user passwords, and more enlightened developers even salt the password. And over the years I've seen heated discussions on just how salt values should be generated and on how long they should be.

Unfortunately in most cases people overlook the fact that MD and SHA hash families are designed for computational speed, and the quality of your salt values doesn't really matter when an attacker has gained full control, as happened with rootkit.com. When an attacker has root access, they will get your passwords, salt, and the code that you use to verify the passwords.

And this is the assumption any security design should be based on; an attacker has access to everything that is on the server.

Salt is primarily intended to prevent precomputed attacks, also known as rainbow tables. And a common assumption has been that as long as precomputed attacks are prevented, passwords are relatively safe even if attacker would get the salt value along with user password.

But MD and SHA hash variants have been designed for computational speed, which means that an attacker can easily get billions of brute force attempts per second when using a video graphics display card for processing.

See: http://www.golubev.com/hashgpu.htm

Which means that even with single ATI HD 5970, an attacker can cover password space equivalent to a typical rainbow table (2^52.5 hashes) in 33 days. And it's a safe bet that a serious attacker will have more than one card for the job.

When an attacker has your salt values and code, the only thing that is protecting user accounts is the strength of passwords they are using, and people are not very good sources of entropy. By combining dictionary attack and brute force techniques it will not take very long to break a significant proportion of passwords, even for a large site with many accounts.

So what should be done to avoid this?

The first thing to consider is that passwords are very much like safes in the real world, what matters is not only the length of the code needed to open the safe that protects the contents, but also how long each attempt takes.

This clearly means that SHA1 or any other plain hash algorithm is clearly a no go for secure password authentication.

What you want to use is something that will not be trivial to brute force. Instead of doing 2300 million attempts per second, you want something that limits an attacker to 10,000 or 100,000 attempts per second.

And while using salt values is vital to proper implementation, it is not a silver bullet which will make your problem go away.

This requires a password hashing scheme that fulfills the following properties:

  •  Computational time required can be adjusted easily when processing power increases
  •  Each user can have unique number of iterations
  •  Each user hash is unique so that it is impossible to find out if two users have same password by comparing hashes

There are several such schemes to choose from:

  •  PBKDF2 http://en.wikipedia.org/wiki/PBKDF2
  •  Bcrypt http://www.openwall.com/crypt/
  •  PBMAC http://www.rsa.com/rsalabs/node.asp?id=2127

Each of the alternatives has their strengths and weaknesses, but all of them are far stronger than general purpose hash implementations such as SHA1+salt.

So if you are working with passwords, pick one of the schemes above, determine the number of iterations it takes your server check the password for the desired length of time (10, 200ms, et cetera) and use that. Have a unique salt value and iteration count for each user — anything that forces the attacker to focus on each account separately rather than being able to try against all accounts on each iteration.

Updated to add: I had accidentally put HMAC on the list of suggested schemes when I should have put PBMAC. Props to Matthew and Sagres for pointing out the error.

<<< From Brain to Stuxnet: 25 Years of Computer Viruses
Restrict USB Autorun: Update for Windows (KB971029) >>>