The Fallacy of Cracking Contests

[Bruce Schneier <schneier@counterpane.com>]

	The Fallacy of Cracking Contests
                      Bruce Schneier


You see them all the time: "Company X offers $1,000,000 to anyone who can
break through their firewall/crack their algorithm/make a fraudulent
transaction using their protocol/do whatever."  These are cracking
contests, and they're supposed to show how strong and secure the target of
the contests are.  The logic goes something like this:  We offered a prize
to break the target, and no one did.  This means that the target is secure.

It doesn't.

Contests are a terrible way to demonstrate security.  A
product/system/protocol/algorithm that has survived a contest unbroken is
not obviously more trustworthy than one that has not been the subject of a
contest.  The best products/systems/protocols/algorithms available today
have not been the subjects of any contests, and probably never will be.
Contests generally don't produce useful data.  There are three basic
reasons why this is so.

1.  The contests are generally unfair.  

Cryptanalysis assumes that the attacker knows everything except the secret.
 He has access to the algorithms and protocols, the source code,
everything.  He knows the ciphertext and the plaintext.  He may even know
something about the key.

And a cryptanalytic result can be anything.  It can be a complete break: a
result that breaks the security in a reasonable amount of time.  It can be
a theoretical break: a result that doesn't work "operationally," but still
shows that the security isn't as good as advertised.  It can be anything in
between.

Most cryptanalysis contests have arbitrary rules.  They define what the
attacker has to work with, and how a successful break looks.  Jaws
Technologies provided a ciphertext file and, without explaining how their
algorithm worked, offered a prize to anyone who could recover the
plaintext.  This isn't how real cryptanalysis works; if no one wins the
contest, it means nothing.

Most contests don't disclose the algorithm.  And since most cryptanalysts
don't have the skills for reverse-engineering (I find it tedious and
boring), they never bother analyzing the systems.  This is why COMP128,
CMEA, ORYX, the Firewire cipher, the DVD cipher, and the Netscape PRNG were
all broken within months of their disclosure (despite the fact that some of
them have been widely deployed for many years); once the algorithm is
revealed, it's easy to see the flaw, but it might take years before someone
bothers to reverse-engineer the algorithm and publish it.  Contests don't
help.

(Of course, the above paragraph does not hold true for the military.  There
are countless examples successful reverse-engineering--VENONA, PURPLE--in
the "real" world.  But the academic world doesn't work that way,
fortunately or unfortunately.)

Unfair contests aren't new.  Back in the mid-1980s, the authors of an
encryption algorithm called FEAL issued a contest.  They provided a
ciphertext file, and offered a prize to the first person to recover the
plaintext.  The algorithm has been repeatedly broken by cryptographers,
through differential and then linear cryptanalysis and by other statistical
attacks.  Everyone agrees that the algorithm was badly flawed.  Still, no
one won the contest.

2.  The analysis is not controlled.

Contests are random tests.  Do ten people, each working 100 hours to win
the contest, count as 1000 hours of analysis?  Or did they all try the same
things?  Are they even competent analysts, or are they just random people
who heard about the contest and wanted to try their luck?  Just because no
one wins a contest doesn't mean the target is secure...it just means that
no one won.

3.  Contest prizes are rarely good incentives.  

Cryptanalysis of an algorithm, protocol, or system can be a lot of work.
People who are good at it are going to do the work for a variety of
reasons--money, prestige, boredom--but trying to win a contest is rarely
one of them.  Contests are viewed in the community with skepticism: most
companies that sponsor contests are not known, and people don't believe
that they will judge the results fairly.  And trying to win a contest is no
sure thing: someone could beat you, leaving you nothing to show for your
efforts.  Cryptanalysts are much better off analyzing systems where they
are being paid for their analysis work, or systems for which they can
publish a paper explaining their results.

Just look at the economics.  Taken at a conservative $125 an hour for a
competent cryptanalyst, a $10K prize pays for two weeks of work, not enough
time to even dig through the code.  A $100K prize might be worth a look,
but reverse-engineering the product is boring and that's still not enough
time to do a thorough job.  A prize of $1M starts to become interesting,
but most companies can't afford to offer that.  And the cryptanalyst has no
guarantee of getting paid: he may not find anything, he may get beaten to
the attack and lose out to someone else, or the company might not even pay.
 Why should a cryptanalyst donate his time (and good name) to the company's
publicity campaign?

Cryptanalysis contests are generally nothing more than a publicity tool.
Sponsoring a contest, even a fair one, is no guarantee that people will
analyze the target.  Surviving a contest is no guarantee that there are no
flaws in the target.

The true measure of trustworthiness is how much analysis has been done, not
whether there was a contest.  And analysis is a slow and painful process.
People trust cryptographic algorithms (DES, RSA), protocols (Kerberos), and
systems (PGP, IPSec) not because of contests, but because all have been
subjected to years (decades, even) of peer review and analysis.  And they
have been analyzed not because of some elusive prize, but because they were
either interesting or widely deployed.  The analysis of the fifteen AES
candidates is going to take several years.  There isn't a prize in the
world that's going to make the best cryptanalysts drop what they're doing
and examine the offerings of Meganet Corporation or RPK Security Inc., two
companies that recently offered cracking prizes.  It's much more
interesting to find flaws in Java, or Windows NT, or cellular telephone
security.

The above three reasons are generalizations.  There are exceptions, but
they are few and far between.  The RSA challenges, both their factoring
challenges and their symmetric brute-force challenges, are fair and good
contests.  These contests are successful not because the prize money is an
incentive to factor numbers or build brute-force cracking machines, but
because researchers are already interested in factoring and brute-force
cracking.  The contests simply provide a spotlight for what was already an
interesting endeavor.  The AES contest, although more a competition than a
cryptanalysis contest, is also fair 

Our Twofish cryptanalysis contest offers a $10K prize for the best negative
comments on Twofish that aren't written by the authors.  There are no
arbitrary definitions of what a winning analysis is.  There is no
ciphertext to break or keys to recover.  We are simply rewarding the most
successful cryptanalysis research result, whatever it may be and however
successful it is (or is not).  Again, the contest is fair because 1) the
algorithm is completely specified, 2) there are no arbitrary definition of
what winning means, and 3) the algorithm is public domain.

Contests, if implemented correctly, can provide useful information and
reward particular areas of research.  But they are not useful metrics to
judge security.  I can offer $10K to the first person who successfully
breaks into my home and steals a book off my shelf.  If no one does so
before the contest ends, that doesn't mean my home is secure.  Maybe no one
with any burgling ability heard about my contest.  Maybe they were too busy
doing other things.  Maybe they weren't able to break into my home, but
they figured out how to forge the real-estate title to put the property in
their name.  Maybe they did break into my home, but took a look around and
decided to come back when there was something more valuable than a $10,000
prize at stake.  The contest proved nothing.

Gene Spafford wrote against hacking contests.
http://www.itd.nrl.navy.mil/ITD/5540/ieee/cipher/old-issues/issue9602

Matt Blaze has too, but I can't find a good URL.


**********************************************************************
Bruce Schneier, President, Counterpane Systems     Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN  55419      Fax: 612-823-1590
           Free crypto newsletter.  See:  http://www.counterpane.com