From: tcmay@got.net (Timothy C. May)
Date: Tue, 26 Mar 1996 04:26:34 +0800
To: cypherpunks@toad.com
Subject: Why and how people work for free on "challenges"
Message-ID: <ad7b38320002100490f1@[205.199.118.202]>
MIME-Version: 1.0
Content-Type: text/plain


At 12:56 AM 3/25/96, Black Unicorn wrote:

>I think, should you have the right attitude, many people here will be
>happy to review your source code, given some pre-conditions.  Mr. May
>summed these up quite well only days ago in the IDG (or whatever)
>snakeoil thread.  I would suggest you take a gander at his post on the
>subject.  Briefly, (and I hope I'm not butchering his points to
>bitterly), he indicated that unless you had hit on most of the basic
>source material to begin with (applied cryptography for example), and
>really knew a bit about the subject, most people wouldn't much care to
>pay attention to you.
>
>I think, however, that if you know your stuff, and you release the source
>code to the list, many people here will be open minded enough to take a
>good look, give you some pointers, perhaps even improve your work.

While I'm certainly no expert in cryptanalysis, the situation with "Can you
break this?" challenges is a special case--and an important one--of
challenges in general.

To cut to the chase, why do challenges work at all? And under what
circumstances?

A challenge that grabs the attention of key people can result in vastly
more effort being put into a task than could be effectively marshalled
almost any other way. An example will make this clearer: human-powered
flight. A challenge prize was offered for the first human-powered flight
around some particular set of pylons...I don't recall the details, but it
was heavily publicized some years back. Vast amounts of effort were put
into this.

Flight, like cryptanalysis, has long been a fairly ideal area for such
challenges. But, like crypto, there are some things that work for such
challenges (and some things that don't).

* the challenge should come from a reputable group or individual (casual
challenges of the "I dare you" sort thus get winnowed out)

* the challenge should involve something "interesting"....first solo flight
across the Atlantic, first human-powered flight, etc.

* the challenge needs to come at the right time. There would be little
interest, for example, in a challenge about the first fusion-powered flight
(excluding solar-powered, which was a challenge).

There is, for example, likely to be little or no interest if I pose this
challenge: "I challenge any of you to fly from San Francisco to Canberra to
Taipei and back to San Francisco without once saying a single word." The
challenge needs to arouse wide interest.

In crypto, there have been _many_ challenges which basically meet the sorts
of criteria I listed. Ralph Merkle offered a prize for anyone who could
break the knapsack algorithm (iterated, or somesuch...cf. Schneier etc. for
details). This was already an important issue, so the challenge was taken
seriously. Shamir ultimately claimed the prize. Later prizes followed a
similar trend.

And there were challenges by Rivest, involving RSA, which an MIT team
ultimately broke (RSA-129). Our own Derek Atkins was involved (and he may
be able to say more about why RSA challenges are more interesting to
students and faculty than are mere "Here's my new cipher" challenges. And
the CIA even has a challenge involving a statue or seal outside its Langley
headquarters building. Not to mention the Beale Cipher.

So, a reasonable challenge will likely generate a lot of free effort. Even
a $1000 prize, if combined with other factors, will draw attention. The
prize itself is not important; it is the defining of precise conditions for
success that is important and interesting.

The recent "I challenge Cypherpunks to break our unbreakable system"
challenge from Snake Oil Associates failed on several grounds. There was no
real evidence the algorithm was "interesting," there was no evidence the
folks at SOA were competent and worth going up against, the conditions of
the challenge were suspect, and there was no substantive prize making
effort potentially rewarding. (The offered to sell the company for $1 to
whomever broke their system, but now seem to have reneged, predictably
enough.)

Even so, a couple of Cypherpunks analyzed their system (parts of which were
secret, usually another killer for effective challenges!). In less than a
day, a crack was reported. (The motive here was yet another one, not listed
above. Namely, the desire to go "gunning" for the incompetent newbies and
cretins.)

So, well-planned challenges can be effective. Naive and puerile challenges
of the sort "I dare you to break this! I double-dog dare you to!" are
rarely treated seriously. Not too surprising.

Bayesian statistics says that someone we've never heard from before is
unlikely to be producing a new cipher which is interesing enough to try to
break. A new cipher from Rivest or the like would of course be somewhat
more likely to be analyzed (though even these ciphers are rarely analyzed
directly).

>Take a look at Mr. May's cyphermonicon, (anyone have the URL/FTP handy
>for our new friend?)

The URL I like is http://www.oberlin.edu/~brchkind/cyphernomicon/. Though,
as I have noted in other threads, I have very little if anything on
"cryptanalysis" per se. Modern ciphers are just not very amenable to
attacks via conventional cryptanalysis. (And symmetric-key ciphers are
really, really old news.)


--Tim May

Boycott "Big Brother Inside" software!
We got computers, we're tapping phone lines, we know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^756839 - 1  | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."