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