[Cryptography] How secure are hashed passwords?

[Krisztián Pintér]

John R. Levine (at Thursday, May 22, 2014, 2:47:25 AM):
> 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?


let's use this assumption, and see the numbers.

a website has a password hashing "budget". this budget can come from
two sources: user impatience and hardware cost. suppose the site has a
huge number of users, so the bottleneck will be the latter.

let's further suppose that they can afford computers up to the point
at which 100 users are authenticated per second per computer. it means
their password hashing budget is 10 computer-millisecond per user. to
go up to 20ms computer-millisecond per user, the would need to double
the hardware cost.

now suppose that the attacker can afford one million of those
computers. yeah, this is not a script kiddie, but it is good to be on
the safe side. that means they can try 100 million passwords per
second, 260 trillion passwords per month. this is over 40 bit. with
such a search space, you can cover most simple passwords, which is
majority of the users.

there is really no escape from choosing strong passwords. if your
password strength is around 60 bit, the above attack will fail. but
that is a lot. it is 6 random words or 12 random alphanumeric.