[cryptography] CAPTCHA as a Security System?

Marcus Brinkmann marcus.brinkmann at ruhr-uni-bochum.de
Mon Jan 2 14:03:07 EST 2012

On 01/02/2012 06:58 PM, Jeffrey Walton wrote:
> I was reading "CAPTCHA: Using Hard AI Problems For Security" by Ahn,
> Blum, Hopper, and Langford (www.captcha.net/captcha_crypt.pdf).
> I understand how recognition is easy for humans and hard for computer
> programs.

But is that really true?

My personal experience with CAPTCHAs is that they are increasingly hard to
decipher for humans.  Has the scale already tipped over in favor of computer

Computer programs today are limited by attention of experts (programmers,
researchers).  What does "hard for computer programs" actually mean then?  Is
there a theoretical boundary that limits the abilities of computer programs to
recognize captures, or is Ahn just exploiting a temporary lack of economic
incentive to realize the full capabilities of computer systems for these kind
of problems?

IMO, the problems that computers are really (as opposed to currently) bad at
often turn out to be the problems that defy objective solutions.  Many
recaptcha (OCR) problems are ambiguous.  If there is no objective solution to
a problem, how can performance be evaluated?

> Where is the leap made that CAPTCHA is a [sufficient?]
> security device to protect things like web accounts, email accounts,
> and blog comments? It seems to me that a threat model in which bots
> (ie, programs) are the only adversary is flawed.

Louis von Ahn's favorite subject is "human computation".  A separation between
(the capabilities of) humans and computers is axiomatic to his research,
otherwise his whole subject would evaporate.

There are two fundamental assumptions made: First, there are problems that are
hard for computers to solve but easy for computers to generate.  Second, the
bad guys can muster huge computational resources but few human resources.

The first assumption is a, at least for the time being, a rejection of the
Church-Turing conjecture.

The second assumption is an extrapolation of past experiences into the future,
and as such very optimistic/naive.

I don't know about any justification offered for either dogma.  Ahn's Phd
thesis[1] is surprisingly void of a theoretical underpinning of his work, in
fact, it does not even contain the phrase "Church-Turing".  It is also
completely void of any security analysis.

You'd think that a phd thesis about "human computation" applied to security
problems would at least contain something on either, but if there is, I can't
find it.

[1] http://www.scribd.com/doc/2533967/Human-Computation-PhD-Thesis-Luis-von-Ahn


More information about the cryptography mailing list