[lsc]

do you think a hashed password is going to last long against an attacker? considering how cheap computing resources are (and the common use of botnets, and the fact that most passwords are dictionary words) I treat password hashes as if they were cleartext passwords.

But I suppose that if you are using https, you get most of the advantages of digest anyhow.

[tptacek]

If the password is hashed well, with stretched SHA1/SHA256 or (better yet) bcrypt, then yes: breaking the hash would involve a significant advance in cryptography.

[lsc]

hm? I'm trying to say that once you have the hash, you can run a dictionary attack against it without any advances in anything. I can use whatever procedure the server uses to verify logins, and just try passwords. You can make the dictionary attack more expensive by using an expensive hash like bcrypt, but that's going to slow down your app, too. (http auth re-authenticates every page load.) so really, you can't make your hash calculation any slower than, say, 50ms without users complaining.

Lets say you can crack the average user account with 40,000 hits from a dictionary attack (I imagine most passwords fall much faster) if each lookup takes 50ms, 20 lookups a second, it'll take around 30 minutes of cpu time to crack each password. assuming a reasonable-sized botnet, that's not much.

[tptacek]

You're not thinking this through. In no well-designed web application is password checking in the 80/20 hotspot of performance. In fact, if it's within a light year of mattering to performance, you've done something horribly wrong.

The point of adaptive hashing is that doubling the cost of the hash on the serverside adds negligable overall cost, but doubling the cost of the hash on the attacker's side doubles their cost. This is not a complicated tradeoff.

[lsc]

hmm? http basic auth checks your password on every request. you can do auth other ways, (but you need to be very careful.) but that's how http basic auth works.

the attacker can check one word from her dictionary in the same amount of time it takes you to authenticate one user for one page.

if you make that check take longer than 50ms, it will start slowing down your webapp.

at 50ms, an attacker can check 40,000 words in around half an hour.

you can double that to 100ms, but at that point you are starting to slow down page loads, and it's still only taking the attacker an hour to run through that dictionary.

[decode]

On average, the attacker will have to search half of the hash space to find a given password. So, your 40,000 searches is way too small as long as you require more than 2 character passwords. If you assume lowercase + uppercase + numbers for the passwords, and require at least 6 characters, you get

(26 + 26 + 10) ^ 6 = 56,800,235,584 combinations

searching half of that would be about 28 billion combinations. At 50ms each, that would take 388,888 hours, or 44.36 years.

[lsc]

if passwords are randomly generated, I agree with you completely, and everything I've said is crazy talk.

But most passwords are not randomly generated. Most passwords are dictionary words, or two dictionary words. You don't need to search the hash space; you only need to search the password space, and if everyone uses the name of their dog, well, that's not a very large space.

http://www.schneier.com/blog/archives/2006/12/realworld_pass...

[tptacek]

Don't use basic auth, lsc.

[Edit] I regret even conceding this point. Even if you use basic auth, the tradeoff here is not complicated.

[lsc]

the bigger point is that there is a limit to how slow you can make the password checking process. Ok, so let us assume you securely authenticate once per session. How long can that authentication take? I suppose you can put up a little clock... make it take a second and we are talking 11 hours per password, which is starting to get significant... but my point is that the small search space provided by user chosen passwords means that if you make the hash function slow enough to stop an attacker, you are moving into time spaces that users will notice.