Thoughts on creating unscalable conditions to brute force even small passwords?

Question

I stumbled upon something called "scrypt" which claims to add fixed time/space complexity requirements into password-based key derivation.

Quoting from their page:

A simple password-based encryption utility is available as a demonstration of the scrypt key derivation function. On modern hardware and with default parameters, the cost of cracking the password on a file encrypted by scrypt enc is approximately 100 billion times more than the cost of cracking the same password on a file encrypted by openssl enc; this means that a five-character password using scrypt is stronger than a ten-character password using openssl [emphasis mine].

I don't think anyone disputes that having fixed time/space complexity requirements can hinder breaking passwords. However, I've not seen any peer-reviewed work done with it in crypto or infosec circles, so I'm not convinced in its implementation. (I mean, you just can't take current methods and layer something like this over it, so they must be implementing their own algorithm.)

Can anyone shed light on scrypt or any, perhaps more well-known time/space complexity password-based key derivation systems in use?

Answer 1

I won't mark this a duplicate (in fact, I'll kick you a +1), but I will primarily answer by pointing to Do any security experts recommend bcrypt for password storage?

The accepted answer there is from our resident cryptographer. The concept itself, mentioned in another answer, is key stretching. For that, there are RFCs, NIST-suggested algorithms, and papers published as references on the Wikipedia page as far back as 1978.

Reading up on those materials should give you a good understanding. See also our sister site crypto.stackexchange.com where algorithm internals are discussed.