L'Ombre de l'Olivier

The Shadow of the Olive Tree

being the maunderings of an Englishman on the Côte d'Azur

26 February 2008 Blog Home : February 2008 : Permalink

The Slow Death of Captcha

For those who don't know, a Captcha is one of those obfuscated words that are used to stop computers signing up or spamming things. Captchas are remarkably successful in stopping machines because decoding them, something that humans find very easy, is not so simple for machines. Unfortunately it is possible that the captcha may be no more.

The register has an article about spammers cracking Google's Captcha linking to this websense article with more detail than you could possibly want. However in summary, as with Yahoo and MSN captcha cracking, what we have is a system where Pwn3d computers fill in the user details and when they get to the Captcha text send the request back to a master server or two somewhere. Ths master server(s) then makes the attempt to crack the code, something that they succeed in about 20% of the time, and send the response back to the 'bot which then fills in the field and hopefully gets a gmail account.

If you read the websense article it looks like at least some of the captcha decoding is being done by paying humans to respond. So in other words captchas are working sufficiently well that it becomes worthwhile paying people to break the barriers. This is kind of a good thing because it indicates that the captcha technique really is mostly uncrackable. On the other hand the fact that it is worthwhile for people to be paid to crack captchas indicates that significant value is available once you have something "free" like a gmail account.

So if captchas are dying what are the alternatives?

Harder captchas are not the solution. The problem being that we need to find a way to differentiate between "good" humans and "bad" Pwn3d bots with "bad" humans answering the questions as opposed to merely differentiating between "good" humans and "bad" Pwn3d bots.

One way that might help is a two-way dialog with fairly strict response times. A possible way to do this would be a game where the person signing up has to (say) shoot down 5 space invaders in 10 seconds. Once the game is over the game sends the score (encrypted in some manner) back to the authentication server along with some other information. If the score is good enough you get to pass the test. The trick here is that the human has a time limit which limits the ability of an Pwn3d computer to call back to base and get a reply. Another advantage is that one can create almost unlimited nearly identical java/flash whatever applets that can be downloaded but which perform sufficiently differently that you can't simply fake the return. You could even create a KittenAuth applet as one of the alternatives....

Other possibilities are to enter things like post code and street address (and possibly cross check at least vaguely with IP address) and be asked for something that would be hard to find out quickly unless one were actually there. With this sort of thing you can limit the number of people who can attmept to sign up for something from a particular address and validate that the address exists. This would work really well in the UK where post codes get you down to about a dozen buildings usually but might also work for other places with a bit of care. For example asking where the nearest post office is. Or some other notable building (church, shop, bank, pub). Or...

And of course you could do simple things like addition, word games that you struggle with if English is not your native language and so on. Even ask trivia questions. All of these would be predicated on the idea that the computer can't figure out the answer and the human will not be of the right culture to get it right quick enough.

In fact the key here would probably be to ask the human which sort of test they want to do so that they have plenty of options. All this would be fairly easy to code I think, at least the simpler versions would be, and I'm fairly sure that you could make the applet non-reverse-engineerable in real time. No doubt even so the bad guys would have ways to get around some of these but by changing the applets you would make it hard for them to keep up, just the same way that malware writers mutate their product to make it hard for virus detectors to keep up.