One problem with hashing passwords is that the attacker has more of everything it seems. More speed, more memory, more time, newer algorithms, etc. It's a constant race to keep up. We have the advantage of having to try less passwords, but even that is only somewhat enough.
What if we threw a human into the mix? Currently, solving 1000 captchas, for example, is \$2. If we had a task as complex as a captcha incorporated into a hash function, and the attacker needed a billion guesses, that would be \$2,000,000 to crack one password.
Of course, incorporating captcha into a hash function I'm pretty sure would be impossible. But there are other tasks that humans seem better that are purely computational. For example, see foldit.
The idea is that when the user enters their password, at a certain step in the hash function, there would be a problem that a human can solve much more efficiently, and the human does it (it can, for example, be presented as a game). It would probably be for the more security conscious, depending how "fun" the hash function is to compute.
Is there such a thing? Is there a hash function such that one of the steps is much more efficient for a human to compute, while still being cryptographically secure?
Note: As for why captchas probably wouldn't work is this, there are only two approaches I can imagine, neither of which works:
- The algorithm produces an image for the human to solve (based on the input and other parts of the algorithm). The human solves it, and the algorithm factors that into the hash. The problem is that, unless it used some direct method, to generate a captcha it would need to generate a random word, and then create a distorted image of that word. An attacker can simply edit out the "create a distorted image" step from the algorithm, and no human is necessary. (Perhaps cryptographic obfuscation could be used to prevent removing the distortion part of the algorithm, but that technology is practical yet.)
- Same as above, but to generate the captcha, and has a huge base of images. Keep in mind that it simply needs to be a captcha, the algorithm doesn't need to know what word goes with each captcha (that's what the humans for). The problem is that A) you would need an infeasible number of images to make it secure and B) whoever is generating all these captchas may make them in such a way that they know what how to solve them.
Also, computers are somewhat good at solving captchas.
Okay, here's what I think we need:
- There must be a very large number of problems (on the same order as the number of passwords/inputs).
- A computer must be able to efficiently generate a random problem without knowing the solution.
- A human must be able to solve the problem a couple of orders of magnitude better than a computer.
- It should be hard for the computer to guess the answer as well. This means the space of possible solutions needs to be large.
- There should be a unique solution.
- The computer should be able to check if something is a solution
- Bonus: Being fun
With these, what we do is:
- Use the password/input to seed a random number generator
- Generate a random problem
- Have the human give the solution
- Now process that into the final hash
Steps #1 and/or #4 will involve computer hashing algorithms. (It doesn't need to exactly follow the above steps; I'm just trying to reduce it to a simpler problem.)