[RC5] I still dont understand

James Bliese jbliese at usa.net
Tue Dec 29 10:18:13 EST 1998


EFF's Deep Crack does indeed do a brute force attack.  As their book is in the
public domain, please read the following excerpt:

Architecture 

     The design of the EFF DES Cracker is simple in concept. It consists of an
ordinary personal computer connected
     with a large array of custom chips. Software in the personal computer
instructs the custom chips to begin
     searching, and interacts with the user. The chips run without further
help from the software until they find a
     potentially interesting key, or need to be directed to search a new part
of the key space. The software periodically
     polls the chips to find any potentially interesting keys that they have
turned up. 

     The hardware's job isn't to find the answer. but rather to eliminate most
of the answers that are incorrect.
     Software is then fast enough to search the remaining potentially-correct
keys, winnowing the false positives" from
     the real answer. The strength of the machine is that it replicates a
simple but useful search circuit thousands of
     times, allowing the software to find the answer by searching only a tiny
fraction of the key space. 

     As long as there is a small bit of software to coordinate the effort, the
problem of searching for a DES key is
     "highly parallelizable". This means the problem can be usefully solved by
many machines working in parallel,
     simultaneously. For example, a single DES-Cracker chip could find a key
by searching for many years. A
     thousand DES-Cracker chips can solve the same problem in one thousandth
of the time. A million DES-Cracker
     chips could theoretically solve the same problem in 



     1-10 

     about a millionth of the time, though the overhead of starting each chip
would become visible in the time required.
     The actual machine we built contains 1536 chips. 

     When conducting a brute-force search, the obvious thing to do is to try
every possible key, but there are some
     subtleties. You can try the keys in any order. If you think the key isn't
randomly selected, start with likely ones.
     When you finally find the right key, you can stop; you don't have to try
all the rest of the keys. You might find it in
     the first million tries; you might find it in the last million tries. On
average, you find it halfway through (after trying
     half the keys). As a result, the timings for brute-force searches are
generally given as the average time to find a
     key. The maximum time is double the average time. 

     Search units 

     The search unit is the heart of the EFF DES Cracker; it contains
thousands of them. 

     A search unit is a small piece of hardware that takes a key and two
64-bit blocks of ciphertext. It decrypts a
     block of ciphertext with the key, and checks to see if the resulting
block of plaintext is "interesting". If not, it adds
     1 to the key and repeats, searching its way through the key space. 

     If the first decryption produces an "interesting" result, the same key is
used to decrypt the second block of
     ciphertext. If both are interesting, the search unit stops and tells the
software that it has found an interesting key. If
     the second block's decryption is uninteresting, the search unit adds one
to the key and goes on searching the key
     space. 

     When a search unit stops after finding an interesting result, software on
the host computer must examine the result,
     and determine whether it's the real answer, or just a "false positive". A
false positive is a plaintext that looked
     interesting to the hardware, but which actually isn't a solution to the
problem. The hardware is designed to
     produce some proportion of false positives along with the real solution.
(The job of the hardware isn't to find the
     answer, but to eliminate the vast majority of the non-answers.) As long
as the false positives don't occur so rapidly
     that they overwhelm the software s ability to check and reject them, they
don't hurt, and they simplify the
     hardware and allow it to be more general-purpose. For the kinds of
problems that we're trying to solve, the
     hardware is designed to waste less than 1% of the search time on false
positives. 


So, you can see Deep Crack works very much the same way as we do, with the
clients performing the same duties as the custom chips.  This is why the
client doesn't alert you when it finds a possible hit, it could very well be a
dud.  The difference being, our clients only look for the text given us by RSA
labs, whereas Deep Crack will find any interesting text, making it much more
flexible as a general cracker.  But, there is no doubt about it being a brute
force attack.

James A. Bliese

Give your computer some brain-candy!
http://www.distributed.net

____________________________________________________________________
Get free e-mail and a permanent address at http://www.netaddress.com/?N=1

--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list