[HARDWARE] ongoing work

Mel Tsai tsaimelv at pilot.msu.edu
Wed Apr 28 02:15:16 EDT 1999


>>On Tue, 27 Apr 1999, Matthew Smart wrote:
>>
>>> But RC5 is a symmetric algorithm, so decrypting is just as easy as
>>> encrypting.  And you only need to decrypt/encrypt the first block (64 bits)
>>> and compare it against the ASCII representation of "The ", which is the
>>> first part of "The unknown message is: ".
>>> 
>>> So encrypting "The " and comparing against the given cyphertext should be
>>> the same as decrypting the first block of the cyphertext and comparing
>>> against "The ".
>
>An idea.. (from a complete novice in cryptography)
>
>There appears to be 15 known characters at the start of the "hidden message"
>t,h,e,u,n,k,o,w,m,s,a,g,i,: and space. with multiples of some.
>
>Statistically which are the least common of these characters in the English
>language? What if a search was mounted for a pattern matching least common
>part of the "known" message.
>
>Is this what bovine is doing or would this possibly work? "The" seems
>awfully common to search for.

RC5 is an 8-byte block cyper...  Since the message is more than 8
bytes, you don't need to check for anything other than the first 8
bytes in a brute-force attack.  The most computationally "efficient"
brute-force method is to decrypt the first 8 bytes of the cypertext
and see if it matches.  If it does, the client will then test (using
the same key) the rest of the message, checking for a match.  

Statistically there can be many hundreds (?) of matches for the first
8 bytes of the message among the 2^64 keys in the keyspace, so I
believe the bovine client simply flags one of the keyservers when it
has hit a potential match (i.e. it matches the first 8 bytes), then
the keyserver checks the rest of the message (not sure about this
though).  Note that 8 bytes is the *minimum* testable block in RC5,
you can't test smaller chunks.

Another important point is to realize how the RC5 decryption process
works...  The algorithm takes the 64 bit key (hence "RC5-64") and
performs a series of rotates and additions on this key to generate 26
"sub keys."  The algorithm will then take these subkeys and perform
some simple operations on the cypertext to generate the original
message.  So, you actually aren't saving a whole lot of time by only
checking for the first 8 bytes of the message, because the creation of
the subkeys is the most CPU intensive step in the decryption.  Once
you get the subkeys, decrypting is "easy."  But I imagine checking the
first 8 bytes increases your efficiency by 25 or 30%, depending on how
the client is optimized.

At one point I had an RC5-64 hardware decryption engine kinda working
in the simulator (the target hardware was a Xilinx Spartan FPGA), but
I got bored and never finished :).

-Mel
--
To unsubscribe, send 'unsubscribe hardware' to majordomo at lists.distributed.net



More information about the Hardware mailing list