From: das@razor.engr.sgi.com (Anil Das)
Date: Sat, 15 Feb 1997 18:36:30 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: DES challenge organisation
In-Reply-To: <199702152256.WAA00403@server.test.net>
Message-ID: <9702151836.ZM26501@razor.engr.sgi.com>
MIME-Version: 1.0
Content-Type: text/plain


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