|
INTRODUCTION
A
captcha is a program that can generate and grade tests that: (A) most humans can
pass, but (B) current computer programs 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 asking which 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 email services, 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. There is 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 and spam: 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 Test has been used to refer to a form of the Turing
Test in which both players pretend to be a computer
<<back
|