Re: RC4

[Hal <hfinney@shell.portal.com>]

schneier@chinet.chinet.com (Bruce Schneier) writes:

>Does anyone know if this is really RC4?  Has anyone compiled it to see
>if it will run?  Has anyone tried to use it to decrypt messages encrypted
>with some commercial RC4 program?

I thought this posting was very interesting.  RC4, as I understand it,
is a secret-key algorithm from RSADSI which has been kept secret.  I have
no information about RC4 so I can't judge whether this is really it.

A couple of comments, though.  First, there was one obvious typo:

          xorIndex = state[x] + (state[y]) % 256;

should clearly be

          xorIndex = (state[x] + state[y]) % 256;

The second thing I notice is, this is a surprisingly simple algorithm.
I say "surprising" for a couple of reasons.  First, it seems like this
algorithm would not have been difficult to deduce from disassembled
object code.  Of course, maybe that is where it came from.  But it has
been around for a number of years without this being published before.

Also, this algorithm is not too different from some "naive" algorithms
that get posted on sci.crypt from time to time.  It basically makes a
random (key-based) permutation of 0..255, then indexes into that table
a couple of times, adds the results, and uses that as the final index,
xor'ing the result with the plaintext.  It gets complicated by a simple
swap of the two index values, and the choice of the initial indexes is
a matter of stepping; one steps by one and the other steps by the table
value of the first index.

Despite the simplicity, there are no obvious (to me) attacks.  The one
thing that I notice is that with known plaintext you can recover the
table lookup values which are being xor'd.  If you can find two identical
xor values which are pretty close together, chances are the underlying
final index (the sum of the two lookup values) is the same.  But since
it is a sum there are still a wide range of possible values which made
up the sum.  It's just really hard to pin things down.  Without the swap
you could probably do it with enough text, but that swap is constantly
stirring the table at a low level, so by the time you had enough data to
try to get a handle on the table structure, the table has changed.  It's
pretty clever.

This raises the question about why it is secret.  It is (hopefully!) not
because the algorithm is weak when exposed.  Presumably it is a matter
of trade secrecy.  Now that the algorithm is exposed (assuming this is the
real thing) then this is an apparently unpatented secret-key cypher.  Would
it be possible for them to have a "backup" patent application that they
could push through now?  I recall some claims of a similar strategy with
respect to Clipper.

>I see that it has been posted anonymously.  Was it posted to Cypherpunks
>only, or did it also get on sci.crypt?  If not, did someone from
>Cypherpunks, anonymously or not, crosspost it to sci.crypt?

I haven't seen it anywhere but here.  We could probably get a lot more
informed comment on sci.crypt.  Maybe it will show up there eventually.

>This seems to be a REALLY GOOD THING, but I would like some verification
>that it is not a hoax.

Yes, it will be interesting to see what comes of it.

Hal Finney