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

[Michael H. Warfield]

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!
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 482 bytes
Desc: This is a digitally signed message part
Url : http://mail.ale.org/pipermail/ale/attachments/20120608/35c8b314/attachment.bin