RC4

I've been out of e-mail range for a while, so some of sci.crypt has fallen
off the back end of my host.  And I don't read the full Cypherpunks feed.
So some of these may be dumb questions, but they're mine and I would like
them answered.

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

Has there been any reaction from anybody?  RSADS?  NSA?  NIST?  I just
sent a copy of Bidzos asking for comment.

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

Inquiring minds want to know.

Bruce

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

Since I haven't seen a statement by anyone who I would believe that
this is, in fact, RC4, I'm calling it "Alleged-RC4"..

Actually, all the %256 operations in the code are superfluous on
8-bit-byte platforms since the indices are declared as `unsigned
char'.

There are two interesting features in this alleged-RC4 which clearly
put it above the typical xor-based homebrew cypher..

 1) the "pad" is maintained as a permutation of 0..255, so the output
should always have a close-to-uniform distribution of output values.

 2) the operations which stir the "pad" all have two counters: one (x)
which increments by 1 each time, and one (t) which moves in a way
dependant on the "pad" values.  The x counter guarantees that all
bytes in the pad get shuffled with roughly equal frequency, so you're
less likely to get stuck in a shorter-length cycle.  The y counter
moves in a "chaotic" data-dependant way, and each slot in the pad
affects its stepping in turn.

Probably the only potential weakness I can see is that the `x' and `y'
counters are always initialized to zero when starting off; this means
that an attacker can almost always know the `x' value used to encrypt
each byte of cyphertext they find.  I can't see any way to exploit
this, though.  It would seem that you could (slightly) strengthen the
cipher by starting with x=state[0] and y=state[1], then cranking the
key generation loop for two more iterations..

The fact that the NSA allows export of this cipher (albeit with keys
limited to 40 bits) is interesting.. unlike DES, the alleged-RC4's key
setup does not appear to be particularly parallelizeable.  A
fully-pipelined alleged-RC4 key breaker would require 256 stages of
key setup followed by n stages of "encryption" (with ~2k bits of state
per stage).  This is significantly more complex than the 16-stage
pipeline with ~128 bits of state per stage in the pipelined
DES-breaker.

					- Bill

Another thing that is pretty obvious is that this kind of cypher is not
suitable for certain applications.  For example, if you wanted to encrypt
individually a lot of different files on your disk, all using the same
key, this kind of stream cypher would be totally unsuitable.  Any success
in guessing the plaintext which corresponds to a given cyphertext reveals
the XOR stream that the key generates, and that is the same stream that
would be XOR'd to encrypt any other file with the same key.  Doing this 
would be similar to re-using a "one time" pad for many encryptions.  This
kind of cypher is more appropriate for a communications channel where the
key is never re-used, and the two sides can keep persistent and
synchronized state.

Hal

I agree; this cypher should definitely be handed a unique key each
time it is used.

However, you can do this pretty easily for file encryption, too..
Generate and store an "initialization vector" with each file of
cyphertext.  Instead of passing the user key directly to RC4, you
instead pass a hash (MD5 or SHA) of the user key concatenated with the
IV.

If you don't have room to store the IV's, you could use some
position-dependant information (e.g., per disk ID plus disk block
number or file inode number) instead.

						- Bill