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)
Lines: 131
Message-ID: <xdIqw-j.jmkelsey@delphi.com>
References: <4ek273$rbv@blackice.winternet.com> <DLzMBK.6uH@cix.compulink.co.uk>
NNTP-Posting-Host: bos1b.delphi.com
X-To: "Stephen Kapp" <skapp@cix.compulink.co.uk>

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