The Misadventures of Quinxy von Besiex truths, lies, and everything in between

A New Approach to CAPTCHA: Ask My Computer a Question, Not Me

Being able to tell a human from a computer is pretty important. While we don't yet need to worry about artificial intelligence run amok, experience has taught us that we do need to worry about the trouble humans can create when they can automate their mischief. These little tests computers give us, called CAPTCHAs (short for Completely Automated Public Turing test to tell Computers and Humans Apart), are used to prevent automated scripts from doing such things as creating millions of bogus Gmail accounts from which to spam us good e-citizens all to hell.  For years now the technique employed for CAPTCHA has been a set of distorted characters we humans are required to use our powerful brains to interpret and then type in.  We humans are still better at pattern recognition than mere computers and so even the dullest of us pass the test, most of the time.  For years CAPTCHAs asked these pointless questions and compared them with known pointless answers.  A new variant arrived,  reCAPTCHA, to at least marry these potentially good labors of man to potentially good works, allowing us to band together in transcribing difficult to read words found in old books.  A hundred years or so of the New York Times has been transcribed in just such a fashion.  And while that's all well and good and has been making the best of a bad situation, the truth remains that CAPTCHAs as thus far implemented are still awfully rotten things, wasting our precious little time on this big blue marble proving we are human, which is something that just shouldn't need to prove to anyone or anything.  A truly great CAPTCHA shouldn't need to ask us any question, it should just size us up as human beings and declare with authority, "By god, this is a human being sitting in front of me."  Or if it couldn't do that, couldn't detect something approximating our soul, it should at least employ some other solution to solve the same basic problem of gating access to a resource without needing anything from our person.

I imagined just such a solution in 1997, and surely some towering genius imagined it even earlier than that.  I'm surprised no one has developed it in the year since.  My schedule is so painfully busy I haven't bothered, that and my woeful disorganization and disinterest in the minutiae required to achieve its perfect implementation.  Still, I have the concept, and I am fully convinced of its probable efficacy.    And if I can't bother creating it at least I can bitch and moan that no one else has either.  And hope for that one day when someone will, because I think the ultimate solution must resemble the one I am here proposing.

First we must admit one thing, no CAPTCHA is perfect, and none make serious attempts to be.  CAPTCHAs are a balance between maximizing the thwarting of automated scripts while minimizing the annoyance of the humans who need to type in the often hard to interpret letters.  If you make the images too hard to read people will become so annoyed that they'll begin to avoid your website, and if you make them too easy the fake users on your site will exceed the real ones.  So a CAPTCHA solution need not be perfect, it simply must prevent severe abuses.  The key point in an example involving a site like Gmail is that if you limit the number of accounts created by an automated script, then the limits separately applied to each account will prevent the serious problems.  For example, an automated script today may be able to guesstimate enough reCAPTCHAs to create a few hundred fake Gmail accounts a day, but if each Gmail account is limited to only sending out a hundred emails a day, then this spammer won't be able to send enough spam to earn himself a steak dinner.

With that explanation of the real expectations of CAPTCHAs I can reveal my super top secret solution...

Instead of requiring a human to view, decipher, and type in a code, require that the user's computer do some fiendishly complicated math the solution it then passes silently to the website in question at the moment your humanness would otherwise be proved.  This CAPTCHA is obviously not living up to its name in proving  you are a human, but what it is doing is requiring you to prove that you have sufficient computing resources to expend on acquiring some resource you want.  To add further protection, the model would be further changed such that executing particular web transactions would also incur this penalizing CPU burden. These computational tokens wouldn't merely be required for creating accounts, they would also be required to download files, send emails, post comments, etc.  The actual math done behind the scenes by the formula I propose is beyond the scope of this document but it would be of the sort where the server delivers a JavaScript (or Java applet with JavaScript glue) with the formula and some input parameters embedded and at the end of some intense computation the solution requested is found and returned to the server which could instantly verify the solution (testing the solution for validity must not require recomputing the problem, it would instead merely involve applying the solution to see if it solved it).  The code in question would execute silently in the background as you accessed the website, ideally beginning its execution long before it was needed.  For example, the first time you land on Gmail.com the script could begin computing  the token.  As you changed pages it would halt and then restart the computation, making gradual progress.  By the time you completed the sign up form it would have the solution token computed and ready to use, without your needing to wait at all.  In the worst case scenario where you might go directly to the sign up page and fill it out with super speed, you might need to wait 10-15 seconds for the token to be generated and exchanged.  Continuing this example, once you've signed up for your account you would use Gmail as always but now, without your being aware of it, every time you send an email a similar token generation and exchange would take place. By demanding these significant chunks of computing resources from each user for each important transaction you are ensuring that nefarious persons who have limited resources would be unable to inflict significant damage.  As with any CAPTCHA system automation could bypass the system to a degree, but only a very limited degree, with very limited consequences.  With this sort of approach we could all be liberated from the traditional image-based CAPTCHA, never again wasting our precious time in the service of proving our very humanness.  We can finally defeat the bogus philosophy of Rene Descartes 2.0 and his, "I am, therefore I will type these characters."  We can be free to waste our life with reality TV, internet pr0n, and attend furry conventions.  But seriously, we should do this.

And now some additional notes and caveats I didn't feel like crafting elegantly into seamlessly arranged paragraphs above:

• Regarding the Formula...  I am no expert in the math required here, so I can only describe the features we'd need from such a formula.  I strongly suspect these sorts of formulas could be created, its features remind me of those used in cryptography and prime number computation (difficult computation, easy testing of the solution, difficult or impossible to shortcut).
• How hard should the math problem be?  I haven't computed how many CPU cycles should be required, and presumably it would vary depending on the resource you were trying to protect.  Important in the implementation would be that the computer and the browser feel responsive, despite the intense labor that is being required of it.  This responsiveness might be the bugbear in any implementation, particularly one that uses JavaScript exclusively.  Implementation would probably require the computation portion be done in Java with communication between it and the web page taking place via JavaScript.  and perhaps even Java would deliver an unpleasant experience, which is why I would argue that the real place for this solution is in the browser itself, via some standard.  Computers can quite pleasantly do intense work without negatively affecting user experience if the process doing that work is executing at a lower CPU priority, but such things cannot be done in JavaScript (except by poor simulation, adding pauses in script execution) and perhaps not with a Java applet (I don't recall, I suspect it can be done, but I just don't remember).
• And now for the possible fly in the ointment...  It cannot be denied that there are botnets which could be employed against just this sort of defensive strategy.  A botnet operator could potentially direct the activities of tens of thousands of computers toward the purpose of bypassing these protections, stealing chunks of CPU cycles from each computer for the proxy computation of a separate automation script.  I have a few ideas about how to mitigate this risk, but I hesitate to share those nascent ideas prematurely.  The risk of this sort of botnet attack isn't known, nor is how this threat would compare to the threat of a similar botnet using a similar attack against traditional CAPTCHA images using traditional OCR techniques.  The goal is to have this alternate approach be no worse than what currently exists and in fact potentially quite a bit better, and I think that's achievable.

^ Quinxy