INTRODUCTION
A captcha is a program that can generate and grade tests that:
 |
| Captcha |
can't pass. Such a program can be used to differentiate humans
from computers and has many applications for practical security,
including (but not limited to):
--- Online Polls.
In November 1999, slashdot.com released an online poll askingwhich was the best graduate school in computer science (a
dangerous question to ask over the web!). As is the case with
most online polls, IP addresses of voters were recorded in order to
prevent single users from voting more than once. However,
students at Carnegie Mellon found a way to stuff the ballots by
using programs that voted for CMU thousands of times. 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 other school with less than 1,000.
Can the result of any online poll be trusted? Not unless the poll
requires that only humans can vote.
---Free Email Services.
Several companies (Yahoo!, Microsoft, etc.) offer free emailservices, most of which suffer from a specifc type of attack:
"bots" that sign up for thousands of email accounts every minute.
This situation can be improved by requiring users to prove they
are human before they can get a free email account. Yahoo!, for
instance, uses a captcha of our design to prevent bots from
registering for accounts. Their captcha asks users to read a
distorted word such as the one shown below (current computer
programs are not as good as humans at reading distorted text).
---Search Engine Bots.
Some web sites don't want to be indexed by search engines. Thereis an html tag to prevent search engine bots from reading web
pages, but the tag 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 that bots won't enter a web site, captchas are needed.
---Worms and Spam.
captchas also offer a plausible solution against email worms andspam: only accept an email if you know there is a human behind
the other computer. A few companies, such as
www.spamarrest.com are already marketing this idea.
---Preventing Dictionary Attacks.
Pinkas and Sander have 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 the passwords.
The goals of this paper are to lay a solid theoretical foundation for
captchas, to introduce the concept to the cryptography
community, and to present several novel constructions.
CAPTCHA stands for "Completely Automated Public Turing Test to
Tell Computers and Humans Apart." The P for Public means that
the code and the data used by a CAPTCHA should be publicly
available. This is not an open source requirement, but a security
guarantee: it should be difficult for someone to write a computer
program that can pass the tests generated by a CAPTCHA even if
they know exactly how the CAPTCHA works (the only hidden
information is a small amount of randomness utilized to generate
the tests) The T for "Turing Test to Tell" is because CAPTCHAs are like
Turing Tests . In the original Turing Test, a human judge was
allowed to ask a series of questions to two players, one of which
was a computer and the other a human. Both players pretended to
be the human, and the judge had to distinguish between them.
CAPTCHAs are similar to the Turing Test in that they distinguish
humans from computers, but they differ in that the judge is now a
computer. A CAPTCHA is an Automated Turing Test. We
deliberately avoid using the term Reverse Turing Test (or even
worse, RTT)because it can be
misleading Reverse Turing Testhas been used to refer to a form of the Turing Test in which both players pretend to be a computer
