[Cryptography] How secure are hashed passwords?

[Jerry Leichter]

On May 21, 2014, at 8:47 PM, John R. Levine <johnl at iecc.com> wrote:

> I see in the press that eBay had a large security breach, in which the
> bad guys stole a lot of personal information such as physical address
> and birth date, and the encrypted passwords.  So eBay wants everyone
> to change their passwords.  Huh?
> 
> Assuming a reasonably competent implementation of password hashing
> (which I realize is a leap of faith here), with a strong hash and a
> large enough salt to make rainbow tables impractical, how much can the
> bad guys recover from the hashes?
Forget rainbow tables; they're irrelevant for modern attacks.  Pure brute force rules the day, using specialized hardware based on multiple GPU's running highly optimized algorithms - and tons of statistical data on the passwords people actually use.  http://arstechnica.com/security/2012/08/passwords-under-assault/ will give you an idea of the state of the art ... almost two years ago.  (At the time, a single AMD Radeon HD7970 GPU could do 8.2 GigaHashes/second - I think MD5, but there's not much difference here among the different commonly-used hashes.  (Hashes like bcrypt and scrypt have been designed to make the problem harder, but they are not widely deployed.)

                                                        -- Jerry