Is there a password hash function with a human component?

Question

Sort of Related: Is there a cryptographic hash function that can be performed with pencil and paper?

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:

1. Use the password/input to seed a random number generator
2. Generate a random problem
3. Have the human give the solution
4. 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.)

Answer 1

Answer: No.

Reason: Useless.

Explanation:

• Not necessarily perfectly reproducible as crowds of people may give different output. So you will end up introducing some degree of tolerance.
• Once introducing that degree of tolerance, pattern recognition algorithms will be able to automate that and possibly even achieve a higher accuracy than the humans.
• NSA will hire many cheap labour agents and manage to get them work for you and cause your hashes to be insecure. NSA is rich, they can hire many of such cheap labour. How can you ensure that the many humans that are solving hashes for you are actually honest people that are not NSA agents?

My opinion: you are trying to solve an existing problem (so the problem actually exists). It's just that your proposed solution is not going to solve the problem. Instead, I even think it will worsen the situation. You seem to be over estimating the uniqueness humans have. Humans are not that unpredictable. Some human-only problems are considered solved by pattern recognitions algorithms. I also think that humans are more predictable than PRNGs. So why not incorporate a seeded PRNG into your hashing function instead? Such seeded PRNGs are less predictable than humans aver all.