By Luis von Ahn, Manuel Blum, and John Langford

TELLINGHUMANS ANDCOMPUTERSAPART
AUTOMATICALLY
You’ve probably seen them—colorful images withdistorted text in them at the bottom of Web registration
forms. CAPTCHAs are used by Yahoo, Hotmail, PayPal andmany other popular Web sites to prevent automated registrations, and they work because no computer program cancurrently read distorted text as well as humans can. Whatyou probably don’t know is that a CAPTCHA is something

How lazy
cryptographers
do AI.

illustration by Jean-François Podevin

COMMUNICATIONS OF THE ACM February 2004/Vol. 47, No. 257

more than just an image with distorted text: it is atest, any test, that can be automatically generated,which most humans can pass, but that current computer programs cannot pass. Notice the paradox: aCAPTCHA is a program that can generate andgrade tests that it itself cannot pass (much like someprofessors).
CAPTCHA stands for “Completely AutomatedPublic Turing Test to Tell Computers and Humans
Apart.” The P for Public means that the code andthe data used by a CAPTCHA should be publicly
available. This is not an open source requirement,
but a security guarantee: it should be difficult forsomeone to write a computer program that can pass
the tests generated by aCAPTCHA even if theyknow exactly how theCAPTCHA works (theonly hidden information
is a small amount of randomness utilized to generate the tests). The T for“Turing Test to Tell” isbecause CAPTCHAs arelike Turing Tests [10]. In
the original Turing Test, ahuman judge was allowed to ask a series of questions
to two players, one of which was a computer and theother a human. Both players pretended to be thehuman, and the judge had to distinguish between
them. CAPTCHAs are similar to the Turing Test inthat they distinguish humans from computers, butthey differ in that the judge is now a computer. ACAPTCHA is an Automated Turing Test. We deliberately avoid using the term Reverse Turing Test (oreven worse, RTT) because it can be misleading—Reverse Turing Test has been used to refer to a formof the Turing Test in which both players pretend tobe a computer.

Applications
Although the goal of the original Turing Test was toserve as a measure of progress for artificial intelligence—a computer would be said to be intelligent if
it passed the Turing Test—making the judge be acomputer allows CAPTCHAs to be useful for otherpractical applications.
In November 1999, for example, the Web siteslashdot.com released an online poll asking which
was the best graduate school in computer science—a dangerous question to ask over the Web. As is thecase with most online polls, IP addresses of voterswere recorded in order to prevent single users fromvoting more than once. However, students at58

February 2004/Vol. 47, No. 2 COMMUNICATIONS OF THE ACM

Carnegie Mellon found a way to stuff the ballots byusing programs that voted for CMU thousands oftimes: CMU’s score started growing rapidly. The
next day, students at MIT wrote their own voting
program and the poll became a contest between voting “bots.” MIT finished with 21,156 votes,
Carnegie Mellon with 21,032 and every otherschool with less than 1,000. Can the result of any
online poll be trusted? Not unless the poll requiresthat only humans can vote.
Another application involves free email services.
Several companies offer free email services that havesuffered from a specific type of attack: “bots” thatsigned up for thousands of email accounts every
minute. This situation
has been improvedby requiring users toprove they are humanbefore they can get afree email account.
Yahoo, for instance, uses
a CAPTCHA of ourdesign to prevent botsfrom registering foraccounts.
Some Web sites don’t
Figure 1. Can you read threewant to be indexed bywords in this image?
search engines. There isa HTML tag to prevent
search engine bots from reading Web pages, but thetag doesn’t guarantee that bots won’t read the pages;
it only serves to say “no bots, please.” Search engine
bots, since they usually belong to large companies,
respect Web pages that don’t want to allow them in.
However, in order to truly guarantee bots won’t
enter a Web site, CAPTCHAs are needed.
CAPTCHAs also offer a plausible solution against
email worms and spam: only accept an email message
if you know there is a human behind the other computer. A few companies, such as www.spamarrest.
com are already marketing this idea.
Pinkas and Sander [9] have also suggested using
CAPTCHAs to prevent dictionary attacks in password systems. The idea is simple: prevent a computer from being able to iterate through the entire
space of passwords by requiring a human to type thepasswords.

Examples of CAPTCHAs
CAPTCHAs further differ from the original Turing
Test in that they can be based on a variety of sensory
abilities. The original Turing Test was conversational—the judge was only allowed to ask questions
over a text terminal. In the case of a CAPTCHA, theCAPTCHAs are similar to theTuring Test in that they distinguish humans
from computers, but they differ in that thejudge is now a computer.

computer judge can ask
any question that can betransmitted over a computer network.
GIMPY and OCR-based
CAPTCHAs. GIMPY [2]is one of the many
CAPTCHAs based on the
difficulty of reading distorted text. GIMPY works
by selecting seven words
out of a dictionary and rendering a distorted image
containing the words (as shown in Figure 1). GIMPY
then presents a test to its user, which consists of thedistorted image and the directions: “type three words
appearing in the image.” Given the types of distortions that GIMPY uses, most humans can read threewords from the distorted image, but current computer programs can’t. The majority of CAPTCHAs
used on the Web today
are similar to GIMPY inthat they rely on the difficulty of optical character recognition (thedifficulty of reading distorted text).
Bongo. Another example of a CAPTCHA isthe program we call
BONGO [2]. BONGO
is named after M.M.
Bongard, who publisheda book of pattern recognition problems in the1970s [3]. BONGO asks
the user to solve a visualpatternrecognition
problem. It displays two series of blocks, the left andthe right. The blocks in the left series differ fromthose in the right, and the user must find the characteristic that sets them apart. A possible left andright series is shown in Figure 2. After seeing the twoseries of blocks, the user is presented with a single
block and is asked to determine whether this block
belongs to the left series or to the right. The user
passes the test if he or she correctly determines theside to which the block belongs. Try it yourself: towhich side does the isolated block belong in Figure 3? (Answer: the rightside.)
PIX. PIX [2] is a program that has a large
database of labeledimages. All of theseimages are pictures ofconcrete objects (a horse,a table, a house, a flower).
The program picks anFigure 2. Everything on theleft is drawn with thick lines,
object at random, finds
while everything on the rightsix images of that object
is drawn with thin lines.
from its database, presents them to the user
and then asks the question “what are these picturesof?” Current computer programs should not be able
to answer this question, so PIX should be a
CAPTCHA. However,PIX, as stated, is not a
CAPTCHA: it is very
easy to write a programthat can answer the question “what are these pictures of?” Remember that
all the code and data of a
CAPTCHA should bepublicly available; in particular, the image database that PIX uses shouldbe public. Hence, writinga program that cananswer the question“what are these picturesof?” is easy: search thedatabase for the images
Figure 3. To which side does
presented and find their
the block on the bottomlabel. Fortunately, thisbelong?
can be fixed. One way for
PIX to become aCAPTCHA is to randomly distort the images before
presenting them to the user, so that computer programs cannot easily search the database for theundistorted image.
Sound-based CAPTCHAs. The final example weoffer is based on sound. The program picks a word
COMMUNICATIONS OF THE ACM February 2004/Vol. 47, No. 259

this approach has the beneficial side
effect of inducing security researchers, aswell as otherwise malicious programmers, toadvance the field of AI.
or a sequence of numbers at random, renders theword or the numbers into a sound clip and distorts
the sound clip; it then presents the distorted soundclip to the user and asks users to enter its contents.
This CAPTCHA is based on the difference in ability between humans and computers in recognizing
spoken language. Nancy Chan of the City University in Hong Kong was the first to implement asound-based system of this type [4].
It is extremely important to have CAPTCHAs
based on a variety of sensory abilities. AllCAPTCHAs presented here, except for the soundbased CAPTCHA, rely on the user being able to see
an image. However, since there are many visually
impaired people using the Web, CAPTCHAs basedon sound are necessary for accessibility.
Unfortunately, images and sound alone are notsufficient: there are people who use the Web that areboth visually and hearing impaired. The construction of a CAPTCHA based on a text domain such as
text understanding or generation is an important
open problem for the project.

A good example of this process is the recent
progress in reading distorted text images motivatedby the CAPTCHA in use at Yahoo. In response tothe challenge provided by this test, Malik and Mori[7] have developed a program that can pass the testwith over 80% accuracy. Malik and Mori’s algorithm represents significant progress in the generalarea of text recognition, and it is extremely encouraging to see such progress. A CAPTCHA implies awin-win situation: either the CAPTCHA is not broken and there is a way to differentiate humans fromcomputers, or the CAPTCHA is broken and a useful AI problem is solved. cReferences
1. Ahn, L. von, Blum, M., Hopper, N.J., and Langford, J. CAPTCHA:
Telling humans and computers apart. In Advances in Cryptology, Eurocrypt ‘03, volume 2656 of Lecture Notes in Computer Science, (2003),
294–311 .
2. Ahn, L. von, Blum, M., Hopper, N.J., and Langford, J. The
CAPTCHA Web page; www.captcha.net.
3. Bongard, M.M. Pattern Recognition. Spartan Books, Rochelle Park, NJ,1970.
4. Chan, N. Program Byan; drive.to/research.
5. Coates, A.L., Baird, H.S., and Fateman, R.J. Pessimal print: A Reverse
Turing Test. In Proceedings of the International Conference on Document
Analysis and Recognition (ICDAR ’01), Seattle, WA, 2001, 1154–1159.
6. Lillibridge, M.D., Abadi, M., Bharat, K., and Broder, A. Method forselectively restricting access to computer systems. U.S. Patent
6,195,698.
7. Mori, G. and Malik, J. Recognizing objects in adversarial clutter—
Breaking a visual CAPTCHA. In Proceedings of the Conference on Computer Vision and Pattern Recognition, June 2003.
8. Naor, M. Verification of a human in the loop or identification via the Turing Test; www.wisdom.weizmann.ac.il/\~naor/PAPERS/human.ps.
9. Pinkas, B. and Sander, T. Securing passwords against dictionaryattacks. In Proceedings of the ACM Computer and Security Conference(CCS ’02), ACM Press, 161–170.
10. Turing, A.M. Computing machinery and intelligence. Mind 59, 236(1950), 433–460.

Lazy Cryptographers Doing AI
Modern cryptography has shown that open or
intractable problems in number theory can be useful: an adversary cannot act maliciously unless hecan solve an open problem (like factor a very large
number). Similarly, CAPTCHAs show that open
problems in AI can be useful: adversaries cannot
vote thousands of times in online polls or obtainmillions of free email accounts unless they can solve
an open problem in AI.
In the case of ordinary cryptography, it isassumed (for example) that the adversary cannot fac- Luis von Ahn (biglou@cs.cmu.edu) is a graduate student in thetor 1024-bit integers in any reasonable amount of Department of Computer Science at Carnegie Mellon University.
Blum (mblum@cs.cmu.edu) is the Bruce Nelson
time. In our case, we assume the adversary cannot ManuelProfessor in the Department of Computer Science at Carnegie
solve an artificial intelligence problem with higher Mellon University.
accuracy than what’s currently known to the AI John Langford (jl@tti-c.org) is a research associate in thecommunity [1, 2, 5, 6, 8]. This approach has the Toyota Technological Institute at Chicago.
beneficial side effect of inducing security researchers,
Permission to make digital or hard copies of all or part of this work for personal or classas well as otherwise malicious programmers, to room use is granted without fee provided that copies are not made or distributed foror commercial advantage and that copies bear this notice and the full citation on
advance the field of AI (much like computational profit
the first page. To copy otherwise, to republish, to post on servers or to redistribute tonumber theory has been advanced since the advent lists, requires prior specific permission and/or a fee.
of modern cryptography). This is how lazy cryptog© 2004 ACM 0002-0782/04/0200 $5.00
raphers do AI.
60

February 2004/Vol. 47, No. 2 COMMUNICATIONS OF THE ACM