[ale] unsalted hashes of 6 million linkedin passwords published on the internet

Fri Jun 8 12:42:19 EDT 2012

On 06/08/2012 11:26 AM, Ron Frazier (ALE) wrote:
>
> "Michael H. Warfield" <mhw at wittsend.com> wrote:
>
>> On Fri, 2012-06-08 at 08:54 -0400, Tim Watts wrote:
>>> Thanks for this Mike.  Great lesson as usual!
>>> On Thu, 2012-06-07 at 22:56 -0400, Michael H. Warfield wrote:
>>> RE Salts:
>>>> So it prevents some optimization in brute forcing
>>>> large tables of passwords (like the Linkedin dump). 
>>> I guess I don't quite see this.  If the salt is invariably stored
>> with
>>> the hash this sounds a bit like claiming base64 is a form of
>> encryption.
>>> The only way I can make sense of this is if the encoding of or
>>> association between the salt and hash is somehow a system secret.  Or
>> if
>>> you don't know the hashes are salted.  Am I missing something?
>> Without salt, the attacker would take a brute force password guess and
>> hash it once and compare that hash to all the hashes in the database.
>> One hash operation per guess to do all the hashes in the table and it's
>> a straight compare.
>>
>> With salt, you have to hash your password with the hash salt that's
>> there for each entry in the table.  So, if you have 6.5 million entries
>> in the compromised hash table you would likely have to hash the guess
>> with each individual salt (6.5 million is still a very tiny percentage
>> of even 2^48 so collisions are almost non-existent) resulting in 6.5
>> million hash operations where you would only have needed 1 hash
>> operation without the salts.  6,500,000:1 is quite an optimization and
>> that's why I said "large tables".  The larger the table, the bigger the
>> effect.
>>
>> The hash is a one-way function.  Even with the salt present with the
>> hash (necessary for verification) you can't reverse the hash back to
>> the
>> password so the presence of the salt doesn't weaken the hash.  It's not
>> any more secret than the hash itself and is necessary to compute the
>> hash given a password to test and verify.
>>
>> Here...  I'll give you an example from the shadow file (no, it's not an
>> active account but it's a real hash, you can try and brute force it if
>> you like...)
>>
>> *****:$1$mVyvPlQz$M02ivX0uzi6al7vWWu5X6.:15499:1:::::
>>                  ^^^^^^^^^^^^^^^^^^^^^^ Hash
>>         ^^^^^^^^ 48 bit salt - almost 3 * 10^14 possibilities.
>>      ^^ Algorithm 1 - md5
>>
>> This is a SHA512 hash pulled from a web page I had handy...
>>
>> *****:$6$QR3drPrQ$JLolPKyiVuXvea1F2IpbPx9F9PEV0s/IGcNCpm6ZrBA6AFDvwHPQG7EsTQHuUqxfCvlsuKRb.O7w5RLPyj8nS/:15119:0:99999:7:::
>>
>> Same format, just algorithm 6, sha512.
>>
>> With the salt, you can hash a password the user enters and, if it then
>> matches the hash you expect, you have a verification match.  That salt
>> has to be present with the hash at the point and time of verification.
>> In theory, they could be stored in different locations but, in
>> practice,
>> that really doesn't buy you much since they have to be retrieved
>> together and are tightly associated, so they're generally stored
>> together.  If that table is compromised, the brute force attacker would
>> then merely take the salt, combine it with the password he's using to
>> guess, and then compare.  But, without a salt, he only has to hash the
>> password once and do a simple compare to all the entries.  Grep would
>> do
>> the job.
>>
>> Regards,
>> Mike
>> -- 
>> Michael H. Warfield (AI4NB) | (770) 985-6132 |  mhw at WittsEnd.com
>> /\/\|=mhw=|\/\/          | (678) 463-0932 | 
>> http://www.wittsend.com/mhw/
>> NIC whois: MHW9          | An optimist believes we live in the best of
>> all
>> PGP Key: 0x674627FF        | possible worlds.  A pessimist is sure of
>> it!
> Tell me if this is right.  So being really simplistic about it, say every password was "password" and there was no salt.  If I were the hacker, I guess "password" hash it, and compare to the information that was leaked.  All the hashes match and I'm done.  If all the passwords were not "password" but some were, those would match and I'm done with them.
>
> Again being simplistic, now, say all passwords are "password" and the salts are 0000 - 9999.  I realize that only allows for 10,000 entries in the user database.  So, to crack the 1st entry, I guess 0000password and hash it and check it.  Then I guess 0001password and check it.  And, I do this all the way up to 9999password if I have to.  At some point, which could be all the way at the end, I hit the match for the first entry in the database.  Then, I do the same thing for the second entry, then the third entry, and so on until I've tried to crack all 10,000 entries with the word "password".  And , in each case, I may have had to try 10,000 times to crack each one.  So, to crack the whole databases with the word "password" could have taken me 10,000 x 10,000 tries, which equals 100,000,000.  And, if the password is "aardvark", then I have to do the whole thing again.  So, the whole task blows up to an unimaginably large impossible task, even for a computer doing a trillion !
>  operations / second.  So, the salt multiplies the number of crack attempts required for each user account record by the number of permutations in the salt.  In my example, the size of the salt limited the number of possible user accounts.  Obviously, in the real world, they wouldn't let that happen.  Is that essentially it?

I think you are overestimating the number of attempts by 2. You should
average about 5000 tries per salted password. But the IMHO the idea is
correct, if you add a large random string, say 50 characters long, to
each password the number of tries needed to crack each password is much
larger thus a longer average computing time. At some point it the odds
of recovering a password in a reasonable period of time to use (say a 3
months) becomes vanishingly small.

With any protection scheme you face two issues, how long is the "key"
and how fast are the available computers. As computers get faster either
the "keys" must get longer or a new protection method must be developed.

The real problem with LinkedIn, et al is they did not make recovery of
passwords more difficult by salting or other well-known techniques that
would increase the difficulty of determining the hash. Essentially they
stored the passwords in a plain text file for someone who understood how
hashing methods worked and knew the methods weaknesses.
>
> Sincerely,
>
> Ron
>
>
> --
>
> Sent from my Android Acer A500 tablet with bluetooth keyboard and K-9 Mail.
> Please excuse my potential brevity.
>
> (To whom it may concern.  My email address has changed.  Replying to former
> messages prior to 03/31/12 with my personal address will go to the wrong
> address.  Please send all personal correspondence to the new address.)
>
> (PS - If you email me and don't get a quick response, you might want to
> call on the phone.  I get about 300 emails per day from alternate energy
> mailing lists and such.  I don't always see new email messages very quickly.)
>
> Ron Frazier
> 770-205-9422 (O)   Leave a message.
> linuxdude AT techstarship.com
>
>
> _______________________________________________
> Ale mailing list
> Ale at ale.org
> http://mail.ale.org/mailman/listinfo/ale
> See JOBS, ANNOUNCE and SCHOOLS lists at
> http://mail.ale.org/mailman/listinfo
>

-- 
Jay Lozier
jslozier at gmail.com