CAPTCHA is Dead, Long Live PAPTCHA?

Slashdot today carries a link to a story claiming that the CAPTCHA algorithm for Hotmail (or Windows Live Hotmail or whatever it's called now) has been defeated by a spambot and the exploits have started. So that's Gmail, Yahoo Mail, and now Hotmail.

CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) is a great idea, but if it doesn't work, then it doesn't work.

CAPTCHAs were developed to tell humans apart from software. They're essentially a Turing Test across a very limited domain, and because of the limited domain, they're much easier to attack. In the case of a standard warped-text CAPTCHA, the attacker knows that the challenge will be an image with a certain number of letters and/or numbers, and that it will be warped in one or more ways. The software can be written with this in mind. Additionally, even if there is only a miniscule success rate, it's often worthwhile for a spammer, particularly if attempts can be automated and run several times a second.

So what's the solution?

Slashdot made a tongue-in-cheek reference to Kitten Auth, suggested in 2006. It may have been a playful suggestion, but I think they're on the right track. Kitten Auth basically presents the user with a number of pictures of cute fluffy animals, and tells the user to select all the kittens. The premise is the same as the text-based CAPTCHAs - easy for humans, hard for computers - but it doesn't use text, making OCR useless.

Something like Kitten Auth could work as long as there's no predictability. If the same images are repeatedly used, a brute force attack would work. If you needed to select three kittens out of nine pictures, all you need is one random success and bam, you have copies of three images that are kittens. Given enough time, the software could learn enough images to be viable as a solution.

Alternatively, if OCR can be trained to learn letters and numbers that are very warped and modified, then why not pictures of kittens? It's harder, sure, but if we mere mortals can tell a kitten apart from a possum, then why not a computer? These spammers and malware authors are pretty determined you know.

So what else?

Maybe the problem with CAPTCHAs is the "CA" part. Completely Automated. What about PAPTCHA? Partially Automated. Sure, it ruins the contrived acronym, but it might be more effective.

Arguably, Kitten Auth is already an PAPTCHA. The pictures of kittens can't really be completely automated unless there are 3D models of kittens rendered from different angles with different lighting each time... hmm... that's an idea... but I digress.

If Microsoft and Google and Yahoo were to put some effort into changing their "PTCHA" regularly, by real people, maybe there's a solution.

Here's how it could work:

Twenty people, armed with cameras, walk the streets for a few hours taking photos of random objects or scenery.
They get back to the office and upload the photos to today's collection.
They link each photo to some standard questions (e.g. "what is the main object in this photo?") and provide acceptable responses.
They provide additional specific questions for each photo (e.g. "How many white horses are there in the field?") and provide acceptable responses.
One or more other staff members look at the photo and each question for quality control. They can add more acceptable answers, remove them, or reject photos or questions outright.
Photos are retired after a time to prevent them being learned.

As a very rough estimate, I'd expect that a person would be able to add at least fifty photos with ten questions each every day. With 20 people, that equals 10,000 new PTCHAs every day - 50,000 per working week. Surely that'd be enough. Is 20 people too many? Even with five people you'd have 12,500 new challenges every week. If you expire the questions after a month, you'd still have an incredibly large number to choose from.

Current CAPTCHAs effectively have an infinite number of possibilities, however they're still in a narrow domain. By expanding the domain to include any question about any photo, there's no pattern to learn - no possible algorithm to solve the problem.

Is it foolproof? Definitely not. However, I'd suggest that implemented properly (and that means a lot of QA), it would be a lot harder to break than current CAPTCHA methods.

There could be a business in this you know... I'd be interested to know what you think!

Damo

Edit: I've been having a discussion with a friend of mine who has outlined exactly why 50,000 new challenges per week is not enough. In short, if x people are creating these challenges, then some fraction of x can be employed to decipher them (answering is quicker than asking). The answers get added to a massive database along with copies of the images, and there'll be enough solutions saved to give some malicious code a decent success rate. If the image and question match one in the database, then the answer will be there.

Repetition of challenges is therefore a significant problem. A challenge that presents an "image and question" that is repeated every 200,000 requests (4 weeks of 50,000 per week) is far too repetitive. If the malicious code runs one request every fifteen minutes on 1,000 nodes, you'd have seen every challenge in just over 2 days.

So to overcome this, here are some ideas:

Use existing CAPTCHA technology such as warping the question text and putting it directly on the photo in a semi-random place. You'd get no exact repeats. The obvious problem is that this may still allow a malicious program to recognise sections of the photo that haven't been altered. With every photo and answer saved, there's still a one in ten chance (given 10 questions per photo) of getting the question right. Very unacceptable.
Warp not only the text, but the image as well. Obviously it'd still need to be recognisable, so overlaying a random, semitransparent pattern or something might be all you could do. It might be enough to slow down matching of the image though.
Include a bevy of questions that bear no relation to the image. These could be added to any of the images. For example, you could have a picture of a field of horses which renders with the question, "How many legs are most people born with?"

So now I have a system where a modified image is rendered with an overlayed warped-text question which may or may not have anything to do with the image.

Of course all I'm really doing is adding complexity, but as long as it's complex enough to withstand attacks for the length of time it's used (one month in my example), it should work.

My other suggestion, the CG kittens, got more interest. In this case, there would be essentially no repeated images. You'd probably only need a handful of animal models with a few variables set at random to make it feasible. Perhaps fur colour, lighting, camera position, and some posture or face variables.