Defeating Bots with CAPTCHAs

Paladion
By Paladion

December 15, 2005

Bots are software that crawl through your web site, make auto registrations and attempt automated attacks like password guessing. This article shows how to stop Bots in their tracks using a technique called CAPTCHAs.

Bots are software that crawl through your web site, make auto registrations and attempt automated attacks like password guessing. This article shows how to stop Bots in their tracks using a technique called CAPTCHAs.

CAPTCHA is an acronym for ‘Completely Automated Public Turing Test to Tell Computers and Humans Apart’. We discussed the basics of CAPTCHAs in this Palisade article a year ago. CAPTCHA technology was pioneered by researchers at Carnegie Mellon University; it relies on an Artificial Intelligence problem presented to website visitors to distinguish between humans and bots. Initially, CAPTCHAs were distorted images of words: they were easily recognizable by humans, but posed a difficult task for a bot. Then on, several CAPTCHA implementations have been developed. In this article, we will be discussing some of the most used ones.

Visual CAPTCHA

The Visual CAPTCHA is the most widely used form of CAPTCHA implementations. This form of CAPTCHA uses images of words, colors or objects. Most people can identify the image whereas it becomes a complex task for a bot. Here’s an example of a Visual CAPTCHA:

CAPTCHA
Fig 1: "Methadone"

Here the word “methadone” has been shown off a little distorted manner with a shaded background.

CAPTCHAAnother form of Visual CAPTCHA is a pattern recognition CAPTCHA. These CAPTCHAs exhibit a pattern and provide the visitor with a choice of solutions. Bongo is a program that provides the user with a pattern recognition problem. Here’s a typical example of a pattern recognition CAPTCHA: What’s the symbol in the second row, second column?

There are also other variants of visual CAPTCHAs such as displaying distorted words in 3D, patterns with a noisy background, and odd images to be identified of a group of like images. These CAPTCHAs can also require humans to use mouse clicks rather than typing the solutions.

This type of CAPTCHA is simple and easy to implement.

CAPTCHAThe main disadvantage of Visual CAPTCHAs, however, is that they are inaccessible to the visually impaired. Concerns over this have led to CAPTCHA implementations that could be used by the visually impaired as well. Further, many visual CAPTCHAs are weakly distorted or improperly implemented enabling bots to identify it easily. For example, the EZ-Gimpy CAPTCHA shown on the side, can be easily identified by a bot:

Greg Mori and Jitendra Malik of UC Berkeley Computer Vision Group wrote an algorithm to defeat the EZ-Gimpy CAPTCHAs and managed to reach a success rate of 92%. They published a paper that completely describes the method used to break the CAPTCHA, which is available at here.

The strength of these CAPTCHAs also depends on the way they are implemented. For example, if the image files are stored in the web server with specific names indicating the image, an automated bot could identify the image after repeated visits to the web pages or by traversing through the web server directories for image files.

On the other hand, if the words are heavily distorted, it becomes difficult for even humans to recognize it: this makes the CAPTCHA ineffective.

Auditory CAPTCHA

This type of CAPTCHAs came to be used to address the needs of the visually impaired. Even though it is not as popular as the Visual CAPTCHA, it is an effective alternative for blind users. In this case, it becomes difficult for the automated bots to break this type of CAPTCHA as it requires good speech recognition capability. For example, Hotmail provides the option of using an audio CAPTCHA in case the visual doesn’t suit the user. Some audio CAPTCHAs are also distorted with obscure tones and frequencies.

The main advantage of this type of CAPTCHA over a visual CAPTCHA is that it is much more difficult to break and so provides a much safer option for application owners.

Audio CAPTCHAs are however inaccessible for users with no sound card, or no required plugins, or those working in noisy environments. Another problem is that the audio CAPTCHA may not be human recognizable at times due to the distortion of the sound or the accent used in the audio CAPTCHA may not be understandable to the users from different parts of the world. Also many users tend to write down the code while listening to the audio, which makes it even more inconvenient.

Logical CAPTCHA

The objective of a CAPTCHA is to differentiate a human from a bot. This can be achieved by testing for the general knowledge or the ability of a user to solve logical problems. In this case, users are presented with a simple logical or mathematical or general knowledge based question.

As most people are capable of solving numeric based math questions, this CAPTCHA system uses English based math questions. One form of this mathematical CAPTCHA can be “5 + 3 = ?”. But automated bots are today capable of parsing this question and getting the right answer using appropriate programs. Hence a better form of a mathematical CAPTCHA can be “what is ten plus the number of characters in the word CAPTCHA? Write the answer in English.” More examples of logical / knowledge based CAPTCHA are:

  1. “Which liquid can be used to put off fire?”
  2. “Write in words the number characters in ‘United States of America’ ?”
  3. “Which is the southern most continent on earth?”

A detailed description of this technique along with the question generation and answer verification procedure is available here.

It is very difficult for an automated bot to crack this type of CAPTCHA while it is easier for most humans to answer. The major challenge in implementing this type of CAPTCHA, however, is that the database of questions has to be large and the questions selected should be more random and not static.

Breaking CAPTCHAS

Even though many techniques are used to implement CAPTCHAs, automated bots are being developed to break them. Many of the Visual CAPTCHAs have been broken by several CAPTCHA projects. PWNtcha is a project that demonstrates the inefficiency of many Visual CAPTCHA implementations. The OCR research team have also analyzed and published a list of weak CAPTCHAs used in several websites. aiCAPTCHA is a technique that uses Artificial Intelligence to beat Visual CAPTCHAs. Spammers could have a programmer paid for aggregating the images and provide them to a human operator in sequence to verify them easily. A variant of that idea is using visitors to adult web sites to decode a CAPTCHA of a different site before granting access to the adult site – this uses free human labor to solve CAPTCHAs. A blog post on this idea written by Cory Doctorow is available here. As the use of CAPTCHAs increase, we can expect more innovative attacks and solutions against them.

References


Tags: Technical

About

Paladion