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. $
participants (3)
-
Mark M. -
mpd＠netcom.com -
tcmay＠got.net