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
participants (3)
-
Bill Sommerfeld -
Hal -
schneier＠chinet.chinet.com