Re: (fwd) DES challenge organisation

["Timothy C. May" <tcmay@got.net>]

At 11:02 PM +0000 2/15/97, Adam Back wrote:
>Thomas S <ths@fh28.fa.umist.ac.uk> writes:
>> [...]
>>
>> 5. The prize money will be split equally between Gutenberg and EFF.
>>    There is a possibility of using part of it for stickers or
>>    something similar, but don't count on it.
>
>Not a good idea.
>
>How can this be enforced?  The RSADSI DES challenge is open to all
>comers, and how do you prove that someone who finds the key found it
>through this group effort?
>
>I have a suspicion many people would be tempted to fill in the RSA
>challenge form and email it in themselves.  $10,000 is a fair amount
>of money.

Once again, the advantages of an "uncoordinated search" should be
mentioned. An uncoordinated search, in which people randomly search chunks
of keyspace is obviously less efficient than a coordinated search where no
part of the space is searched two or more times.

However, an uncoordinated search is only less efficient by a small factor
of two or three, with a 95% probability that the key will be found with an
effort "only" 3 times greater than with a coordinated search. (The Poisson
probability distribution is what's involved here, and the math is fairly
easy to work out.)

A 2-4x factor is significant, and may warrant a coordinated search.
However, the various problems implicit in coordinated searches are factors,
too.

Also, an uncoordinated search solves the "prize" problem, as whomever finds
the key makes  the contact with RSADSI.

One of the problems with a coordinated search, if the remaining keyspace to
be doled out is publically announced, is that as the keyspace is searched
and a key _not_ found, the remaining keyspace is increasingly more tempting
for "independent searchers" to search. Sort of the way the odds on some
lotteries actually become "acceptable" as the lottery pot grows. The
organizer of the coordinated search must then, I surmise, keep the
assignments secret and dole out keyspace securely.

Having the prize money go to the finder of the key, as opposed to some
artificial division between EFF, Gutenberg, etc., is also an incentive for
people to contribute more CPU time.

--Tim May





>I know I would be tempted.  I have been running Svend Olaf's DES code,
>and my intention in the unlikely event that I hit the key had been to
>claim the money.
>
>How does it hurt the publicity if the actual individual who finds the
>key takes the money?  Surely it adds excitement to the story?
>
>In fact it would provide people with a possibly more powerful
>incentive to try to break the key in the first place -- in the hopes
>of winning the prize!  $10,000 means more to a lot of people than
>opposing ITAR/EAR, and participating in a technical challenge.  To
>start with a lot of people who's CPUs we could be using don't even
>know what ITAR/EAR are!
>
>> We hope to get a working system up and running ASAP. The fact alone
>> that DES is seriously challenged (with a reasonable time frame)
>> should give us quite some publicity (by the time the system is
>> ready). If we can make use of that, we will have significantly more
>> client than for the 48 bit key.
>
>I would have thought announcing that $10,000 can be won by running
>easy to use windows software on a wide selection of newsgroups would
>get you lots of CPUs!
>
>Adam
>--
>print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
>)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`


Just say "No" to "Big Brother Inside"
We got computers, we're tapping phone lines, I 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^1398269     | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."