From: "Mark M." <markm@voicenet.com>
Date: Wed, 24 Jul 1996 14:27:00 +0800
To: cypherpunks@toad.com
Subject: Re: DES-Busting Screen Savers?
In-Reply-To: <ae1a5e6f1d021004c7bc@[205.199.118.202]>
Message-ID: <Pine.LNX.3.94.960723223340.330A-100000@gak>
MIME-Version: 1.0
Content-Type: text/plain


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

On Wed, 24 Jul 1996, Timothy C. May wrote:

> BTW, sitting in my hot tub last night I quickly reconstructed the math for
> the "random" keyspace inefficiency:
> 
> -- Imagine that N users are "randomly" picking chunks of keyspace to
> search. That is, they are not coordinating with others to avoid
> duplication.
> 
> -- By the time the total amount of computons expended has equalled the
> amount that would have been expended in a "no duplications" allocated
> search, the Poisson probability distribution says that 1/e = 36.8% of the
> keyspace will not have been searched; the rest of the probabilty lies in
> keyspace searched once, twice, three times, etc.
> 
> -- 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.

Interesting.  I think the most efficient way to search the keyspace would be
combine both methods of distributed cracking.  Each person would choose a
chunk of keyspace and brute-force all the keys within that space.  Then, the
user would send a PGP-signed message to some centralized database that says
what keyspace was brute-forced.  The UserID and fingerprint of each user would
be made available along with the keyspace each user claims to have searched.
This way, reputations could be used to establish which keyspaces should be
double-checked and which ones shouldn't.  This would allow for more "weighted"
probabalistic assignment.  The number of computons that would be used to crack
the keyspace would be somewhere in between centralized and probabalistic
assignment.

- -- Mark

PGP encrypted mail prefered
Key fingerprint = d61734f2800486ae6f79bfeb70f95348
http://www.voicenet.com/~markm/  


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv

iQCVAwUBMfWN6rZc+sv5siulAQHTfgQAkiopcwtuufvNOnit7peOj4PS33M+T68W
VQcaeW2drqlTHXBlfLEn3uAw4syWA/XkPUQhA1l46KiCnPzXa2xIFub+Uk/dRVDO
j5YRvRmrJ2Ly+BZQOvHug3pMtCtoY3QhJKIWSqGFoZj6SYL8Bgc0STBmzeKdC77O
sdyDZvh5Znk=
=Kx49
-----END PGP SIGNATURE-----