The Bike Shed

Security

 

LinkedIn Password Leak: Salt Their Hide

If it does not take a full second to calculate the password hash, it is too weak.


Poul-Henning Kamp


6.5 million unsalted SHA1 hashed LinkedIn passwords have appeared in the criminal underground. There are two words in that sentence that should cause LinkedIn no end of concern: "unsalted" and "SHA1."

Let me walk through the process of password protection and explain why unsalted passwords are only infinitesimally better than plaintext passwords:

User Alice selects and enters a new password for use with some kind of computer service: "LIMaabotM." The computer needs to be able to check if Alice types the right password the next time she logs in, and so it stores the password in a file or database. This is obviously bad, because anybody with read-access, legitimate or illegitimate, can read Alice's password and login as Alice. So what smart people figured out in the 1970s was that you should store a one-way hash of the password instead.

When somebody tries to log in as Alice, the password that person enters is run through the same one-way hash, and if the output matches what is in the database, that person knew the right password. This works great, and now Evil Sysadmin Bob and Industrial Spy Charles can no longer read Alice's password. But they can still try to guess it. If they run all possible passwords they can imagine through the same one-way function, and one of the outputs is the same as the value the database has for Alice, they have found something that will work as a password for Alice's account.

An important detail here is that they can do that on any computer or computer-cluster they have access to without anybody noticing and that is apparently why the password file was generated: the criminals needed help guessing the passwords.

This is the first place LinkedIn failed utterly: Calculating the SHA1 function is very, very fast. A regular computer can crunch from 10 million to 100 million of them per second using the GPU, making it a trivial task to check even very large lists of potential passwords. The obvious way to make this harder is to make the calculation take more time, so instead of:

scrambled_password = HASH(password)

we could make it:

scrambled_password = HASH(password)
       for (i = 0; i < 1000; i++)
scrambled_password = HASH(scrambled_password)

In all probability, 1,000 is far too small a value and should be replaced with some suitably large number so that the loop takes a full second on a fast computer. A second is a minor detail for the user logging in, but slows the attackers' brute-force attack by a factor of 10,000,000 or more.

But we're not done.

On a system with many users, the chances that some of them have chosen the same password are pretty good. Humans are notoriously lousy at selecting good passwords. For the evil attacker, that means all users who have the same hashed password in the database have chosen the same password, so it is probably not a very good one, and the attacker can target that with a brute force attempt.

This became a problem and was solved in the 1980s: To fix the problem, we have to make sure that users do not have the same hash-value stored, even if they have the same password. And that is what a salt does: When a user changes her password, the system picks a random number or string X, and calculates

scrambled_password = SLOW_HASH(X + password)

and stores X along with the scrambled password in the database.

Even if all users choose "LIMaabotM" as their password, they all get a different X, and, therefore, different scrambled passwords, and the attacker will only discover this by the time he bruteforces the second or third password, and starts to detect a pattern.

LinkedIn didn't do this either.

The 6.5 million hashed passwords in all likelihood represent far more users than that, because everybody who chose "qwer5678" as a password shares a single entry in that file. I wouldn't be surprised if 6.5 million was the number of unique passwords all LinkedIn users have chosen, as there is, after all, only so much imagination to go around.

The fact that the leaked file does not have usernames attached is no consolation, it just means that whoever leaked it knows the value of what they have, and wants to keep the haul for themselves.

But we are still not done:

By the 1990s, people had started to experiment with putting computing into programmable chips, which means that a password protected with the standard UNIX crypt(3) function could be bruteforced in far too short time. The fix I applied back then, was to switch to a much more complex and hardware-unfriendly hashing function based on MD5. It got the name "md5crypt," and is probably one of the most widely used password scramblers today, which just goes to show that back then I totally failed to communicate my central insight. So let me again:

You can change your SLOW_HASH() function any time you want, provided you also store which function was used in addition to the salt and the scrambled password. This means that as computers get faster, you can increase the complexity of the function to slow it down, or if somebody finds an analytical attack that weakens your password scrambler, you can switch to a stronger one. The next time your users change their passwords, the extra strength kicks in. This property of password protection is what will allow LinkedIn to upgrade their password storage security now, without forcing all users to change their passwords at the same instant. As I said, md5crypt is pretty much the "default" password scrambler for a lot of people, but even though it fulfilled all relevant criteria back in 1995, I no longer consider it safe enough (see: http://phk.freebsd.dk/sagas/md5crypt_eol.html).

Recent research has managed to get a GPU processor very close to 1,000,000 md5crypt operations per second (see: http://2012.sharcs.org/slides/sprengers.pdf) and that means that any 8-character password can be bruteforced in approximately two days.

Conclusion

LinkedIn is learning fast right now, according to their damage control missives, they have now implemented salting and "better hashing." But we have yet to find out why nobody objected to them protecting 150+ million user passwords with 1970s methods.

And everybody else should take notice too: Even if you use md5crypt, you should upgrade your password scrambling algorithm. As a rule of thumb: If it does not take a full second to calculate the password hash, it is too weak.

LOVE IT, HATE IT? LET US KNOW

feedback@queue.acm.org

Poul-Henning Kamp (phk@FreeBSD.org) has programmed computers for 26 years and is the inspiration behind bikeshed.org. His software has been widely adopted as "under-the-hood" building blocks in both open source and commercial products. His most recent project is the Varnish HTTP accelerator, which is used to speed up large Web sites such as Facebook.

© 2012 ACM 1542-7730/11/0600 $10.00

acmqueue

Originally published in Queue vol. 10, no. 6
see this item in the ACM Digital Library


Tweet



Related:

Geetanjali Sampemane - Internal Access Controls
Trust, but Verify


Thomas Wadlow - Who Must You Trust?
You must have some trust if you want to get anything done.


Mike Bland - Finding More Than One Worm in the Apple
If you see something, say something.


Bob Toxen - The NSA and Snowden: Securing the All-Seeing Eye
How good security at the NSA could have stopped him



Comments

Displaying 10 most recent comments. Read the full list here

Mike | Sat, 09 Jun 2012 07:38:16 UTC

@Matt: In your calculation where you came up with 600,000 years, you used the ops/sec of md5crypt (1,000,000/sec) LinkedIn was not using md5crypt, but SHA1, which can be brute forced much faster. You are also assuming a single computer. Presumably the attackers would have a botnet with tens of thousands of computers or more.

Ben | Sat, 09 Jun 2012 12:37:52 UTC

"The 6.5 million hashed passwords in all likelihood represent far more users than that, because everybody who chose "qwer5678" as a password shares a single entry in that file." So how are the password statistics concerning this leak even possible when no other information but those pw hashes are available?

Nate | Sun, 10 Jun 2012 04:37:30 UTC

If you had an existing salted, SHA1 password database, couldn't you convert everyone instantly to a new combined algorithm that first computes the salted SHA1 and then passes it through bcrypt using the same or (even better) a second salt. Then, assuming your system is un-compromised, you'd have a very secure password hash without requiring users to log in or change passwords. Any opinions on whether that would work? Seems like it would in my opinion. I'd rather not wait for users to log in/change passwords to ensure the password db could not be compromised by brute force. The one I'm dealing with is already salted, but uses SHA1 and I'd like to take it to the highest standard.

shackrock | Sun, 10 Jun 2012 15:36:59 UTC

I always have used this webpage as a guide: http://elbertf.com/2010/01/store-passwords-safely-with-php-and-mysql/ - which seems to cover all of your statements from the article, agreed?

Anon | Tue, 12 Jun 2012 00:05:48 UTC

"Recent research has managed to get a GPU processor very close to 1,000,000 md5crypt operations per second ... and that means that any 8-character password can be bruteforced in approximately two days." Your calculation assumes an 8-character lowercase a-z password, not "any 8-character password". If you assume that your password can be made from the 52 upper and lower case letters, the 10 digits, the 32 keyboard symbols, and spaces, your time goes from 2 days to 200 years.

Poul-Henning Kamp | Tue, 12 Jun 2012 10:27:54 UTC

@Anon: Please see the SHARCS conference presentation linked to in the article for stats.

Michael | Tue, 12 Jun 2012 15:32:57 UTC

@PB | Fri, 08 Jun 2012 09:08:17 UTC "Could it be changed even sooner than that by generating salted hashes of the stored hashes? Then when someone logs in you can simply try both?" Shouldn't the hash and not the password be transmitted over the internet? This also distributes the computation issue to all user computers instead of a single webserver.

Cory House | Wed, 13 Jun 2012 15:37:24 UTC

@Michael - Login should use https to assure sending the plain text password is safe. The password must be hashed on the server to avoid exposing the hashing algorithm and salt in client-side code.

Michael | Thu, 14 Jun 2012 09:45:17 UTC

@Cory House: Eh, the salt and algorithm should not need to be secret. The password should. If the channel is safe enough to transmit a plain text password, it is also secure enough to transmit a hash of that password. If the channel is being sniffed, it is also better that a hash is discovered, which is only valid for a single website, due to the salt, while a password is likely valid for many websites.

bendra | Tue, 17 Jul 2012 22:04:51 UTC

Hello, Interesting article and comments! One thing this has me wondering is: if GPUs are so darn good at hashing, is there anyone who is using GPU-based hashing on the server to log users in? It would take quite a load off the server, particularly if you are using a slow adaptive hash no?
Displaying 10 most recent comments. Read the full list here
Leave this field empty

Post a Comment:







© 2014 ACM, Inc. All Rights Reserved.