[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]

If passwords are two dictionary words, then even with the system dictionary, a single 50ms hash takes 889,251 hours to crack. 8 million if people put a single digit at the end of it. You won't win this argument.

[lsc]

adding two dictionary words and a number, yeah, that helps a lot. looks like you are right, and that if your users use 2 words and a number, and you use a hash that takes 50ms to calculate, you are probably OK.

but my point is that passwords are a lot less secure than they sound if you just add up the characters. And most hash functions take a whole lot less than 50ms of cpu time to calculate. Bcrypt does look pretty cool in it's ability to slow down brute force attacks. It does still require a minimum amount of entropy in the user passwords, though.

[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.