From: John Kelsey <jmkelsey@delphi.com>
Newsgroups: sci.crypt
Subject: RC2--Some very preliminary analysis
Date: Sat, 3 Feb 96 19:25:21 -0500
Organization: Delphi (info@delphi.com email, 800-695-4005 voice)
Lines: 168
Message-ID: <xPDIhyR.jmkelsey@delphi.com>
NNTP-Posting-Host: bos1e.delphi.com

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

[ To: sci.crypt, cypherpunks ## Date: 02/02/96 06:21 pm ##
  Subject:  Alleged RC2--some very preliminary analysis ]

I just wanted to post some corrected comments here, regarding
alleged-RC2.

1.   The best differential characteristic I can think of looks like
it will have a probability of 2^{-4} per round.  It's a one-round
iterative characteristic.  In my earlier post, I miscalculated this
to be 2^{-8} per round.  Sorry.

2.   Each round of RC2 represents four "steps."  This means that RC2
has 64 "steps," the same number as MD5.  (I find this interesting,
since MD5 has twice as many bits to diffuse through, and the
attacker can choose its key, but not its input block.)

3.   I don't see how to build useful linear characteristics.  Our
S-box is one bit wide.  There may be some very low-round confusion
failures, but they don't seem particularly useful here.  I'd like to
hear from anyone who can see a way to do a linear attack here.

It looks to me (though I haven't spent enough time to be certain)
that the best differential characteristics to push through the block
are going to be one-bit characteristics.  (These are certainly easy
to analyze.)

Let's throw some terminology in here:

This is one step:

A = rotl(A + f(B,C,D) + sk[i], 1);

A round is all four of these steps.  In the step above, A is the
target block (it's the one that's getting stomped by the other
values) and B, C, and D are the source block.  f(B,C,D) is the
bitwise-select function.  For each bit position i, if B_i is a one,
then f_i = C_i, otherwise f_i = D_i.

Now, when a one-bit difference is anywhere in the target block (the
block getting all the stuff added into it) except for the high bit,
its probability of not propogating to other bits in that block seems
to be about 0.5.  (This is just based on its chances of affecting
the carry into the next bit position.)  When the flipped bit is the
high-order bit of the target block, it has no chance of propogating.
When a one-bit difference is in the source block, if the rest of the
bits are approximately random, then it has a 0.5 probability of not
affecting the target block at all.  If it does affect the target
block, it has a 0.5 probability of only affecting one bit in that
block.

Note that I messed up the calculations in my earlier post on RC2 by
combining these three events in each round.  Let me try to fix that:

We flip some bit, t, making certain that if this bit doesn't
cause other bits to change, it won't ever affect the low six bits of
any block during rounds 4 and 11, when it would have a radical
effect on the encryption process.  (In other words, we choose an
input XOR delta with only bit t on.)  This bit then has the
following effect:

a.   Whenever it's in the target block, it passes through the
encryption step with probability 0.5.  (This means that changing
this bit doesn't change the carry into the next higher bit.) This
happens once per round.

b.   Whenever it's in the source block, it fails to affect the
target block with probability 0.5.  This happens three times per
round.

Note the reasons for this.  The source block affects the target
block only through this function:  ((A&B)|((~A)&C)).  This function
looks somewhat complicated, but it's really just a bitwise IF-THEN
statement:  If bit A is on, then choose bit B, otherwise choose bit
C.  Assume that A, B, and C are random.  Now, imagine flipping A.
If you were choosing bit B before, now you're choosing bit C.  Since
they're both random, half the time, B=C, so there's no change.  On
the other hand, imagine flipping bit C.  About half the time, bit A
is a one, and so C has no effect on the output.

All of this gives us a total per-round probability of 2^{-4} (NOT
2^{-8}). Getting through 14 rounds with this characteristic thus
happens with probability 2^{-56}.  *IF* single-bit characteristics
are the best ones to use, I'm doing the calculations right, and
there aren't some improvements in splitting out and dealing with
several possible characteristics in the later rounds, then it looks
to me like straight differential attacks aren't going to be too
practical against alleged RC2, though they will be possible. The
trick is going to be detecting the right pairs reliably. (This
analysis is guaranteed to be worth at least what you paid me for it.
:-) )

If this really is RC2, I suspect the number of rounds needed was
determined by imagining flipping a bit, and then seeing what the
odds were that it wouldn't flip any other bits all the way through.
My guess is that a probability of 2^{-64} of this happening was
deemed acceptably low.

That takes care of diffusion--now how about confusion?  Has anyone
looked at this cipher with regard to linear attacks?  In general, it
seems like source-heavy UFNs can often be attacked by linear
attacks.  However, it's not clear to me how to build linear
characteristics that will make it through more than a few rounds of
alleged-RC2.  Linear characteristics that are spread across many
subblocks (i.e., partly in A and partly in B) seem to get messed up
quickly by the rotations.  However, just keeping a linear
characteristic in A doesn't seem to work too well, either--if the
bits in the other blocks are random, then the bits in our
characteristic will quickly become random, as well, because the
bit-selection function has balanced outputs.  Intuitively, I think
the problem here is that we're applying a three-bit to one-bit
balanced S-box here, and each output from this S-box has at least
one different input bit.  This seems to make it really hard to find
correlations between multiple S-box output bits and their
corresponding input bits that span more than one or two rounds.
Also, we have to deal with the carry-bits from addition, which make
things significantly harder.  Am I missing something?

There are some other plaintext patterns that will make it through a
single round, but I can't see any way to exploit them for more
rounds.  Anyone want to point something out to me?

The other interesting area is the key schedule.  Recall that phase
one of the key schedule in alleged-RC2 works by filling the leftmost
k bytes with the k bytes of key, and then using a byte-wide S-box to
expand this out to 128 bytes.  Phase two then works from the
opposite direction, taking the last t bits of the expanded key
buffer, and making the entire expanded key dependent only upon those
bytes.  As someone on cypherpunks pointed out, this seems to be
meant to make it possible to use the key schedule directly on user
passphrases, and then reduce the effective key length to t bits to
meet export control requirements.

In general, I don't think it's a good idea to use that key schedule
to hash long user passphrases, because the first few subkeys wind up
with some badly skewed bits. (This may or may not translate into an
attack, but there isn't any good reason for allowing it.)  If you
had (say) a 64-byte user passphrase, this would mean that the first
four rounds' subkeys were badly skewed in this way, and the next
four rounds' subkeys were probably not all that well-mixed.  As I
said, I don't see a specific attack based on this, but it seems like
a bad idea, since I might be able to plan out (for example)
differential characteristics that took advantage of the skewed
subkey bits.

If you're using the key schedule to hash passphrases, then it's
probably better that you use phase two as well, perhaps with bits =
256 or something similar.  If you limit user passphrases to
something reasonable, such as 64 characters, then this is probably
okay.  Has anyone else looked at this?  (Naturally, it would make
more sense to just hash the passphrase intelligently, and then use
the export control hack if you had to.)

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

iQCVAwUBMRP5S0Hx57Ag8goBAQFdvwP+MzIfZ2sy7mg9YriPyXdfY4FbrMR9jACU
jatadovxaG0pXlfJHGfkFGD+3sr47ClnLWIQgK8ZuRWyVZfoD+gL5GsbkkgHF7MR
ePNPUJYyj92sgxmu1DeVEcI7u2k5096n1nagkx6EslUJ9DrzYqHLfak1ktsDHmpM
qEHboL74z5c=
=BH4l
-----END PGP SIGNATURE-----