Technical comments on RC2 from John Kelsey

["baldwin" <baldwin@RSA.COM (Robert W. Baldwin)>]

        Here are some interesting technical comments on RC2 from
sci.crypt.  If you already read sci.crypt, delete this now and
accept my apologies for wasting your time.
                --Bob


______________________________ Forward Header __________________________________
From: John Kelsey <jmkelsey@delphi.com> 
Newsgroups: sci.crypt
Subject: Re: RC2 source code
Date: Tue, 30 Jan 96 10:20:43 -0500
Organization: Delphi (info@delphi.com email, 800-695-4005 voice) 

-----BEGIN PGP SIGNED MESSAGE-----

[ To: sci.crypt ## Date: 01/29/96 09:18 pm ##
  Subject: RC2 source code ]

>From: anon-remailer@utopia.hacktic.nl (Anonymous) 
>Newsgroups: sci.crypt
>Subject: RC2 source code
>Date: 29 Jan 1996 06:38:04 +0100

This was interesting.  Is this another "S1," or another 
"alleged-RC4?"  The whole thing looks pretty believeable, i.e., it 
doesn't have any obviously dumb parts that I can see.

Note that alleged RC2's block encryption function looks an awful lot 
like one round of MD5 performed on 16-bit sub-blocks, using the 
bitwise selection function as the nonlinear function, and a 
key-derived constant table.  Additionally, in rounds four and eleven, 
there are four lookups into the expanded key array.

The encryption function could be rewritten as

for(i=0;i<16;i++){
     a = rotl(a + bsel(d,c,b) + *sk++, 1); 
     b = rotl(b + bsel(a,d,c) + *sk++, 2); 
     c = rotl(c + bsel(d,c,b) + *sk++, 3); 
     d = rolt(d + bsel(c,b,a) + *sk++, 5);

     if((i==4)||(i==11)){
          a += xk[d&0x3f];
          b += xk[a&0x3f];
          c += xk[b&0x3f];
          d += xk[c&0x3f];
     }
}

If this is accurate, it may give us some insight into Rivest's 
development of MD4 and MD5, which were radically different than MD2. 
What are the dates on this?  Did Rivest do MD4 or RC2 first?  This 
may be the first block cipher in the commercial/academic world to 
use a UFN structure.  One interesting part of this is the use of the 
subkey array as an S-box twice during the encryption process.  I'm 
curious as to why this would be used only twice, rather than each 
round, i.e.

a += bsel(b,c,d) + *sk++ + s[d&0x3f];

Sticking a very different internal transformation in may have been 
an attempt to make iterative (i.e., differential) attacks harder, 
since there's no longer a single round function through which you 
can pass differential characteristics.  This depends upon when RC2 
was developed and released.

Note that the claim that "RC2 is not an iterative block cipher" 
seems to be based on the fact that it has two instances where a 
different round function is thrown in.  (Essentially, it's actually 
an 18-round cipher with two different round functions, one of which 
is used only twice.)  This other round function isn't very 
impressive, since it uses only six bits of the source block to 
affect the target block.

A one-bit change in a randomly-distributed input block looks
look like it will propogate pretty quickly:  There's a roughly 0.5 
probability that it doesn't make it through the bsel function.  If 
it does, then there's about a 0.5 probability that it will cause a 
change in the carry bit.  This happens four times per "round," so a 
one-bit change should have about a 2^{-8} chance to make it through 
one round as a one-bit change, and so about a 2^{-128} chance to 
make it through all sixteen rounds, assuming no impact from either 
of the two S-box lookups. Does this look right, or am I missing 
something?  (This is a first approximation--if our bit is in the 
high-order position anywhere, then it *can't* cause a carry bit, but 
there's no obvious way to keep it there for long.)  By choosing the 
input block, I can ensure that one-bit XOR difference makes it 
through the first step or two, but that doesn't do too much for an 
actual attack.

Other XOR differences can help with the first round or so, but stop 
being helpful afterward.  It generally looks hard to prevent 
diffusion by choosing other values, at least using XOR differences, 
because each subblock is rotated a different amount in each round. 
(The bits don't keep lining up.)

We can also try to do a differential attack based on subtraction 
modulo 2^16, based partially on Tom Berson's attempt to 
differentially attack MD5 using subtraction modulo 2^32.  This gets 
complicated because of the rotations and the bit selection 
operations, but it ought to be tried if it hasn't already.

The key scheduling is also interesting, and somewhat reminiscent of 
MD2's internal operations.  Each expanded key byte after the first N 
(where N is the number of bytes in the user's key) is determined by 
two bytes--the previous expanded key byte, and the expanded key byte 
N positions back.  This means that we probably don't get ideal 
mixing of the key bytes in the early expanded key bytes, but it 
isn't clear to me that there will be a lot of problems with 
reasonable key lengths.  (Note that a reasonable key length would be 
128 bits=16 bytes, and that it should come from the output of a good 
one-way hash function.)  I wouldn't recommend using the key schedule 
to hash passphrases, since long passphrases would leave us with many 
very low-entropy subkey values.  In general, I think that really 
large user keys will leave us vulnerable to a variety of related-key 
attacks and other nasty stuff.  I'm a little curious as to the 
purpose of phase 2 of the key schedule, but since it's only used 
when a watered-down version of the algorithm is wanted (right?), I 
haven't spent much time looking at it.

Does alleged RC2's key schedule use the same permutation table as 
MD2 does?  For small systems, this might have been a reasonably nice 
space savings.  (On the other hand, if you have a hash function 
available at the same time, it makes sense to go ahead and use it in 
your key schedule, which isn't done here.)

The algorithm looks like it will have reasonable performance on 
16-bit machines like the 8086, which was almost certainly one of the 
requirements for the algorithm, given the times it was used.

Comments?

   --John Kelsey, jmkelsey@delphi.com / kelsey@counterpane.com
 PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMQ43Q0Hx57Ag8goBAQG0LQQAiohrNSPvKzSIJjMeWjrK/r7HZOWp0Mhg 
zcq60rIyPMpsDnxuk7VlLrU2XBy0Aff4QpO8jORS3VFKtaLH5XJehc7WTZF+1En1 
ux4prro+Gpvn99HToTqKa6igxlEGYShskoF/aBIkszZAg6m/P92BPyZ/PW3tnMtp 
MoMcdNGcO0I=
=ttGl
-----END PGP SIGNATURE-----