Re: DES-Busting Screen Savers?

At 5:02 PM 7/23/96, Lucky Green wrote:
>At 15:53 7/23/96, Timothy C. May wrote:
>
>>Or several times that number of machines or time for machines with less
>>crunch. Say, 100K Pentium-type machines for a month or two. How might this
>>be gotten?
>>
>>A while back I proposed one approach: a brute force "screen saver" for
>>Windows machines. Other platforms, maybe, but the most cost-effective thing
>>to do is to go after the Windows market only.
>
>A friend of mine actually wrote an RC4-40 cracking screen saver during the
>initial RC4 crack. We finished the brute force so quickly that he never
>released the software.
>

Too bad. Properly modularized software, i.e., with a place to drop in the
specific system/algorithm being attacked, could be adapted quickly to
DES-busting, or whatever.

If your friend still has this, and it's not just spaghetti code, maybe he
can adapt it to a truly large-scale attack.

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.


--Tim May

Boycott "Big Brother Inside" software!
We got computers, we're tapping phone lines, we 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,
Licensed Ontologist         | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."

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

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