(fwd) DES challenge organisation

An announcement forwarded to me (due to being on des-challenge mailing
list I think) of proposed organisation for breaking RSADSI's DES
challenge.

Those interested in participating might wish to join the lists
mentioned.

In addition the list: des-challenge@muffin.org is for discussion of
the DES challenge, and can be subscribed to by sending email to
majordomo@muffin.org.

-Adam

======================================================================
Subject: Announcement: Organisation Committee
From: ths@rz.tu-ilmenau.de (Thomas S.)
Date: 15 Feb 1997 18:27:40 +0000

Hi!

The six volunteers who answered the call for a committee of
management have got together to try to help 'steer' the DES challenge.
We have considered the available options of proceeding, and we kindly
ask everyone interested in this project to follow our proposals, to
avoid waste of efforts.

1. The attempt to break the key will be coordinated. We chose this
   mainly because we can make a political statement. We don't want it
   to be a race for money.
   
   Each task will be handled by logically separate servers, some of
   which with be replicated and run as a hierachy. The protocol will
   use UDP, although there will be gateway servers for other protocols
   (such as HTTP, SMTP, FAX, etc). We hope that one of the first
   requests for a key range will be from parties interested in using a
   "random" approach -- we would appreciate some discussion on how
   large their ranges should be.

2. There will be one consistent WWW structure for the project. It does
   not have to managed by a single person. This structure should
   provide statistics, information for developers, interested users
   and perhaps even for the press. Several mirrors and translations
   will be started soon. The starting point is:
	http://www.des.crypto.org/ [fh28.fa.umist.ac.uk/des/]
   The url in brackets has to be used till we get the final subdomain.
   Likewise for the rest of this document.

3. The work of the different groups should be stated and coordinated
   on the page http://www.des.crypto.org/people.html.
   [fh28.fa.umist.ac.uk/des/people.html] This is to avoid uncoordinated
   parallel developmemt. Please write to Thomas S. 
   <webmaster@mail.des.crypto.org> [webmaster@fh28.fa.umist.ac.uk] 
   if you what want to be mentioned on this page. 

3a. Several mailing lists have been set up for the different groups: 

des-coding	for the actual DES routine and optimisation
des-networking	for the network code and protocol
des-www		for www contributions and mirrors
des-pr		for press contact, translations etc (like challenge-pr)
des-misc	:-)
des-announce	moderated, important information for users of the client

List address: <list>@lists.des.crypto.org [@xtn.net] 
To subscribe, send mail to majordomo@lists.des.crypto.org [@xtn.net] 
with in the body of the message (several actions allowed): 
   subscribe <list> 
Achives available (see homepage).

4. The actual DES routine has to be written and optimised. We ask
   developers to participate and coordinate their efforts using the
   mailing list des-coding. For obvious reasons, developers outside
   the USA are prefered, but "publication" of algorithms seems to be
   a legal way go get around. Please do not use this list to 
   distribute crypto code.

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.

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.

The organisation committee:

Piete Brooks <Piete.Brooks@cl.cam.ac.uk>
Jered Floyd <jered@mit.edu>
Tim Newsome <drz@froody.bloke.com>
Germano Caronni <caronni@tik.ee.ethz.ch>
Thomas Roessler <Thomas.Roessler@sobolev.rhein.de>
Thomas S. <ths@fh28.fa.umist.ac.uk>

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.

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`

-----BEGIN PGP SIGNED MESSAGE-----

On Sat, 15 Feb 1997, Adam Back wrote:

> > 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

Unless people modify the client, we will know about it before they do.
Yes, people might cheat. Main point is we don't want to turn this into a
race for money. (Also, that way we can't use university machines etc.)
This topic has been discussed too often also. Read the archives for more
debate.

Tim

Tim Newsome. Programmer for Megasoft. Student at CMU. Cynic in life.
Intel sucks. Motorola forever! If it's not PGP signed, it didn't come from me. 
Always look on the bright side of life. I think I think therefore I think I am.
drz@froody.bloke.com  http://www.local.com/~tnewsom/  PGP key: 2048/C32F01A5

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3a
Charset: noconv
Comment: In God we trust. Everybody else we verify using PGP!

iQEVAwUBMwh34PKkXTDDLwGlAQE/KggAmWk9rL86fknnXWy9ASPWQokH6J0vEzW+
qhrBklXwv0Lz5HGNV92OM0qh9KI+bqFct9aNY0B15g6APspSUNYr7RaXI2/LaSYb
0gG7YpPe2kHFdSWsodhYyu7DTzYvdDI1AJOmEnSUKHQPKiLwU/RgVZiLEttuvIcS
GCjDEGEW7C0YIrQKTkLoYKkSHz6HHXQ+/hr66yCBMD7AIS1C/p9yN2ticmQ3hLnd
DYSpVQb9NudLcU0bGZC1U31o70hSVmyETTt9VcuJCOXseiggWTZsZuNK/D+f5TfA
WBEcIAWToBHfrWSokuF9nunAarmcddQyPu/93hzRkgODVTWgmnpOGA==
=IuAs
-----END PGP SIGNATURE-----

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."

Timothy C. May wrote:

 > The organizer of the coordinated search must then, I surmise, keep the
 > assignments secret and dole out keyspace securely.

Perhaps they should DES-encrypt the list of assignments :-)

    - mark

--------------------------------------------------------------------
I tried an internal modem,                          newton@dotat.org
     but it hurt when I walked.                          Mark Newton
----- Voice: +61-4-1155-2401 ------------- Fax: +61-8-83732527 -----

Adam Back <aba@dcs.ex.ac.uk> writes:

 > 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.

Of course they will.  If the unsearched portions of the keyspace
are published, you can just sit back until the odds go up and
then throw some CPU power at it.  There is no obligation on the
part of the individual who finds the key to not claim the prize
personally.

The issues of random keyspace assignment to protect against
sabotage and centralized monolithic server vs autonomous client
have been debated on the "muffin" list, where I have been
lurking, but the people in charge seem to like explicit keyspace
partitioning and servers a lot.

Should be an interesting effort.

By the way, does anyone know if des-challenge@muffin.org is
alive?  I haven't seen any messages from it in over a day and
majordomo is not responding to inquiries.

--
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $

On Feb 15,  5:01pm, Timothy C. May wrote:
> Subject: Re: (fwd) DES challenge organisation
> 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.)
> 
	The motivation to crack the DES challenge is more the
political one of proving DES (aka 56 bit encryption in the popular press)
insecure than the financial one of getting the $10,000 prize. To actually
get a good mesaure of the strength of DES using this approach, the number
of machines that participated in the attack and the time they spend
has to be known. This is a main reason why Germano's team prefers
the search to be co-ordinated and why they have been asking people not
to start the search before the server is ready.

> 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.
 
	Knowing the number of people they were able to get to participate
in the RC5 attack, this is not a significant problem. They are going to
have 5000 clients nibbling away on the not-yet-searched keyspace. Some 
Johnny-come-lately trying to muscle in on the action towards the end
is not going to make a significant dent in their chances of hitting the
correcy key first.

> 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.

	Again, they didn't have a problem getting people to join in on
the RC5/32/12/6 attack. At least the same number of people can be expected
to join in for the DES attack, giving an estimated search time of around
eight months, if nobody else builds a hardware DES cracker first.

--
Anil Das

Hi!

(wow, what a distribution. I should mention that des-challenge is down
this weekend, so the response may not be as expected.)

>>>>> "Timothy" == Timothy C May <tcmay@got.net> writes:

    Timothy> 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?

The client reports the key to the server, not to the user (very
simple, and very simple ways to get around of course). In a nutshell:
we can't enforce it, at least I can't see a way to do so. We certainly
can't keep people from doing their own "treasure hunt".

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

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

Indeed--that's what we try to avoid. Our project is not a race for
money, it is a demonstration with a political impact.

The main point in favour of a coordinated search is the availability
of progress reports. Nobody can argue that the key was found by
chance--as there is exact data about performance and the expected
maximum duration for the search.

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

This is a technical problem which is discussed at the moment. The
keyspace will not be publically announced (and it wasn't during the
last project).

			Thomas
-- 
    OOOO,    OOOOOOOO,  |, ths@rz.tu-ilmenau.de
  OO,   OO,   O,    O,  |, http://www.rz.tu-ilmenau.de/~ths/
 O,       O,   O,       |, ______   __   ___
 O, O--O, O,    O,      |,  |      (_   |-|-`   
 O,       O,   O,       |,  |homas __)te| |en   
  OO,   OO,   O,    O,  |, 
    OOOO,    OOOOOOOO,  |, not to be forwarded without permission