Captchas

[seminar class]

PRESENTED BY:
Sandeep Bal

---

CAPTCHA

---

[attachment=13781]
INTRODUCTION
CAPTCHA  Completely Automated Public Turing Test to tell Computers and Humans Apart
 The term "CAPTCHA" was coined in the year 2000 by Luis Von Ahn, Manuel Blum, Nicholas J. Hopper (all of Carnegie Mellon University(CMU)), and JohnLangford (then of IBM).
CAPTCHA is a program that is a challenge –response test to separate humans from computer programs
Generic CAPTCHAs distort letters and Numbers
Distorted characters are presented to user
User has to recognize the distorted Letters
If the guessed letters are correct, the user is inferred to be a human and allowed access
Humans can read the distorted and noisy text.
Background
Why CAPTCHA was needed?
To prevent the following
Sabotage of online polls
Worms and Spam e-mails
Search engine BOTs
Preventing dictionary attacks(password cracking)
Tampering with rankings on recommendation systems (e.g. Ebay,Amazon etc)
Altavista first used a crude CAPTCHA in their sites
That resulted in 95% spam reduction
Yahoo partnered CMU to counter the threats in Messenger chat service
Luis von Ahn and Manuel Blum of
CMU trademarked CAPTCHA in 2000
What is a Turing test?
Proposed by Alan TuringTo test a machine’s level of intelligenceHuman judge asks questions to twoparticipants, one is a machine and other is a human the judge doesn’t know which is machine or which is human.
If judge can’t tell which is the machine,
The machine passes the test
CAPTCHA employs a Reverse Turing Test(RTT),
judge = CAPTCHA program,participant = userif user passes CAPTCHA, he is humanif user fails, it is a machine
Types of CAPTCHAs
Text based
Gimpy, ez-gimpy
Gimpy-r, Google CAPTCHA
Simard’s HIP (MSN)
Graphic based
Bongo
Pix
Audio based
Text Based CAPTCHAs
Gimpy, ez-gimpy
Pick a word or words from a small dictionary
Distort them and add noise and background
Gimpy-r, Google’s CAPTCHA
Pick random letters not from dictionary.
Distort them, add noise and background
Simard’s HIP(MSN’s CAPTCHA)
Pick random letters and numbers
Distort them and add arcs
Some Text Based CAPTCHAs
Graphic based CAPTCHAs:
BONGO:
User has to solve a pattern recognition
problem
Has to tell the distinct characteristic
between two sets of figure
Then to which set the given figure belongs to
PIX:
Uses a large database of labelled images
It shows a set of images, user has to recognize the common feature among those
E.g., Pick the common characteristic
among the following four pictures
“Airplane”
Audio CAPTCHAs:
Consist of downloadable audio clip
User listens and enters the spoken word
Helps visually disabled users
Below is the Google’s audio enabled
CAPTCHA
Not popular
APPLICATION
Protect online polls
Prevent Web registration abuse,protect passwords from brute-force attack
Prevent comment spam and spam e-mail
E-ticketing , prevent scalping
Help advance Artificial Intelligence knowledge
CAPTCHAs are called Hard-AI problems
A win-win scenario:
If CAPTCHAs are broken by a bot, a Hard-
AI problem is solved
If its not yet broken, then current implementation is able to withstand Attacks
Thus AI knowledge is advanced if CAPTCHAs are broken
CONSTRUCTING CAPTCHAs
Things to keep in mind:
Don’t store CAPTCHA solution in Web
page’s metadata
A CAPTCHA is no good if it doesn't
distort
Need a large database of different
CAPTCHA questions
Avoid repetition of questions
CAPTCHA Logic:
Generate the question
Persist the correct answer
Present the question to user
Evaluate answer, if incorrect, startagain-- Generate a different CAPTCHA
If correct, allow access to user
Embeddable CAPTCHAs:
Available freely, just embed code into
Web page’s HTML, from e.g.,recaptcha.net
No maintenance
Custom CAPTCHAs:
Fits to the theme of the page
Better protected from spammers
Can be written in any language– Perl,
.NET, ASP, JavaScript
BREAKING CAPTCHAs
Exploiting bugs in the implementation that allows attacker to bypass CAPTCHAs.
Cracking CAPTCHAs through programs :
Convert CAPTCHA into greyscale
Detect patterns in the image
corresponding to Characters
Or, read session files of that user and
know the CAPTCHA word
Solution:
Only store a hash of the
CAPTCHA word in session files
Greg Mori and Jitendra Malik have broken text CAPTCHAs, e.g., Ez- Gimpy
To break this CAPTCHA )
Segmentation: Locate possible
letters in the image------->
Construct graph of consistent
letters ----------------------------->
Find out plausible words from
the graph, use scores to rank
roll=11.94, profit=9.42 (better match) 
Social engineering to break CAPTCHAs:
Spammer encounters a CAPTCHA
That CAPTCHA is copied to another site
Humans are baited, e.g., free MP3s
To get those MP3s, users are told tosolve the copied CAPTCHA
Solution is routed to the spammer
Solution: Fix a time-to-live period for a Question.
CAPTCHA cracking as a business:
Firms offer CAPTCHA cracking service in
exchange for money
ISSUEs with CAPTCHAs
Usability issues:
Some CAPTCHAs are inaccessible to
visually impaired, cognitively challenged
People
Compatibility issues:
JavaScript may need to be activated in
browsers
Some may need Adobe Flash plugin
SUMMARY
CAPTCHAs are an effective way to
counter bots and reduce spam
They serve dual purpose– help
advance AI knowledge
Applications are varied– from
stopping bots to character
recognition & pattern matching
Some issues with current
implementations represent
challenges for future improvement