An attacker has to brute force the whole universe of human-friendly passwords. So 1000x the computation is a lot more painful for the attacker than for a legitimate user who only uses the operation occasionally (create/change password and login).

Additionally, salts protect against attacks that use pre-calculated tables.

I haven't read Colin's scrypt paper, so I'm not sure if its strategy differs.

Right, but if your password is an English word concatenated with a number, you might really be looking at the attacker getting it in the first 10,000 guesses, which isn't much if the password can be checked on your webapp box in less than half a second, (in that completely made up case, even if the attacker only has the same resources as you, the password would last an hour and a half) considering 1. the attacker probably has more compute resources dedicated to the cracking than you have dedicated to logging in, and 2. the attacker doesn't mind waiting all day for a login. (I mean, I'm assuming the attacker has other compromised hosts to use in the cracking effort.) I think it's a losing battle.

I'm not saying that slowing down the checking of a password has no value; Clearly it has much value. Without it, even a strong password would be brute forced quickly. I'm just saying, I am missing how it solves the problem of weak passwords.

The real problem here is that I know I can't remember a sufficient degree of entropy. Sure, there are all sorts of ways to fake it; take the first letter of every word in a sentence, but that's not exactly random, either. I know a guy who, for a pass phrase, would use a 24 line block of text from some project Gutenberg title. I doubt that was any more secure than 4 or 5 random characters.

Yeah, I don't think a KDF makes arbitrarily bad passwords OK. They just move the needle and thus increase the cost of the attack. In many cases, the derived key can be cached by the legitimate user, so you can throw a few seconds at it on the user's machine.

10000 * 1s = ~2 hours cpu time, but that's a terrible password -- common words plus 3 digits means 1000 * 10000. 26^6 * 1s = ~10 years CPU time -- a few thousand bucks on EC2 -- that's getting better for what is still a pretty weak password. In any case, straight MD5s are super-fast. At 1e5-1e6 MD5s/second or more on a modern CPU, paying the compute cost for a 1 cpu-second KDF can be several orders of magnitude stronger than MD5(password+salt).

Yeah. But really, I was hoping someone had come up with a way to make something like client certs usable. a six character completely random password (even if it's all lower-case without punctuation) is a damn sight better than your average password.

Can you tell me more about allowing the user to cache the derived key within the context of web applications? that would mitigate the limitation I was describing (where how slow you made the password check was limited by what delay a user would tolerate when logging in.)

I don't think this is really suitable for web applications. Javascript really sucks at crypto (due to the lack of suitable data types), and requiring Java wouldn't fly with too many people (Flash is sort of in-between, I guess?). There is a very large constant factor here, so and since the whole point of this key derivation stuff is to make an attacker work harder...

scrypt is like PBKDF2 but with careful analysis and a focus on using up lots of memory per-password in addition to CPU. Both seem fine to me.