[RC5] My contribution to RC5

gindrup at okway.okstate.edu gindrup at okway.okstate.edu
Fri Apr 3 14:27:22 EST 1998


     It is not unreasonable to assume that a concerted "real" crack 
     against a ciphertext has the following information about the 
     plaintext:
     1) What cipher was used to encrypt
     2) What the keylength is
     3) What headers were used to encode (wrapped) the plaintext
     4) Who sent it
     5) Who was to receive it
     6) What (classification, not detail) the message contains
     
     For most real communication, the important one of those is 3.  Since 
     most headers have a well-defined format, non-compliant trial 
     ciphertexts generated in brute-force decryption efforts indicate a 
     failed attempt.  4 and 5 can also help you narrow down the legal 
     character set for the plaintext.  6 gives keywords to search for in 
     the trial plaintext.
     
     Thus, 1 and 2 permit a brute-force attempt.  3 permits one to do 
     one-block decrypts that eliminate most trial plaintexts.  4, 5, and 
     6 can do "sanity checks" on the bytestream contained in the trial 
     ciphertext.  The result is that *very* few trial plaintexts fall 
     through the automated procedure and so require human inspection.
     
     Declassified material on the attempt to cryptanalyze Enigma during 
     WWII indicate that 3 through 6 were used in automated tools to 
     attempt decrypts and the few remaining "sane" trial plaintexts were 
     multiplexed to small armies of humans to categorize as "keep" or 
     "toss."
     
     This still applies to decryption attempts against encrypted data 
     today.  All the known prefix is giving us is the "well-known header" 
     that normal transmitted data would have, e.g. IP and TCP headers.
     
     Let's say we didn't know what it was, but we knew the plaintext was 
     ASCII (which means it's 7-bit clean).  This means that there are 8 
     bits in the first (64-bit) block that must be 0 (the MSb in each 
     byte).  Only one decrypted block in 256 will have this property.  
     Similarly, of the keys that "sanely" decrypt the first block, only 1 
     in 256 will sanely decrypt the second block.  After 8 blocks, the 
     likelihood that the so-far-successful key is the correct key is the 
     same as what we have now with "probable" keys: 2^64 - 1 in 2^64.
     
     We can compute the amount of effort for this attack as follows:
     255/256 of the time a trial key is defeated in the first block.
     of the 1/256 of the keys that are left,
        255/256 of the keys are defeated in the second block
        of the 1/256 of those keys that are left...
     So, we want the sum of
               255/256 * 1 +  //most keys take one decrypt to toss
       1/256 * 255/256 * 2 +  //most that are left require one more
      1/2^16 * 255/256 * 3 +  //ditto
      1/2^24 * 255/256 * 4 + ...
      1/2^72 * 255/256 * 8
     ~= 1.004
     
     This means that one has to do about 1.004 trial decrypts per key to 
     use this decryption method to achieve the same amount of "thinning" 
     of the keyspace as the current method, 1 trial decrypts per key, 
     where we know the first block of plaintext.
     
     Therefore, knowing the form of the header but not its content does 
     not terribly increase the amount of effort expended in the cracking 
     process.
            -- Eric Gindrup ! gindrup at Okway.okstate.edu


______________________________ Reply Separator _________________________________
Subject: Re: [RC5] My contribution to RC5 
Author:  <rc5 at llamas.net> at SMTP
Date:    3/31/98 11:45 PM


     [snip]
Another thing to think about is we have a distinct advantage over a hacker... 
We know what the first few bytes of the message is...
     [snip]
Until soon...
Ed Wensell III
Systems and Operations Support, Pellissippi State 
http://www.pstcc.cc.tn.us/departments/sos
     [snip]

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