Analyzing CAPTCHAs

New research: “Attacks and Design of Image Recognition CAPTCHAs.”

Abstract. We systematically study the design of image recognition CAPTCHAs (IRCs) in this paper. We first review and examine all IRCs schemes known to us and evaluate each scheme against the practical requirements in CAPTCHA applications, particularly in large-scale real-life applications such as Gmail and Hotmail. Then we present a security analysis of the representative schemes we have identified. For the schemes that remain unbroken, we present our novel attacks. For the schemes for which known attacks are available, we propose a theoretical explanation why those schemes have failed. Next, we provide a simple but novel framework for guiding the design of robust IRCs. Then we propose an innovative IRC called Cortcha that is scalable to meet the requirements of large-scale applications. Cortcha relies on recognizing an object by exploiting its surrounding context, a task that humans can perform well but computers cannot. An infinite number of types of objects can be used to generate challenges, which can effectively disable the learning process in machine learning attacks. Cortcha does not require the images in its image database to be labeled. Image collection and CAPTCHA generation can be fully automated. Our usability studies indicate that, compared with Google’s text CAPTCHA, Cortcha yields a slightly higher human accuracy rate but on average takes more time to solve a challenge.

The paper attacks IMAGINATION (designed at Penn State around 2005) and ARTiFACIAL (designed at MSR Redmond around 2004).

Tags: , , ,

Posted on October 5, 2010 at 7:22 AM • 38 Comments

Comments

Clive Robinson • October 5, 2010 8:02 AM

I’m glad the authors of the paper realise how CPATCHAs actually work as,

“a task that humans can perform well but computers cannot”

It has however two issues involved with it,

1, Computers are and will get better at these “human” taks.

2, Attackers have avoided the wait on 1 by employing humans to do the job.

It is the second issue that needs to be fixed or accounted for in any new design (which they don’t appear to have addressed).

The real solution in this area is to use not just context sensitive with respect to the image but context sensitive with regards to the individual for these systems to have a security value above 30cents (the current going rate for Chinese and other “Capatcher droids”.

Yes there are ways this can be done but all those that are currently known “academicaly” need some kind of centrralised authority in one form or another which precludes anonymous activities.

Jay from BKK • October 5, 2010 8:20 AM

@Clive Robinson

30 cents each is highway robbery. In Bangkok my labor cost to compensate a sufficiently English literate, numerate and Mac-savvy workforce in such an undertaking would be only US$12 per man per day.

bob • October 5, 2010 9:26 AM

“Attackers have avoided the wait on 1 by employing humans to do the job.”

Attackers have even avoided that by creating porn sites that require a captcha. Obviously, the captcha comes from the target site and the answer is logged.

See also various warez forums, etc that use other people’s captchas to a) protect them from spam bots and b) break the captchas…

Gavin B. • October 5, 2010 9:54 AM

if it is chinese human’s that the captcha is intended to defeat then it could be based on a task that is culturally difficult for them to perform – like matching face-pairs of European people.
Since for many Europeans many Chinese look alike – why not switch the tables.

Greg Linden • October 5, 2010 10:24 AM

Not sure this matters. CAPTCHAs are broken these days by farms of hundreds of low paid human workers — see Stefan Savage’s research on this — not automated attacks. This new CAPTCHA scheme won’t help with that.

fine • October 5, 2010 10:31 AM

If humans are cheaper than computers for breaking CAPTCHAs, what more can you really hope to do at this point?

“Beat me in a Quake deathmatch 1 on 1 to enter this website.”

or

“Sing us a song about when you were workin’ on the pea farm.”

kog999 • October 5, 2010 10:35 AM

The real solution in this area is to use not just context sensitive with respect to the image but context sensitive with regards to the individual for these systems to have a security value above 30cents (the current going rate for Chinese and other “Capatcher droids”.

I’m not sure how you could do that with a site like gmail that needs to cater to random members of the public. Anything that people like my parents could do that 30 cent worker can do also.

D • October 5, 2010 10:51 AM

@bob

How’s that not “employing humans”? Unless you take “employ” to mean “hire and pay” which isn’t always the case. See definition 2.

slyib • October 5, 2010 10:58 AM

I find the idea of the CORTCHA interesting. And amusing, especially if a random photo happens to be snagged from a p0rn site. Try explaining that one to the HR folks…

Nice effort, though. Bruce, thanks for the find.

EH • October 5, 2010 11:12 AM

Anybody who would use $12/day workers to break CAPTCHAs would certainly want to save even more money by avoiding repeating the same captchas over and over. The image should be shifted around the space of a few pixels to throw off the hasher that keeps repeats out of the worker pool.

Ersun Warncke • October 5, 2010 1:26 PM

The costs I have seen advertised publicly are .2 cents ($0.002) per solved captcha from established solving services that advertise on google. These services are relatively new, so they will improve with time, and prices will fall with increased competition. At this point, I would consider captchas to be completely broken in terms of actual security, with the practical security they offer falling along the cost curve vs. potential profit from bypassing them. Combining advanced OCR techniques with human verification, where the human op checks the OCR result, then only has to enter the challenge response if the computer got it wrong, only lowers the cost. Improving captcha technology to fight against improving image processing and OCR techniques helps to keep the overall cost at the current levels, but doesn’t address the underlying problem of the current costs of bypass already being so low that they allow for a wide variety of profitable compromise schemes. It should also be remembered that a bypass service can do adaptive visual enhancement to make a captcha image easier for a human op to solve (resizing, tweaking contrast, etc) even if it can’t actually solve it automatically. Basically, different approaches to security are required: either using server based detection of automated bots (possible now) or moving to trusted ids with users identified by digital signature (a very long way off considering that in the infinite wisdom of the W3C they did not address the most fundamental weakness in the current version of the web with HTML5).

Clive Robinson • October 5, 2010 2:30 PM

@ Ersun Warncke,

“The costs I have seen advertised publicly are .2 cents ($0.002) per solved captcha from established solving services that advertise on google.”

Ouch, thats lower than the proverbial snake sphincter in a wheel rut.

“considering that in the infinite wisdom of the W3C they did no address the most fundamental weakness in the current version of the web with HTML5)”

Hmm there are a few arguments either way but two of interest are,

1, Authentication is not a fundemental atrabute of HTML, it’s an addition.

2, Prescribing any particular method is either going to age rapidly or run up against political issues.

AppSec • October 5, 2010 2:59 PM

I’ve been fighting against CAPTCHA for a long time. There just is no point to it and it was fairly obvious that it would be broken in one way or another — either via workforce or automation.

While I understand the need for recognizing computer vs. human, it just seems to be that we are going about it the wrong way — and ultimately isn’t the goal of Aritifical Intelligence to eliminate the distinction?

Even timings don’t solve the problem.

jgreco • October 5, 2010 3:07 PM

@AppSec

Exactly. I can only see the situation getting worse and worse. People arn’t going to get any better at solving CAPTCHAs so it’s really only a matter of time until machines can match and overcome the average person. Eventually the only way to stop spam will be the old fashion way with filters, because comment content will be the only distinguishing feature between humans with insightful comments and spambots looking to sell their crap.

Kai Howells • October 5, 2010 3:38 PM

I’m actually struggling myself with some CAPTCHAs – Google for instance will have me re-log in to my account periodically and some of the CAPTCHAs that they’re using are unreadable.

How about a system where instead of typing in what the word is (which it’s been noted that computers are getting better and better at) we have to identify a picture – for instance be shown three pictures of animals and have to identify the bird. This is a little more abstract and harder for a computer to solve, but is trivial for a human.

Sure, it doesn’t solve the issue of having people paid to solve the CAPTCHAs, but it is a step in the right direction

Donn • October 5, 2010 3:48 PM

I also studied the IMAGINATION CAPTCHA and found that by using a very basic statistical attack, I could automatically pass the first stage with 53% accuracy (compared to 74% in this paper with a sophisticated attack). The attack I used was based on locations of the click zones (the centres of the images in the collage). By collecting enough clicks, it was possible to make a very good guess about where the most probable successful click would be.

GSE • October 5, 2010 4:22 PM

@Kai Howells

If you read TFA you would see that such things have been attempted, but they aren’t scalable up to Gmail-sized websites due to the human interaction required during the labeling phase. The other issue with that is that labeling can be subjective and unreliable (many humans don’t know the difference between a leopard and a tiger, for example).

A quick summary of the proposed CAPTCHA process:
An image is taken (almost any image will do) and a portion of it is removed using automated object recognition. The empty space is filled up using automatic filling (ala photoshop’s band-aid feature) and then the user must pick that object from similar-shaped objects and place it in the correct place in the photo. Page 10 of the PDF has a sample photo.

Glenn Maynard • October 5, 2010 4:54 PM

If figure 7 and 8 (there are no page numbers for me–PDF needs to die) is their ideal demonstration example, then it’s a terrible idea. Captchas need to be instantly, intuitively solvable–not a puzzle that needs to be solved.

They go on to claim that fifteen seconds is an acceptable time to require a human to spend to solve a captcha. I doubt they honestly believe that themselves. Why not open a copy of King’s Quest and make me finish the game before I can use your website?

Mark • October 5, 2010 6:06 PM

Their comparison table (table 1) omits ReCAPTCHA, which is interesting in that it contains a feedback loop for current machine ability (i.e., filters words that are easy for a machine to recognize). ReCAPTCHA still doesn’t adress the crack-it-with-a-human aproach (aside from some measures against man-in-the-middle).

Eivind • October 6, 2010 1:12 AM

It doesn’t matter. Even a captcha that successfully distinguishes human from robot, is useless if the human in question is doing the job of a robot.

Captchas must be easy to solve for average humans, no more than 5-10 seconds on average, which means that you get on the order of 4000 solved for a single days wage. Given a supply of literate workers willing to work for say $40/day in such a boring, but safe and fairly comfy job, that works out 1 cent each.

Really, the best one can do, is to either skip the things entirely, or alternatively, atleast use something where solving the captchas is actually useful, as for example what recaptcha does.

Spammers still get account for 1 cent a piece, but atleast that way, something useful is acomplished in the process.

AC2 • October 6, 2010 2:54 AM

Well MY website will display an obfuscated image of a mathematical formula and ask a simple question, e.g.

“sin^2 x + cos^2 x = ?” or
“e = m.c^x, then x = ?”, or better
“x^2 = -1, then x = ?”, or better still
” x / 0 = ?”

Donn • October 6, 2010 3:07 AM

@Kai Howells

We have implemented such a system but have found that depending on the image dataset used, resistance to automated attacks is less than ideal. Subjectivity is mitigated by semantically matching the proposed labels via the WordNet lexicon.

Try it out for yourself:

http://dolphin.unige.ch/tagcaptcha/

The idea was to use principles from the ESP Game and reCAPTCHA in order to exploit CAPTCHAs to annotated images. The research paper is here:

http://portal.acm.org/citation.cfm?id=1600166

Peter A. • October 6, 2010 3:58 AM

Every free-of-charge service that offers useful resources, like storage space, “advertisement” space (for example a way to publish links to websites), email sending capability etc. etc. will get massively abused, CAPTCHA or no CAPTCHA. Live with that. There are only two real solutions:

  1. Police the service by hiring large enough staff of admins, moderators etc. This costs real money, so the service may not be able to sustain the free-of-charge-for-end-user business model.
  2. Collect a fee. If the fee is higher than the eventual proceedings of most abuse cases, the abuse will effectively stop or diminish to marginal levels.

So this is a business decision. Offer a “free” service and get a large body of users and a relatively large body of abusers, get ready to bear the costs of abuse and collect your $$$s by indirect means (like advertising or selling users’ data to third parties) or get a smaller body of users willing to pay for your excellent service, getting real $$$s from each active account.

Of course, you may use both approches: collect a fee to prevent massive bot-generated abuse and police out the remaining abuse by using much smaller staff of moderators paid out of a fraction of fees collected.

Implementing stronger CAPTCHAs is a slippery slope – before you limit abuse to acceptable level you’ll start getting more and more annoyed and angry users, and hurt your business seriously.

AppSec • October 6, 2010 12:44 PM

CAPTCHA Response time:
I don’t want to waste 5-10 seconds trying to decipher a string and then find out that I mis-read one of the elements. That is not “acceptable”. It might be “required”, but that is different.

There are plenty of ways to add “blocks” for these type which are automated or human without affecting your real users. It requires logic and thinking and an accepting less than 100% success.

Doug Coulter • October 6, 2010 10:15 PM

Back when we were advertising our services as DSP experts, I got many emails asking us if we could “solve the captcha” problem — eg read them in an automated way.

I hope the nasty response emails we sent helped. It was obvious then why someone would want that.
(a few years back)

Wayne • October 7, 2010 7:54 AM

Captcha suck IMO. I spend as much time requesting a new imagine so i can read the blasted thing then I do answering them.

Nostromo • October 7, 2010 3:49 PM

This research is pointless: human labor is very cheap, so there’s no point in automating captcha recognition.

@Peter A.: there is another solution – authentication. The user establishes his/her identity by a digital signature.

jgreco • October 7, 2010 4:52 PM

@Obijan at October 6, 2010 11:54 PM

Checking for symmetry with facial recognition software will get you pretty decent results there. Throw in some heuristics to try to guesstimate weight and I’m sure you could beat that CAPTCHA a good percentage of the time.

RE Vernoti • October 8, 2010 3:05 PM

You don’t even have to employ individuals to fill out captchas. It’s as simple as:

  1. Setting up dummy web pages offering something for free in exchange for filling out the form. These can be automated.

  2. Framing a captcha image from any site you want to bypass and putting it on the dummy form

  3. You could even go so far as to use the individuals information on said site where you’re trying to break captcha

Ersun Warncke • October 11, 2010 5:16 PM

@Clive Robinson

“1, Authentication is not a fundemental atrabute of HTML, it’s an addition.”

True, but client side relational databases, 2D graphics, etc, are not any more “fundamental” to HTML than digital signature and encryption infrastructure. In fact, every modern browser already has the infrastructure built in through TLS support. It is just not made available to web developers.

If you wanted to implement digital signatures and encryption on the client side, a natural place would be through elements with a corresponding API accessible through JavaScript, so until W3C does it, it won’t happen.

See the element, which is part of the current HTML5 recommendation, and provides some functionality, but is hardly complete (and Microsoft refuses to support it).

“2, Prescribing any particular method is either going to age rapidly or run up against political issues.”

I agree that the main problem here is political on one hand and business driven on the other hand. The U.S. government is strongly opposed to broad dispersal of strong cryptography to consumers. Advertisers, social networking sites, etc, would all suffer financially from having users able to encrypt their content and digitally sign their uploads. I.e. if users could digitally sign and retain ownership of what they upload it would kill all of the sites which are built around delivering advertising using free content uploaded by users without providing them any compensation for their work.

AviD • October 20, 2010 8:45 AM

I notice most of the comments here are mostly anti-CAPTCHA, to begin with… So I’ll just throw another comment on the pile :).

I did an analysis of CAPTCHA implementations at an OWASP conference couple years ago, and it comes down to these:
– Most sites, implement CAPTCHA wrong – wrong configuration, wrong settings, static images, exposing the answer, etc.
– Even for those that “get it right” (and by now a large portion of those sites are using reCAPTCHA), OCR is usually good enough, or almost good enough, to solve the CAPTCHA most of the time…
– But it’s easier to just use CAPTCHA proxies…
– or CAPTCHA farms (i.e. buying in bulk from those low-cost far-east outsourcers). I had found a listing on eBay, 4$ for every 1000 CAPTCHAs “solved” – even had an SLA for reliability %…

It’s like I’ve always said, CAPTCHA tries to solve the wrong problem, and it does it badly: even if it worked perfectly, the problem is not “I want to identify who is a computer and who is a human and allow only humans to use my site however they want”, but rather “I want to prevent misuse and flooding on my site”. We shouldnt be trying to turing-test the users, we should be limiting what they could do.
AKA authentication (or identification) is a poor replacement for authorization.

Vasiliy Alibabevitch • December 21, 2010 11:16 AM

All mentioned approaches are victim-oriented.

Professional spambots (or amateur’s persistence + time) circumvent them programmatically with ease and, if not, just send screenshots (or webpages) to 3d party human solvers (while keeping thousands of connections open untill getting solution).

The other problem is context-based spam when even the author of blog fails to detect that he is having dialogs inserted by AI-enabled bots. The easiest approach is just to determine the topic (this is pretty easily automated) abd insert from different IPs of different countries the phrases of human dialogs taken from other web boards (chats, blog comments, forums, etc.)

So, there is no sense in further complicating captchas without understanding and realizing the mechanisms needed to be blocked like resending (screenshots and/or webpages) captchas to 3d party human solvers.

The only known at the moment protection against context-sensitive spamming and resending captchas to 3d parties is KeyCAPTCHA (keycaptcha.com).

It is developed by former spambot developers, having multiple level of protection, completely free, unbreakable by bots.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.