A plan for CAPTCHAs

I had the idea (I'm uncertain if it is original [pdf]) of mixing two distinct elements to make a better CAPTCHA. The problem is that there are essentially two ways to solve a CAPTCHA. The first is by designing some kind of image recognition system, this is an OCR problem and there are indications that nearly every major CAPTCHA has been broken. The other main avenue of attack seems to come down to paying people to crack them. This is a much tougher nut to crack because CAPTCHAs are not designed to prevent humans from cracking them; in some sense, this attack isn't a break of the system at all, but a design goal of CAPTCHAs. But much like the mathematician in that old joke, this definition of acceptable wouldn't sit well with some. The solution is to pose a question in such a way that is very hard for a computer to perceive but at the same time hard for a person to solve by herself. As an example, imagine a cryptographically hard problem posed in a way that a computer couldn't readily interpret, and a person would find difficult (or impossible) to solve by hand. This could be the source code for a simple discrete logarithm solver. The code would be obscured in the normal way that a CAPTCHA is (wavy text, visual noise, etc.) The user is instructed to type the code into a text box (where a built-in solver, client-side, can operate on it), and then use the result for entry into the protected resource. It would be easy to tune the toughness of the discrete log problem (randomly chosen of course) to generate any penalty you want. This penalty would cost an attacker any amount of CPU time that the challenger desires. By mixing a character-recognition task (that a human is good at) with a number-crunching task (which a computer is good at, but can be made arbitrarily CPU-intensive and thus slow) you protect from both types of attacks:

1. If an OCR program can read your text, they still must compute a computationally expensive value.
2. If humans are being used to circumvent the OCR task, a computer must be used to compute the expensive task as well, still incurring most of the penalty (by tweaking the exact type and hardness of the one-way function, this part can come to dominate the time needed for a successful break).

Some ideas on how to make the computation time more palatable for a legitimate user:

• Make this be the first question on a form that the user has to fill out.
• Grant the user provisional access to the site while the computation proceeds in the background.