Monday, May 16, 2011

More On Seasoning (of Passwords)

More information about passwords, first from Jan-Willem:
In your post you quote "Mean On Sunday" as writing that there is no way to crack a large number of hashed passwords. Unfortunately, in practice this is not true.

You can think of a hash as a fingerprint. It's just a relatively small derived property of something else. Just as you can identify a person with only his fingerprint, so you can identify a password using only its hash. And just as with a fingerprint, you can't use it to calculate all the details of the original (person or password). Outageddon has demonstrated why you'd want to use this: if your database is ever hacked, the hackers will only have the hashes (fingerprints), and not the original passwords.

Now for the bad news. While you can't efficiently calculate the reverse of a hash, i.e. the original password, you CAN calculate the hash for every word in the dictionary, and store these hashes along with the corresponding words in a database. (See
http://en.wikipedia.org/wiki/Rainbow_tables.) This will take a long time, but you only need to do it once, and it's easy to parallelize over hundreds or thousands of computers. Once you have such a database, you can very quickly look up hashes and find the corresponding passwords.

This approach only works if the original password was in your dictionary, which sufficiently random passwords won't be. But in a database of millions of passwords chosen by everyday people, you can safely assume you'll get lots and lots of hits. Especially if your dictionary contains variations like "p4ssw0rd" and "password123".

There are things Sony could have done to defend against this, primarily using a technique called salting, where some random data is added to a password before it is hashed, thus ensuring that it's random enough to not be in most rainbow tables. I hope Sony used this, but I haven't read anything confirming or denying this. So, if people used their PSN passwords for anything important besides PSN, they'd better assume that it's compromised...

Next, additional information from Garth Pricer:
Yes, the Sony passwords were hashed. However, what we haven’t been told is whether or not they were salted.. The rabbit hole on cryptography can go pretty deep, but the short (and mostly accurate) takeaway is this- Hashing passwords make brute force attacks time consuming, but massive tables exist of precomputed reverse cryptographic hashes. These “rainbow tables” can reduce the time it takes to reverse a hashed password to mere seconds. There’s a further counter-measure to rainbow tables known as Salting. This is kind of like multiplying the hash password value by another variable. If this variable is different for each password, rainbow tables become effectively useless, because you’d need a separate rainbow table for each and every salt value.

So did Sony actually salt the hashed passwords? And if so, did they do so properly, changing the salt value each time? I’ve heard they didn’t, but I have no idea how much credulity to give those allegations. Consider this, however- Last year, fail0verflow derived Sony’s ECDSA private key from its public key. How did they manage this incredible feat, something that should have taken currently infeasible levels of computing power? Well, instead of using a random number as part of the calculation, Sony’s signing software used a fixed value, leaving the derivation a simple exercise in algebra. So did they properly salt their hashed passwords? I don’t know, but if I was a betting man, I know where I’d put my money.

Site Meter