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:
- If an OCR program can read your text, they still must compute a computationally expensive value.
- 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.
I just wanted to make the announcement, if anyone happened to be unaware. The reason for the holiday, if you haven't guessed already, is because sqrt(1225) = 35. Translating those numbers into calendar dates gives us the square root of Christmas 12/25 falling on 3/5.
It just so happens that there is another big nerd holiday in March, Pi Day (3/14). Why not connect these two dates with a week(ish) long nerd celebration? I hereby declare that:
