[rc5] Question for beginner

Bob Krzaczek rskpci at cis.rit.edu
Mon Oct 27 19:59:16 EST 1997

You know, sometimes I wonder... perhaps I should have pressed my point
harder back in June about searching the first 256th of the 64 bit keyspace
while we were searching the 56 bit keyspace. 

The point was that RC5 uses an identical expanded key table for every four
bytes of key length.  That is, a 56 bit key and a 64 bit key will possess
the exact same expanded key table *iff* the most significant byte of the
64 bit key is 0x00.  And likewise, if the top two bytes of a 64 bit key
are zero, the key is identical in function to a 48 bit key.  (Of course,
this all assumes the same word size and number of rounds between
implementations of RC5). 

Not a huge deal, really (at best, you might say that RC5 has some
"semi-semi-weak keys", since RC5 is not a single algorithm but a family of
algorithms, and these tables are only similar *among* algorithms, not
*within* a single algorithm).  Besides, from a security point of view,
they're trivially easy to avoid (much like DES weak and semi weak keys
are) if it really annoys you.

The kicker is that, when encrypting with RC5-32/12/7 (for example), it
takes 546 operations to set up the expanded key table, and only 80
operations actually encrypting the first block of plaintext.  We could
have searched the first 1/256th of RC5-32/12/8 with only a 12-13% hit to
our performance in RC5-32/12/7. 

Ah well.  Perhaps it was better that the Bovine people stayed focused on
only 56 bit encryption; a rough guesstimate translates that to nearly an
extra month of computation if we *had* gotten saucy and tried to get a
headstart on the 64 bit keyspace while still searching for the 56 bit key.
(Then again, it was pointed out that distributed.net's computing power was
still increasing when the key was found, so perhaps it would have taken
less than an extra month? How much less?)

This is mostly academic, I guess; the trick doesn't extend past four byte
increments of the keylength.  Therefore, even if we found RC5-32/12/8
tomorrow, and we had doubled our computing power in the meantime, and we
were insane, and we went after RC5-32/12/9, nothing we do with RC5-32/12/8
would apply, no matter what we did right now.  :-) 

See <http://cwww.llamas.net/~chipper/hypermail/rc5.Jun1997/0775.html> for

// bob

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

On Mon, 27 Oct 1997, Eric Gindrup wrote:

;      Th ratio of the o() (not O()) leading coefficient for the RC5-56 
;      client to the RC5-64 client.  I.e.  the work to do an old 56-bit key 
;      is about 7/8 the work to do a new key, so 7/8 of the old utility 
;      transforms to new utility when the units are held fixed at keys per 
;      second.
;             -- Eric Gindrup ! gindrup at Okway.okstate.edu

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

More information about the rc5 mailing list