Re: thoughts on RC4

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

perry@imsi.com (Perry E. Metzger) writes:

>Unlike most ciphers, RC4 doesn't seem to have any particular word
>length dependancies in its principles. That is to say, a cipher like
>IDEA has lots of magic numbers involved, but RC4 does not, which means
>that one could, in principle, extend it from being byte oriented
>stream to being word oriented stream without causing particular
>harm. (It would, of course, become incompatible, but thats not a real
>issue.) Can anyone see any reason why one could not change RC4 tO
>being a word oriented stream cipher, call it "ERC4"?

I'm not sure exactly how you would generalize it.  Right now it has a 256
entry table which holds a permutation of the values in 0..255.  A byte is
selected from this table and xor'd with the data stream.  To increase to
four bytes per entry and keep it as a permutation we would have to have 4
billion entries taking up 16 GB of memory which seems a bit much.
Altenatively we could still have 256 entries but have them four bytes
each, but then it's not clear that you keep the cryptographic properties
since you no longer have a permutation.

However a good application of Perry's suggestion would be to go to a
two-byte formulation.  You would have 64K entries of two bytes each,
holding a permutation of 0..65535, and then use the same algorithm with
the 256's replaced by 65536 and the chars replaced by shorts.  This would
retain the cryptographic properties and IMO would make many sorts of
attacks harder (at least requiring more data, probably by a factor of
256).  The main down side is that key setup takes 256 times longer, but
it shouldn't take much time to init a 64K entry table with a couple of
indexes and xor's per entry.  So on the whole it seems like a worthwhile
extension.

I wonder if the NSA would approve it?  I think it was Bill Sommerfield
who pointed out that it was a little curious that NSA approves RC4 with a
40 bit key when hardware-assisted search like the DES key cracker would
appear to be impractical.  Maybe some other parallel machine would be
suitable, though.  (But another possibility is that they can break the
cypher and the key length restriction is just cover for that.)

Trying to get a 16-bit RC4 approved for export would perhaps not work
for 40 bit keys because key setup takes 256 times longer, but key size
could be decreased to 32 bits to compensate.  OTOH maybe that is not
necessary because probably the whole array does not have to be set up
in order to tell whether a given key will work.  1/3 of the entries in
the table are fixed once they have been swapped once, so if you checked
after doing the first 20 entries, say, about 7 should have their final
values, and we can perhaps reject a key already in a known plaintext
situation just from that.  So actually the large table size may not
help against exhaustive key search.  (The mod I suggested to the key
setup would defend against this possibility, which raises the question
of whether this design aspect was chosen to allow for export approval.)

Hal

Hal