Friday, November 13, 2009

Only humans allowed

Computing: Can online puzzles that force internet users to prove that they really are human be kept secure from attackers?

ON THE internet, goes the old joke, nobody knows you’re a dog. This is untrue, of course. There are many situations where internet users are required to prove that they are human—not because they might be dogs, but because they might be nefarious pieces of software trying to gain access to things. That is why, when you try to post a message on a blog, sign up with a new website or make a purchase online, you will often be asked to examine an image of mangled text and type the letters into a box. Because humans are much better at pattern recognition than software, these online puzzles—called CAPTCHAs—can help prevent spammers from using software to automate the creation of large numbers of bogus e-mail accounts, for example.

Unlike a user login, which proves a specific identity, CAPTCHAs merely show that “there’s really a human on the other end”, says Luis von Ahn, a computer scientist at Carnegie Mellon University and one of the people responsible for the ubiquity of these puzzles. Together with Manuel Blum, Nicholas J. Hopper and John Langford, Dr von Ahn coined the term CAPTCHA (which stands for “completely automated public Turing test to tell computers and humans apart”) in a paper published in 2000.

But how secure are CAPTCHAs? Spammers stepped up their efforts to automate the solving of CAPTCHAs last year, and in recent months a series of cracks have prompted both Microsoft and Google to tweak the CAPTCHA systems that protect their web-based mail services. “We modify our CAPTCHAs when we detect new abuse trends,” says Macduff Hughes, engineering director at Google. Jeff Yan, a computer scientist at Newcastle University, is one of many researchers interested in cracking CAPTCHAs. Since the bad guys are already doing it, he told a spam-fighting conference in Amsterdam in June, the good guys should do it too, in order to develop more secure designs.

That CAPTCHAs work at all illuminates a failing in artificial-intelligence research, says Henry Baird, a computer scientist at Lehigh University in Pennsylvania and an expert in the design of text-recognition systems. Reading mangled text is an everyday skill for most people, yet machines still find it difficult.

The human ability to recognise text as it becomes more and more distorted is remarkably resilient, says Gordon Legge at the University of Minnesota. He is a researcher in the field of psychophysics—the study of the perception of stimuli. But there is a limit. Just try reading small text in poor light, or flicking through an early issue of Wired. “You hit a point quite close to your acuity limit and suddenly your performance crashes,” says Dr Legge. This means designers of CAPTCHAs cannot simply increase the amount of distortion to foil attackers. Instead they must mangle text in new ways when attackers figure out how to cope with existing distortions. Mr Hughes, along with many others in the field, thinks the lifespan of text-based CAPTCHAs is limited. Dr von Ahn thinks it will be possible for software to break text CAPTCHAs most of the time within five years. A new way to verify that internet users are indeed human will then be needed. But if CAPTCHAs are broken it might not be a bad thing, because it would signal a breakthrough in machine vision that would, for example, make automated book-scanners far more accurate.



CAPTCHA me if you can
Looking at things the other way around, a CAPTCHA system based on words that machines cannot read ought to be uncrackable. And that does indeed seem to be the case for ReCAPTCHA, a system launched by Dr von Ahn and his colleagues two years ago. It derives its source materials from the scanning in of old books and newspapers, many of them from the 19th century. The scanners regularly encounter difficult words (those for which two different character-recognition algorithms produce different transliterations). Such words are used to generate a CAPTCHA by combining them with a known word, skewing the image and adding extra lines to make the words harder to read. The image is then presented as a CAPTCHA in the usual way.

If the known word is entered correctly, the unknown word is also assumed to have been typed in correctly, and access is granted. Each unknown word is presented as a CAPTCHA several times, to different users, to ensure that it has been read correctly. As a result, people solving CAPTCHA puzzles help with the digitisation of books and newspapers.

Even better, the system has proved to be far better at resisting attacks than other types of CAPTCHA. “ReCAPTCHA is virtually immune by design, since it selects words that have resisted the best textrecognition algorithms available,” says John Douceur, a member of a team at Microsoft that has built a CAPTCHA-like system called Asirra. The ReCAPTCHA team has a member whose sole job is to break the system, says Dr von Ahn, and so far he has been unsuccessful. Whenever the in-house attacker appears to be making progress, the team responds by adding new distortions to the puzzles.

Even so, researchers are already looking beyond text-based CAPTCHAs. Dr von Ahn’s team has devised two image-based schemes, called SQUIGL-PIX and ESP-PIX, which rely on the human ability to recognize particular elements of images. Microsoft’s Asirra system presents users with images of several dogs and cats and asks them to identify just the dogs or cats. Google has a scheme in which the user must rotate an image of an object (a teapot, say) to make it the right way up. This is easy for a human, but not for a computer.

The biggest flaw with all CAPTCHA systems is that they are, by definition, susceptible to attack by humans who are paid to solve them. Teams of people based in developing countries can be hired online for $3 per 1,000 CAPTCHAs solved. Several forums exist both to offer such services and parcel out jobs. But not all attackers are willing to pay even this small sum; whether it is worth doing so depends on how much revenue their activities bring in. “If the benefit a spammer is getting from obtaining an e-mail account is less than $3 per 1,000, then CAPTCHA is doing a perfect job,” says Dr von Ahn.

Source of Information : The Economist 2009-09-05

No comments: