[rc5] Checking for 64 bit RC5 on the fly?

Bob Krzaczek rskpci at cis.rit.edu
Mon Jun 23 19:30:05 EDT 1997

On Mon, 23 Jun 1997, Fedor Kouranov wrote:
> On 06/23/97 Klaus Espenlaub <kespenla at hydra.informatik.uni-ulm.de> said:
> >Would it be worth the time doing another decryption and check for the
> >other pattern as well? The drawback is obvious: some loss of speed, but
> >[ ... ]
> For each 56-bit key 0xFFFFFFFFFFFFFF check a 64-bit 0x00FFFFFFFFFFFFFF?
> This will *double* the work. Hey, we want to crack it in this millenium!
> ;-)

Not necessarily :)  Just assume for the moment the expanded key table
would be the same in the above case.  Then, the decision to check both
problem spaces depends on how much of your time is spent generating the
expanded key table and how much is encrypting the block of known
plaintext.  If we were to naively assume a 50/50 split (hey, I said this
was naive), we would incur a slowdown of 50%.  No joy. 

But if we count only the computational operations present in the 12 round
algorithm (disregarding things like array lookups), we find only 80
operations in the encryption phase compared to 546 operations in the key
mixing phase.  Adding a second set of encryptions would only incur a
slowdown of only about 12%.  Joy! ;-) 

So, what about those identical expanded key tables...?

> Encrypting with a 56-bit key is *not* the same as with a (similar) 64-bit
> key.

Don't be so hasty... in certain circumstances, encrypting via RC5 with a
56 bit key *is* the same as encrypting with a 64 bit key, provided the
other RC5 parameters (word size and number of rounds) are unchanged.  The
resulting expanded key table would be the same. 

In other words, in certain cases, RC5 does encrypt identically with
slightly different size secret keys.  At first, I doubted this myself,
assuming that I had obviously missed something.  Even after I re-examined
the algorithm and it seemed true, I still wasn't sold on it.  So, I edited
some noweb files I had lying around from a recent implementation of RC5
;-), recompiled, and... sure enough, the results matched.

The reason?  It's so obvious, though, that you might miss it like I did at

(Since I don't have the richness of different fonts and faces in this
message, I'm going to use different names for various RC5 parameters than
what Rivest uses in his paper.  Sorry.) 

Consider a 56 bit key (K): it requires seven bytes of storage. Klen = 7. 

Before a secret key is ``mixed'' in to the expanded key table (S), it is
restructured into an array (L) of register-sized words just large enough
to hold it.  The length of that array is ( Klen+3 )/4 words, or 2 in the
case for Klen = 7. Before the bytes of the secret key are copied in, all
elements of L are initialized to zero. 

That is the only explicit reference to Klen.  The rest of the key mixing
algorithm uses the lengths of S and L.  The length of S is based solely on
the number of rounds implemented.  The length of L (Llen) varies only as K
grows by increments of 4 (given 32 bit words and 8 bit bytes).  For Klen =
{ 1, 2, 3, 4 }, Llen = 1. For Klen = { 5, 6, 7, 8 }, Llen = 2.  And so on. 

If K was a 64 bit key, Klen would be 8 and Llen would still be 2. 

Notice that the unused bytes in the last word of array L were explicitly
initialized to zero.  This is equivalent to a key of greater length with a
value of 0x00 in those ``extra'' bytes. 

Again, nowhere else in the RC5 key expansion, encryption, or decryption
algorithms does the exact length of the user's secret key (Klen) appear. 

If you increment Klen enough that the size of L increases, *then* you will
see a difference in the action of the underlying algorithms.  In
particular, during the key expansion phase, computations modulo Llen will
be different.  But again, this only affects the generation of S; the
encryption and decryption phases will operate identically. 

So, in *general*, encryptions with different lengths keys are not
necessarily the same.

But, in certain special cases (and 56 vs. 64 bit encryption is one of
these cases), identical encryptions can occur with two different length
keys, if and only
	1) both keys result in the same length of the word array L, and
	2) all the bytes in the shorter key appear in the same position
	   and with the same value in the larger key, and
	3) the extra bytes in the longer key all have a value of 0. 

Finally, if you want to see the effects yourself, encrypt something using
a 5 byte key such as [[01 23 45 67 89]].  The encrypt it again with the 8
byte key [[01 23 45 67 89 00 00 00]].  Compare the results. 

That's a lot of ``ifs'', but it's possible.  It's worth noting when you're
considering brute force attacks against ciphers of unknowable key lengths. 
But, in the long run, is the knowledge useful?  Doubtful.  It's trivial to
avoid null bytes in the most significant locations of a user key.  (And I
also note that none of the RSA practice contests have any keys with a null
byte in them). 

Anyway, I fully admit that the entire preceding message may be completely
wrong; after all, I'm just an amateur.  But, after studying the algorithm
recently, and writing some test cases, it certainly seems like this is the
case.  Please, if someone knows differently, educate me! 

// bob

// Bob Krzaczek                              <http://www.cis.rit.edu/~rskpci/>
// Center for Imaging Science, RIT                        <rskpci at cis.rit.edu>

To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.

More information about the rc5 mailing list