So PBKDF2 or scrypt just slows down the process of checking a users password against a hash, right? That does make sense in that it does slow down an attacker (and combined with a strong user password it seems like it could be secure) but it doesn't solve the essential problem that humans are not good at remembering random things, and there is a limit to how slow your 'check password' function can be in production. your attacker can almost always be assumed to have more computing resources than you do.
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.
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.
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).
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.)