This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (January 2011)

Early CAPTCHAs such as these, generated by the EZ-Gimpy program, were used on Yahoo!. However technology was developed to read this type of CAPTCHA^[1]

A modern CAPTCHA, rather than attempting to create a distorted background and high levels of warping on the text, might focus on making segmentation difficult by adding an angled line

Another way to make segmentation difficult is to crowd symbols together, as in Yahoo's current CAPTCHA format.

A CAPTCHA ( /ˈkæp.tʃə/) is a type of challenge-response test used in computing as an attempt to ensure that the response is generated by a person. The process usually involves a computer asking a user to complete a simple test which the computer is able to grade. These tests are designed to be easy for a computer to generate, but difficult for a computer to solve, so that if a correct solution is received, it can be presumed to have been entered by a human. A common type of CAPTCHA requires the user to type letters or digits from a distorted image that appears on the screen, and such tests are commonly used to prevent unwanted internet bots from accessing websites.

The term "CAPTCHA" was coined in 2000 by Luis von Ahn, Manuel Blum, Nicholas J. Hopper, and John Langford (all of Carnegie Mellon University). It is an acronym based on the word "capture" and standing for "Completely Automated Public Turing test to tell Computers and Humans Apart". Carnegie Mellon University attempted to trademark the term,^[2] but the trademark application was abandoned on 21 April 2008.^[3]

A CAPTCHA is sometimes described as a reverse Turing test, because it is administered by a machine and targeted at a human, in contrast to the standard Turing test that is typically administered by a human and targeted at a machine.

Applications[link]

CAPTCHAs are used in attempts to prevent automated software from performing actions which degrade the quality of service of a given system, whether due to abuse or resource expenditure. CAPTCHAs can be deployed to protect systems vulnerable to e-mail spam, such as the webmail services of Gmail, Hotmail, and Yahoo! Mail.

Most interactive sites today are run by databases and become quickly clogged and sluggish when a database table exceeds capabilities the operating server can handle^[4]. A website's Google Page Rank can also be reduced by excessive commercial links created by automated posting^[5].

CAPTCHAs are also used to minimize automated posting to blogs, forums and wikis, whether as a result of commercial promotion, or harassment and vandalism. CAPTCHAs also serve an important function in rate limiting. Automated usage of a service might be desirable until such usage is done to excess and to the detriment of human users. In such cases, administrators can use CAPTCHA to enforce automated usage policies based on given thresholds. The article rating systems used by many news web sites are another example of an online facility vulnerable to manipulation by automated software.^[6]

Accessibility[link]

Because CAPTCHAs rely on visual perception, users unable to view a CAPTCHA due to a disability will be unable to perform the task protected by a CAPTCHA. Therefore, sites implementing CAPTCHAs may provide an audio version of the CAPTCHA in addition to the visual method. The official CAPTCHA site recommends providing an audio CAPTCHA for accessibility reasons, but it is still not usable for deafblind people or for users of some text-based web browsers.

Attempts at more accessible CAPTCHAs[link]

Even audio and visual CAPTCHAs will require manual intervention for some users, such as those who have disabilities. There have been various attempts at creating more accessible CAPTCHAs, including the use of JavaScript, mathematical questions ("how much is 1+1") and common knowledge questions ("what color is the sky on a clear day"). However, these approaches may worsen accessibility for people with intellectual and developmental disabilities, for instance dyscalculia. Some CAPTCHAs of this kind do not meet the criteria for a successful CAPTCHA because they are not automatically generated or do not present a new problem or test for each attack.

One approach to text-based CAPTCHAs is to create a central "anti-bot server", used by many websites, which selects for each call one puzzle, randomly, from a very large set of many different automatically-generated puzzles, of many different kinds. Such a solution can be made usable for blind and visually impaired people who otherwise find prevalent image-based CAPTCHAs to be insurmountable obstacles to completing web forms.

Circumvention[link]

There are several approaches available to defeating CAPTCHAs:

• exploiting bugs in the implementation that allow the attacker to completely bypass the CAPTCHA,
• improving character recognition software, or
• using cheap human labor to process the tests (see below).

Insecure implementation[link]

Like any security system, design flaws in a system implementation can prevent the theoretical security from being realized. Many CAPTCHA implementations, especially those which have not been designed and reviewed by experts in the fields of security, are prone to common attacks.

Some CAPTCHA protection systems can be bypassed without using OCR simply by re-using the session ID of a known test image. A correctly designed CAPTCHA does not allow multiple solution attempts at the same test, which would allow unlimited reuse of a correct solution, or a second guess after an incorrect OCR attempt.^[7] Other CAPTCHA implementations use a hash (such as an MD5 hash) of the solution as a key passed to the client to validate the answer. Often the answers are drawn from a small enough range that this hash could be cracked.^[8] Further, the hash could assist an OCR based attempt. A more secure scheme would use an HMAC. Another example is directly provide answer in the code such as showing four pictures to let user pickup the correct one, a spam bot can always guess first picture to gain 25% success rate in this case. Finally, some implementations use only a small fixed pool of CAPTCHA images. Eventually, when enough image solutions have been collected by an attacker over a period of time, the test can be broken by simply looking up solutions in a table, based on a hash of the challenge image.

Computer character recognition[link]

A number of research projects have attempted (often successfully) to beat visual CAPTCHAs by creating programs that contain the following functionality:

1. Pre-processing: Removal of background clutter and noise.
2. Segmentation: Splitting the image into regions which each contain a single character.
3. Classification: Identifying the character in each region.

Steps 1 and 3 are easy tasks for computers.^[9] The only step where humans still outperform computers is segmentation. If the background clutter consists of shapes similar to letter shapes, and the letters are connected by this clutter, the segmentation becomes nearly impossible with current software. Hence, an effective CAPTCHA should focus on the segmentation.

Several research projects have broken real world CAPTCHAs, including one of Yahoo's early CAPTCHAs called "EZ-Gimpy",^[1] the CAPTCHAs used by popular sites such as PayPal,^[10] LiveJournal, phpBB, the e-banking CAPTCHAs used by a lot of financial institutions,^[11] and CAPTCHAs used by other services.^[12][13][14] In January 2008 Network Security Research released their program for automated Yahoo! CAPTCHA recognition.^[15] Windows Live Hotmail and Gmail, the other two major free email providers, were cracked shortly after.^[16][17]

In February 2008 it was reported that spammers had achieved a success rate of 30% to 35%, using a bot, in responding to CAPTCHAs for Microsoft's Live Mail service^[18] and a success rate of 20% against Google's Gmail CAPTCHA.^[19] A Newcastle University research team has defeated the segmentation part of Microsoft's CAPTCHA with a 90% success rate, and reported that this could lead to a complete crack with a greater than 60% rate.^[20]

Human solvers[link]

CAPTCHA is vulnerable to a relay attack that uses humans to solve the puzzles. One approach involves relaying the puzzles to a group of human operators who can solve CAPTCHAs. In this scheme, a computer fills out a form and when it reaches a CAPTCHA, it gives the CAPTCHA to the human operator to solve.

Spammers pay about $0.80 to $1.20 for each 1,000 solved CAPTCHAs to companies employing human solvers in Bangladesh, China, India, and many other developing nations.^[21] Other sources cite a price tag of as low as $0.50 for each 1,000 solved.^[22]

Another approach involves copying the CAPTCHA images and using them as CAPTCHAs for a high-traffic site owned by the attacker. With enough traffic, the attacker can get a solution to the CAPTCHA puzzle in time to relay it back to the target site.^[23] In October 2007, a piece of malware appeared in the wild which enticed users to solve CAPTCHAs in order to see progressively further into a series of striptease images.^[24][25] A more recent view is that this is unlikely to work due to unavailability of high-traffic sites and competition by similar sites.^[26]

These methods have been used by spammers to set up thousands of accounts on free email services such as Gmail and Yahoo!.^[27] Since Gmail and Yahoo! are unlikely to be blacklisted by anti-spam systems, spam sent through these compromised accounts is less likely to be blocked.

Legal concerns[link]

The circumvention of CAPTCHAs may violate the anti-circumvention clause of the Digital Millennium Copyright Act (DMCA) in the United States. In 2007, Ticketmaster sued software maker RMG Technologies^[28] for its product which circumvented the ticket seller's CAPTCHAs on the basis that it violated the anti-circumvention clause of the DMCA. In October 2007, an injunction was issued stating that Ticketmaster would likely succeed in making its case.^[29] In June 2008, Ticketmaster filed for default judgment against RMG. The Court granted Ticketmaster the default and entered an $18.2M judgment in favor of Ticketmaster.

In 2010, encouraged by Ticketmaster, the US District Attorney in Newark, New Jersey won a grand jury indictment against Wiseguy Tickets, Inc. for purchasing tickets in bulk by circumventing CAPTCHA mechanisms.^[30] Among its 43 findings, the grand jury found Wiseguy Tickets Inc defeated online ticket vendors' security mechanisms CAPTCHA."^[31]

Interaction with images as an alternative to texting (text typing)[link]

Some researchers promote interaction with images as a possible alternative for texting CAPTCHAs. Computer-based recognition algorithms require the extraction of color, texture, shape, or special point features, which cannot be correctly extracted after the designed distortions. However, humans can still recognize the original concept depicted in the images even with these distortions.

Image-Identification CAPTCHA. Source: www.picatcha.com

A recent example of interacting with images CAPTCHA is to present the website visitor with a grid of random pictures and instruct the visitor to click on specific pictures to verify that they are not a bot (such as “Click on the pictures of the airplane, the boat and the clock”).

Image interaction CAPTCHAs face many potential problems which have not been fully studied. It is difficult for a small site to acquire a large dictionary of images to which an attacker does not have access and without a means of automatically acquiring new labelled images, an image-based challenge does not usually meet the definition of a CAPTCHA. KittenAuth, by default, had only 42 images in its database.^[32] Microsoft's "Asirra," which it is providing as a free web service, attempts to address this by means of Microsoft Research's partnership with Petfinder.com, which has provided it with more than three million images of cats and dogs, classified by people at thousands of US animal shelters.^[33] Researchers claim to have written a program that can break the Microsoft Asirra CAPTCHA.^[34] Extending the number of categories (more than just cats & dogs) and randomizing the number of correct images in a grid increases the security of the system. The IMAGINATION CAPTCHA, however, uses a sequence of randomized distortions on the original images to create the CAPTCHA images. Their original images can be made public without risk of image-retrieval or image-annotation based attacks.

Human solvers are a potential weakness for strategies such as Asirra. If the database of cat and dog photos can be downloaded, paying workers $0.01 to classify each photo as of either a dog or a cat means that almost the entire database of photos can be deciphered for $30,000. Photos that are subsequently added to the Asirra database are then a relatively small data set that can be classified as they first appear. Causing minor changes to images each time they appear will not prevent a computer from recognizing a repeated image as there are robust image comparator functions (e.g., image hashes, color histograms) that are insensitive to many simple image distortions. Warping an image sufficiently to fool a computer will likely also be troublesome to a human.^[35]

Researchers at Google used image orientation and collaborative filtering as a CAPTCHA.^[36] Generally speaking, people know what "up" is but computers have a difficult time for a broad range of images. Images were pre-screened to be determined to be difficult to detect up (e.g. no skies, no faces, no text). Images were also collaboratively filtered by showing a "candidate" image along with good images for the person to rotate. If there was a large variance in answers for the candidate image, it was deemed too hard for people as well and discarded.

Many users^[who?] of the phpBB forum software (which has suffered greatly from spam) have implemented an open source image recognition CAPTCHA system in the form of an addon called KittenAuth^[37] which in its default form presents a question requiring the user to select a stated type of animal from an array of thumbnail images of assorted animals. The images (and the challenge questions) can be customized, for example to present questions and images which would be easily answered by the forum's target userbase. Furthermore, for a time, RapidShare free users had to get past a CAPTCHA where they had to enter letters attached only to a cat, while others were attached to dogs.^[38] This was later removed because (legitimate) users had trouble entering the correct letters.

See also[link]

• Image spam, where spammers exploit the inability of computers to read text in images to avoid junkmail filtering
• One-way function
• reCAPTCHA
• Web scraping

References[link]

External links[link]

Wikimedia Commons has media related to: Captcha

• The Wiktionary entry for captcha

Luis von Ahn
Born	1979 (age 32–33)[citation needed] Guatemala City, Guatemala
Residence	United States
Institutions	Carnegie Mellon University
Alma mater	Carnegie Mellon University Duke University
Doctoral advisor	Manuel Blum
Known for	CAPTCHA, reCAPTCHA, crowdsourcing pioneer
Notable awards	MacArthur Fellowship (2006), TR35 (2007)[1]

Dr. Luis von Ahn (born in 1979 in Guatemala City, Guatemala) is an entrepreneur and an associate professor in the Computer Science Department at Carnegie Mellon University.^[2] He is known as one of the pioneers of the idea of crowdsourcing. He is the founder of the company reCAPTCHA, which was sold to Google in 2009.^[3] As a professor, his research includes CAPTCHAs and human computation,^[4] and has earned him international recognition and numerous honors. He was awarded a MacArthur Fellowship (a.k.a., the "genius grant") in 2006,^[5][6] the David and Lucile Packard Foundation Fellowship in 2009, a Sloan Fellowship in 2009, and a Microsoft New Faculty Fellowship in 2007. He has also been named one of the 50 Best Brains in Science by Discover Magazine, and has made it to many recognition lists that include Popular Science Magazine's Brilliant 10, Silicon.com's 50 Most Influential People in Technology, Technology Review's TR35: Young Innovators Under 35, and FastCompany's 100 Most Innovative People in Business.

Siglo Veintiuno, a leading newspaper in Guatemala, chose him as the person of the year in 2009. In 2011, Foreign Policy Magazine in Spanish named him the most influential intellectual of Latin America and Spain.^[7]

Biography[link]

Von Ahn grew up in Guatemala City. He attended the American School of Guatemala and graduated from it in 1996. He received a B.S. in mathematics (summa cum laude) from Duke University in 2000. He obtained a Ph.D. from Carnegie Mellon University in 2005 under the supervision of professor Manuel Blum, who is well known for advising some of the most prominent researchers in the field of computer science. In 2011, he was awarded the A. Nico Habermann development chair in computer science,^[8] which is awarded every three years to a junior faculty member of unusual promise in the School of Computer Science.

Work[link]

Von Ahn's early research^[9] was in the field of cryptography. With Nicholas J. Hopper and John Langford, he was the first to provide rigorous definitions of steganography and to prove that private-key steganography is possible.

In 2000, he did early pioneering work with Manuel Blum on CAPTCHAs,^[10] computer-generated tests that humans are routinely able to pass but that computers have not yet mastered.^[11] These devices are used by web sites to prevent automated programs, or bots, from perpetrating large-scale abuse, such as automatically registering for large numbers of accounts or purchasing huge number of tickets for resale by scalpers. CAPTCHAs brought von Ahn his first widespread fame among the general public due to its coverage in The New York Times, USA Today, Discovery Channel, NOVA scienceNOW, and other mainstream outlets.

Von Ahn's Ph.D. thesis, completed in 2005, was the first publication to use the term "human computation" that he had coined for methods that combine human brainpower with computers to solve problems that neither could solve alone. Von Ahn's Ph.D. thesis is also the first work on Games With A Purpose, or GWAPs, which are games played by humans that produce useful computation as a side-effect. The most famous example is the ESP Game,^[12] an online game^[13] in which two randomly paired people are simultaneously shown the same picture, with no way to communicate. Each then lists a number of words or phrases that describe the picture within a time limit, and are rewarded with points for a match. This match turns out to be an accurate description of the picture, and can be successfully used in a database for more accurate image search technology. The ESP Game was licensed by Google in the form of the Google Image Labeler, and is used to improve the accuracy of the Google Image Search. Von Ahn's games brought him further coverage in the mainstream media. His thesis won the Best Doctoral Dissertation Award from Carnegie Mellon University's School of Computer Science.

In July 2006, von Ahn gave a tech talk at Google on "Human Computation" (i.e., crowdsourcing) that became viral and was watched by over one million viewers.^[14]

In 2007, von Ahn invented reCAPTCHA, a new form of CAPTCHA that also helps digitize books. In reCAPTCHA, the images of words displayed to the user come directly from old books that are being digitized; they are words that optical character recognition could not identify and are sent to people throughout the Web to be identified. ReCAPTCHA is currently in use by over 100,000 web sites and is transcribing over 40 million words per day.^[15]

As of 2011, von Ahn is working on Duolingo, a project that aims to coordinate millions of people to translate the Web into every major language.^[16]

Teaching[link]

Von Ahn has used a number of unusual techniques in his teaching, which have won him multiple teaching awards at Carnegie Mellon University.^[17] In the fall of 2008, he taught a new course at Carnegie Mellon entitled "Science of the Web".^[18]

See also[link]

• MacArthur Fellows Program

References[link]

External links[link]

• Luis von Blog, Luis von Ahn's weblog
• Luis von Ahn on Twitter
• Google Tech Talk on human computation by Luis von Ahn
• Google Image Labeler
• John D. and Catherine T. MacArthur Foundation
• Example of SEO Project given at CMU
• Profile: Luis von Ahn NOVA scienceNOW aired 2009-06-30
• Luis von Ahn at TED Conferences