Yesterday, LinkedIn confirmed reports that some member passwords have been compromised.
Here’s some info from their blog:
“It is worth noting that the affected members who update their passwords and members whose passwords have not been compromised benefit from the enhanced security we just recently put in place, which includes hashing and salting of our current password databases.”
Hashing and salting? Is that enough? That’s the question our own Jarno Niemela asked last year in this reprinted post (with updates).
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.
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.
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:
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.
Original post (and comments) here.
Leave a reply