The end of CAPTCHA? - hardly

The NYT has an article predicting the end of CAPTCHAs, or rather their replacement with a new type of test.

I don't think we have seen the end of the CAPTCHA. Like passwords they are easy to implement and have a high ratio of perceived security to cost. Designers like to sprinkle them liberally onto their Web sites as 'magical anti-bot pixie-dust'.

The problem with CAPTCHAs and their replacements is that the problems chosen are hard for computers to solve because until recently there was no incentive to solve them. Back in 2000 there was nobody who was spending their time trying to OCR on text that had been deliberately obfuscated with lines, distortion, etc. Today there are plenty of folk in Eastern Europe and Russia who have become experts at it.

Asking folk to pick out all the cats from a mixture of cats and dogs may appear hard today, but wait a couple of weeks after deployment and see if it is still so hard.

And there is also the systems attack. Methinks that Microsoft do not have a very large catalog of photographs to show to users, maybe a thousand, maybe a hundred thousand. The attackers don't need to build a machine to sort the pictures out, they can have people do that for them. They can use the man-in-the-middle porn site attack or just pay folk to do it for them. All they need to do once the pictures are sorted is to undo whatever obfustication is in place to prevent simple matching of the photographs.

Bruce Schneier often remarks that anyone can design an encryption scheme that they cannot break themselves. In the area of CAPTCHAs I can't do that. I can break every scheme I have seen and I can break every scheme I can think of.

Update: Welcome TPM visitors. Following Josh's link it turns out that the database of pet pictures has two million entries. More significant though is the rate of addition - 10,000 a day. This is an order of magnitude higher than my original guess, but I don't think it invalidates the suggested lines of attack.

The hard part is cataloging the original database - ten man years worth of effort. That is certainly going to cost more than the $5,000 the Kiev gang would charge for breaking a text CAPTCHA. Unfortunately certain organized crime rings have repeatedly demonstrated that they have the necessary level of resources to simply pay people to break the problems by brute force.

Once the main catalog is sorted it is quite easy to keep up as it turns out that Asirra has a 'tell'. If you have 90% of the catalog archived and the images are selected randomly the chances are that you will only be presented with one unknown image per test. Since Asirra requires the subject to be 100% correct a cataloging bot can tell whether the unknown image was a dog or a cat by whether it passed the test or not. A simple way to fix this tell would be to weaken the match criteria so that 9 out of 10 correct answers was sufficient, but this opens up the door to other attacks.

The other weakness I see in the approach is asking image recognition experts to estimate the difficulty of differentiating pictures of cats from pictures of dogs. It isn't the right test. The hidden assumption here is that the best attack is going to solve the problem the way a human would. Thats not the way internet criminals think. Ants solve similar problems every day with 100,000 total neurons.

Update 2: it appears that the code as implemented, as opposed to the documentation allows one wrong answer out of 12. Turns out that it does not defeat the automatic cataloging attack described earlier as I assumed. In order to use the automatic cataloging trick the attacker would have to present ten correct tries, and one deliberately wrong try together with the unknown picture.