Nowadays, it is hard to find a popular Web site with a registration form that is not protected by an automated human proof test which displays a sequence of characters in an image, and requests the user to enter the sequence into an input field. This security mechanism is based on the Turing Test—one of the oldest concepts in Artificial Intelligence—and it is most often called Completely Automated Public Turing test to tell Computers and Humans Apart (CAPTCHA). This kind of test has been conceived to prevent the automated access to an important Web resource, for example, a Web mail service or a Social Network. There are currently hundreds of these tests, which are served millions of times a day, thus involving a huge amount of human work. On the other side, a number of these tests have been broken, that is, automated programs designed by researchers, hackers, and spammers have been able to automatically serve the correct answer. In this chapter, we present the history and the concept of CAPTCHAs, along with their applications and a wide review of their instantiations. We also discuss their evaluation, both from the user and the security perspectives, including usability, attacks, and countermeasures. We expect this chapter provides to the reader a good overview of this interesting field. CES IN COMPUTERS, VOL. 83 109 Copyright © 2011 Elsevier Inc. 65-2458/DOI: 10.1016/B978-0-12-385510-7.00003-5 All rights reserved. 110 J.M. GOMEZ HIDALGO AND G. ALVAREZ MARAÑON 1. I ntroduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 1 .1. T he Turing Test and the Origin of CAPTCHAs . . . . . . . . . . . . . . . 111 2. M otivation and Applications . . . . . . . . . . . . . . . . . . . . . . . . 116 2 .1. G eneral Description of CAPTCHAs . . . . . . . . . . . . . . . . . . . . . 116 2 .2. D esirable Properties of CAPTCHAs . . . . . . . . . . . . . . . . . . . . . 117 2 .3. I m plementation and Deployment . . . . . . . . . . . . . . . . . . . . . . 119 2 .4. A pplications and the Rise of the Robots . . . . . . . . . . . . . . . . . . . 121 3. T ypes of CAPTCHAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 3 .1. O CR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 3 .2. I m age . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 3 .3. A udio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 3 .4. C ognitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 4. E valuation of CAPTCHAs . . . . . . . . . . . . . . . . . . . . . . . . . 146 4 .1. E fficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 4 .2. A ccessibility Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 4 .3. P ractical Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 5. S ecurity and Attacks on CAPTCHAs . . . . . . . . . . . . . . . . . . . . 156 5 .1. A ttacks on CAPTCHAs . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 5 .2. S ecurity Requirements on CAPTCHAs . . . . . . . . . . . . . . . . . . . 169 6. A lternatives to CAPTCHAs . . . . . . . . . . . . . . . . . . . . . . . . . 171 7. C onclusions and Future Trends . . . . . . . . . . . . . . . . . . . . . . . 173 R eferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173