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

[Tim Watts]

Makes sense now.  Thanks!

On Fri, 2012-06-08 at 09:58 -0400, Michael H. Warfield 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
> _______________________________________________
> 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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 490 bytes
Desc: This is a digitally signed message part
Url : http://mail.ale.org/pipermail/ale/attachments/20120608/26f1dfe9/attachment.bin