From: mpd@netcom.com (Mike Duvos)
Date: Wed, 24 Jul 1996 15:47:41 +0800
To: cypherpunks@toad.com
Subject: Re: DES-Busting Screen Savers?
In-Reply-To: <ae1a5e6f1d021004c7bc@[205.199.118.202]>
Message-ID: <199607232002.NAA21336@netcom14.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


tcmay@got.net (Timothy C. May) writes:

 > -- Thus, the calculation will have to go 2-4 times longer
 > to give a high (>95%) chance that the answer is found. For
 > example, at 3 times the "efficient" search time, there is
 > only a 1/e^3 = 5% chance that nobody has found the answer

 > The probabalistic assignment is less efficient, obviously,
 > but has the advantage of not requiring a registry of
 > keyspace allocations. Further, "denial of service" attacks
 > (lying about having searched a chunk, or incorrectly
 > searching or reporting) are not a problem.

This is definitely the way to go when trying to break a block
cipher on the Net.  Partitioning out sieving works well for
distributed factoring only because verfying the submitted
relations requires a trivial amount of computer time compared
that expended in locating them.  There is no way for a central
server to verify a claim that a chunk of DES keyspace has been
thoroughly searched without a key being found, and it only takes
one bozo or saboteur to spoil the effort.

At triple the non-overlapping search time, we get about a 5%
chance of failure.  At quadruple, this falls to slightly less
than 2%.

Close enough for government work.

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