Misplaced Pages

CAPTCHA: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 18:07, 25 June 2013 view sourceMicrophonics (talk | contribs)136 edits →External links: adding a link about client-side CAPTCHA using data hashes← Previous edit Revision as of 19:10, 25 June 2013 view source Hipal (talk | contribs)Extended confirmed users, Pending changes reviewers, Rollbackers137,994 edits Undid revision 561552091 by Microphonics (talk) off topicNext edit →
Line 95: Line 95:
* *
* *
*


=== Defeating CAPTCHAs === === Defeating CAPTCHAs ===

Revision as of 19:10, 25 June 2013

Not to be confused with reCAPTCHA.

A CAPTCHA (an initialism for "Completely Automated Public Turing test to tell Computers and Humans Apart", trademarked by Carnegie Mellon University) is a type of challenge-response test used in computing to determine whether or not the user is human. The term was coined in 2000 by Luis von Ahn, Manuel Blum, Nicholas J. Hopper of Carnegie Mellon University, and John Langford of IBM. The most common type of CAPTCHA was first invented by Mark D. Lillibridge, Martin Abadi, Krishna Bharat, and Andrei Z. Broder. This form of CAPTCHA requires that the user type the letters of a distorted image, sometimes with the addition of an obscured sequence of letters or digits that appears on the screen. Because the test is administered by a computer, in contrast to the standard Turing test that is administered by a human, a CAPTCHA is sometimes described as a reverse Turing test. This term is ambiguous because it could also mean a Turing test in which the participants are both attempting to prove they are the computer.

This CAPTCHA of "smwm" obscures its message from computer interpretation by twisting the letters and adding a background color gradient.

Origin and inventorship

Since the early days of the Internet, users have wanted to make text illegible to computers. The first such people were hackers, posting about sensitive topics to online forums they thought were being automatically monitored for keywords. To circumvent such filters, they would replace a word with look-alike characters. HELLO could become |-|3|_|_() or )-(3££0, as well as numerous other variants, such that a filter could not possibly detect all of them. This later became known as leetspeak.

The first discussion of automated tests which distinguish humans from computers for the purpose of controlling access to web services appears in a 1996 manuscript of Moni Naor from the Weizmann Institute of Science, entitled "Verification of a human in the loop, or Identification via the Turing Test".

Subsequent to that work, two teams of people have claimed to be the first to invent the CAPTCHAs used throughout the Web today. The first team consists of Mark D. Lillibridge, Martin Abadi, Krishna Bharat, and Andrei Z. Broder, who used CAPTCHAs in 1997 at AltaVista to prevent bots from adding URLs to their search engine. Looking for a way to make their images resistant to OCR attack, the team looked at the manual to their Brother scanner, which had recommendations for improving OCR's results (similar typefaces, plain backgrounds, etc.). The team created puzzles by attempting to simulate what the manual claimed would cause bad OCR.

The second team to claim inventorship of CAPTCHAs consists of Luis von Ahn and Manuel Blum, who described CAPTCHAs in a 2003 publication and subsequently received much coverage in the popular press. Their notion of CAPTCHA covers any program that can distinguish humans from computers, including many different examples of CAPTCHAs.

The controversy of inventorship has been settled by the existence of a 1998 patent by Lillibridge, Abadi, Bharat, and Broder, which predates other publications by several years. Though the patent does not use the term CAPTCHA, it describes the ideas in detail and precisely depicts the graphical CAPTCHAs used in the Web today.

Applications

CAPTCHAs are used to prevent bots from using various types of computing services or collecting certain types of sensitive information. Applications include preventing bots from taking part in online polls, registering for free email accounts (which may then be used to send spam) and collecting email addresses. CAPTCHAs can prevent bot-generated spam by requiring that the (unrecognized) sender pass a CAPTCHA test before the email message is delivered, but the technology can also be exploited by spammers by impeding OCR detection of spam in images attached to email messages. CAPTCHAs have also been used to prevent people from using bots to assist with massive downloading of content from multimedia websites. They are used in online message boards and blog comments to prevent bots from posting spam links as a comment or message.

Characteristics

CAPTCHAs are by definition fully automated, requiring little human maintenance or intervention in administering the test. This has obvious benefits in cost and reliability.

By definition, the algorithm used to create the CAPTCHA must be made public, though it may be covered by a patent. This is done to demonstrate that breaking it requires the solution to a difficult problem in the field of artificial intelligence (AI) rather than just the discovery of the (secret) algorithm, which could be obtained through reverse engineering or other means.

Accessibility

CAPTCHAs based on reading text — or other visual-perception tasks — prevent blind or visually impaired users from accessing the protected resource. However, CAPTCHAs do not have to be visual. Any hard artificial intelligence problem, such as speech recognition, can be used as the basis of a CAPTCHA. Some implementations of CAPTCHAs permit users to opt for an audio CAPTCHA. Other implementations do not require users to enter text, instead asking the user to pick images with common themes from a random selection.

For non-sighted users (for example blind users, or the color blind on a color-using test), visual CAPTCHAs present serious problems. Because CAPTCHAs are designed to be unreadable by machines, common assistive technology tools such as screen readers cannot interpret them. Since sites may use CAPTCHAs as part of the initial registration process, or even every login, this challenge can completely block access. In certain jurisdictions, site owners could become target of litigation if they are using CAPTCHAs that discriminate against certain people with disabilities. For example, a CAPTCHA may make a site incompatible with Section 508 in the United States. In other cases, those with sight difficulties can choose to identify a word being read to them.

While providing an audio CAPTCHA allows blind users to read the text, it still hinders those who are both visually and hearing impaired. According to sense.org.uk, about 4% of people over 60 in the UK have both vision and hearing impairments. There are about 23,000 people in the UK who have serious vision and hearing impairments. According to The National Technical Assistance Consortium for Children and Young Adults Who Are Deaf-Blind (NTAC), there were 9,516 deafblind children in the USA in 2004. Gallaudet University quotes a 1993 estimate of 35,000 fully deafblind adults in the USA. Deafblind population estimates depend heavily on the degree of impairment used in the definition. An open question is what fraction of people cited as impaired use websites that would restrict them.

The use of CAPTCHA thus excludes a small number of individuals from using significant subsets of such common Web-based services as PayPal, GMail, Orkut, Yahoo!, many forum and weblog systems, etc.

Even for perfectly sighted individuals, new generations of graphical CAPTCHAs, designed to overcome sophisticated recognition software, can be very hard or impossible to read.

A method of improving the CAPTCHA to ease the work with it was proposed by ProtectWebForm and was called "Smart CAPTCHA". Developers advise to combine the CAPTCHA with JavaScript support. Since it is too hard for most of spam robots to parse and execute JavaScript, using a simple script which fills the CAPTCHA fields and hides the image and the field from human eyes was proposed.

One alternative method involves displaying to the user a simple mathematical equation and requiring the user to enter the solution as verification. Although these are much easier to defeat using software, they are suitable for scenarios where graphical imagery is not appropriate, and they provide a much higher level of accessibility for visually impaired users than the image-based CAPTCHAs. These are sometimes referred to as MAPTCHAs (M = 'Mathematical'). However, these may be difficult for users with a cognitive disorder.

Other kinds of challenges, such as those that require understanding the meaning of some text (e.g., a logic puzzle, trivia question, or instructions on how to create a password) can also be used as a CAPTCHA. Again, there is little research into their resistance against countermeasures.

See also: Web accessibility

Circumvention

There are a few approaches to defeating CAPTCHAs: using cheap human labor to recognize them, exploiting bugs in the implementation that allow the attacker to completely bypass the CAPTCHA, and finally improving character recognition software.

Cheap or unwitting human labor

It may be possible to subvert CAPTCHAs by relaying them to a sweatshop of human operators who are employed to decode CAPTCHAs. The W3C paper linked below states that such an operator "could easily verify hundreds of them each hour". Nonetheless, some have suggested that this would still not be economically viable. Another technique used consists of using a script to re-post the target site's CAPTCHA as a CAPTCHA to a site owned by the attacker, which unsuspecting humans visit and correctly solve within a short while for the script to use.

Insecure implementation

Howard Yeend has identified two implementation issues with poorly designed CAPTCHA systems:

  • Some CAPTCHA protection systems can be bypassed without using OCR simply by re-using the session ID of a known CAPTCHA image.
  • Captchas residing on shared servers also present a problem; a security issue on another virtual host may leave the CAPTCHA issuer's site vulnerable.

Sometimes, if part of the software generating the CAPTCHA is client-side (the validation is done on a server but the text that the user is required to identify is rendered on the client side), then users can modify the client to display the unrendered text. Some CAPTCHA systems use MD5 hashes stored client-side, which may leave the CAPTCHA vulnerable to a brute-force attack.

Computer character recognition

Although CAPTCHAs were originally designed to defeat standard OCR software designed for document scanning, a number of research projects have proven that it is possible to defeat many CAPTCHAs with programs that are specifically tuned for a particular type of CAPTCHA. For CAPTCHAs with distorted letters, the approach typically consists of the following steps:

  1. Removal of background clutter, for example with color filters and detection of thin lines.
  2. Segmentation, i.e. splitting the image into segments containing a single letter.
  3. Identifying the letter for each segment.

Step 1 is typically very easy to do automatically. In 2005, it was also shown that neural network algorithms have a lower error rate than humans in step 3. The only part where humans still outperform computers is step 2. 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 step 2, the segmentation.

Neural networks have been used with great success to defeat CAPTCHAs as they are generally indifferent to both affine and non-linear transformations. As they learn by example rather than through explicit coding, with appropriate tools very limited technical knowledge is required to defeat more complex CAPTCHAs.

Some CAPTCHA-defeating projects:

  • Mori et al. published a paper in IEEE CVPR'03 detailing a method for defeating one of the most popular CAPTCHAs, EZ-Gimpy, which was tested as being 92% accurate in defeating it. The same method was also shown to defeat the more complex and less-widely deployed Gimpy program 33% of the time. However, the existence of implementations of their algorithm in actual use is indeterminate at this time.
  • PWNtcha has made significant progress in defeating commonly used CAPTCHAs, which has contributed to a general migration towards more sophisticated CAPTCHAs.
  • A number of Microsoft Research papers describe how computer programs and humans cope with varying degrees of distortion.

Image recognition CAPTCHAs vs. character recognition CAPTCHAs

With the demonstration (through research publications) that character recognition CAPTCHAs are vulnerable to computer vision based attacks, some researchers have proposed alternatives to character recognition, in the form of image recognition CAPTCHAs which require users to identify simple objects in the images presented. The argument is that object recognition is typically considered a more challenging problem than character recognition, due to the limited domain of characters and digits in the English alphabet.

Some proposed image recognition CAPTCHAs include:

  • Chew et al. published their work in the 7th International Information Security Conference, ISC'04, proposing three different versions of image recognition CAPTCHAs, and validating the proposal with user studies. It is suggested that one of the versions, the anomaly CAPTCHA, is best with 100% of human users being able to pass an anomaly CAPTCHA with at least 90% probability in 42 seconds.
  • Datta et al. published their paper in the ACM Multimedia '05 Conference, named IMAGINATION (IMAge Generation for INternet AuthenticaTION), proposing a systematic way to image recognition CAPTCHAs. Images are distorted in such a way that state-of-the-art image recognition approaches (which are potential attack technologies) fail to recognize them.

References

  1. Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/3-540-39200-9_18, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/3-540-39200-9_18 instead.
  2. U.S. Patent 6,195,698. Method for selectively restricting access to computer systems. Filed on Apr 13, 1998 and granted on Feb 27, 2001. Available at http://www.google.com/patents/US6195698
  3. The W3C paper Inaccessibility of CAPTCHA outlined some of the accessibility problems with CAPTCHAs.
  4. The article Proposal for an accessible Captcha describes how audio and visual test can be combined to increase accessibility in a Captcha.
  5. "HumanAuth supports ADA and Section 508 requirements without forcing users to read distorted CAPTCHA text". Retrieved 2006-10-23.
  6. http://www.tr.wou.edu/ntac/index.cfm?path=publications/publications_census.html
  7. http://library.gallaudet.edu/dr/faq-stats-deaf-blind.html
  8. http://www.protectwebform.com/smartcaptcha
  9. "Hire People To Solve CAPTCHA Challenges". Petmail Design. 2005-07-21. Retrieved 2006-08-22.
  10. Doctorow, Cory (2004-01-27). "Solving and creating captchas with free porn". Boing Boing. Retrieved 2006-08-22.
  11. "Breaking CAPTCHAs Without Using OCR". Howard Yeend (pureMango.co.uk). 2005. Retrieved 2006-08-22.
  12. Kumar Chellapilla, Kevin Larson, Patrice Simard, Mary Czerwinski (2005). "Computers beat Humans at Single Character Recognition in Reading based Human Interaction Proofs (HIPs)" (PDF). Microsoft Research. Retrieved 2006-08-02. {{cite journal}}: Cite journal requires |journal= (help)CS1 maint: multiple names: authors list (link)
  13. http://www.cs.berkeley.edu/~mori/gimpy/mori_gimpy.pdf
  14. http://sam.zoy.org/pwntcha/
  15. http://research.microsoft.com/~kumarc/
  16. http://www.cs.berkeley.edu/~tygar/papers/Image_Recognition_CAPTCHAs/imagecaptcha.pdf
  17. http://en.wikipedia.org/CBIR
  18. http://infolab.stanford.edu/~wangz/project/imsearch/IMAGINATION/ACM05/

External links

Defeating CAPTCHAs

Categories: