Friday, June 8, 2012

The Real Lesson of the LinkedIn Password Hack, pt2

In part 1 I explained the logic behind the first password best practice that LinkedIn was just barely smart enough to use. Now we explore the simple - yet shockingly effective - ways to further enhance password security.

Password Best Practice #2: Use a random salt to produce unique hashes.
A “salt” (no clue why it’s called this) is simply extra random text that is added to your password. Instead of encoding “mypassword” the site will encode “mypassword/2dsdjkl23r”. Notice the different result:

91dfd9ddb4198affc5c194cd8ce6d338fde470e2 = “mypassword”
eb8b3a04fb5bb65ecc02f40e83fa4d8065b26af6 = “mypassword/2dsdjkl23r

And every user gets her own random salt. So all of the fools who used the weak “mypassword” will end up with different encodings:

6097a22f84896b07dcd240f18b2a79ff84bec499 = “mypassword/8sadfljk23j2d08
85673bdb67447ca772199344de3fbb9ddb360368 = “mypassword/jkl34rjsdf89kl

So even if one “mypassword” account is compromised, the other “mypassword” fools are still safe, for now. Better.

But even this isn’t perfect. 

It turns out that the salts have to be stored out in the open, unencrypted (sounds odd, but it’s actually pretty logical; you can google it to find out why).

The hacker can see your salt so now he just has to add it to his dictionary of common passwords, encode them, and test for matches:

a3f60c5d228c7835cb31d950f34db378950513e6 = “password/2dsdjkl23r”
dc7c326296b42c0d43349087ac5d94e437da8bff = “password1/2dsdjkl23r”
e5497803dc75b80e5f9375919c372bcbed61f29e = “thepassword/2dsdjkl23r”
eb8b3a04fb5bb65ecc02f40e83fa4d8065b26af6 = “mypassword/2dsdjkl23r”

Match! The hacker now knows your password. But because your salt is different from everyone else's, none of these computations are relevant for anyone else's account. He’ll have to recompute his entire dictionary of common passwords for every single account. That’s an order of magnitude more work. Good.

But we can make it even more painful for the hacker:

Password Best Practice #3: Iterate. Like, a lot.
Here’s a cool fact about the encoding algorithm: it can encode its own output ad infinitum. Let’s salt and encode our password:

eb8b3a04fb5bb65ecc02f40e83fa4d8065b26af6 = “mypassword/2dsdjkl23r”

and the run that resulting “eb8b3a04fb5bb65ecc02f40e83fa4d8065b26af6” through the encoder. We get:


Now let’s run that through the encoder. The result:


We can keep doing this as many times as we like. Security folks recommend a minimum of 1,000 iterations!! A modern computer can rock these iterations in a matter of milliseconds. No big, but now you’ve made life really difficult for the hacker. He has no way of knowing if you did 10 iterations or 1,000 or 50,000. So now he has to compute each of his dictionary passwords – with your specific salt – over thousands of iterations each, just to see if he gets a match:

a3f60c5d228c7835cb31d950f34db378950513e6 = “password/2dsdjkl23r” (1 iteration)
12fd772862071a3271196cc7a7e160ca73e5545b = “password/2dsdjkl23r” (2 iterations)
7da106033e14deed965fd9f2d7ace565c9c04121 = “password/2dsdjkl23r” (3 iterations)
fb9e5f4deae37c6a54d2d405a15ae4ce984c2b1b = “password/2dsdjkl23r” (4 iterations)

…and so on for 1,000 or 50,0000 iterations or however many he has patience for, just to see if your password was “password” (it wasn’t. Phew!). Then he starts over and runs "password1" through thousands of iterations. No match. And so on for his entire dictionary of common passwords.

This is now getting excruciatingly computationally intensive for your hacker. He can still do it, but all that computation is only valid for your particular salt. He has to do it all over again for the next user. It’ll take him a crap-ton of time to crack all 6.5 million passwords this way. The sun might supernova before he’s done. No joke.

That is good security. That’s what I implemented for EssayTagger. And I know these best practices because I spent a whopping ten minutes on Google.

LinkedIn didn’t salt their passwords and they iterated exactly once.

Conclusions and lessons learned
Now do you see why LinkedIn’s password fiasco is so horrifying? Remember that LinkedIn’s paltry encryption could be hacked by a human by hand. But just add a salt and a couple thousand iterations and now a supercomputer cranking until the end of the Earth’s existence might not be able to crack all 6.5 million passwords in time. That difference in security would have cost LinkedIn all of a couple milliseconds of compute time per login. Trivial compared to the immense security boost they would have achieved.

The shocker isn’t that LinkedIn was hacked. No, the shocker is that they left our passwords so vulnerable and failed to follow basic encryption best practices.

So figure out which of your developers coded the password encryption for your company and ask: “Are our passwords salted and how many times are we iterating the hashing function?”

If he says, “uh, what?”, you have a problem that you need to address ASAP.

Further reading
The resource I relied on to guide my password security policy:

A similar, but even harsher take on LinkedIn and, now, eHarmony's password security: