> Unfortunately it has a rather damning effect on the cipher. > First in the key > scheduling there is a distinct possibility of keys that are > impossible. It > assumes that all K[i] are generators mod 37, so using a key > where the offset > is 0 will result in an infinite loop in the key scheduling, this is > obviously a bad design decision. Second the distinguisher > from random for > such a small RC4 state would require a relatively small known > plaintext. In > fact at that size I think there are better attacks against it than the > distinguishers known for full sized RC4. I believe it would > be achievable to > actually determine that complete state, although it would take more > significant amounts of work than would be applied to most > inmate mail (an > encrypted message would probably be simply discarded and > never delivered).
The specification for the key requires all key values to be nonzero. From the web site: "an array of key values K, where each value is a nonzero alphabetical character or its numerical equivalent" However, there was an error in the source code that allowed zeroes in the key. This has been corrected. Any zeroes in the key definition now cause the program to abort with an "invalid character" error message. Regarding the distinguisher, I don't think I understand how distinguishing the keystream from random amounts to an attack that will recover the internal state. Could you offer further clarification on that? Incidentally, for paper-and-pencil applications, I'm assuming that the message length will not exceed about 100 characters. > I don't think this reduced version of RC4 would be very suitable even > assuming a perfect delivery mechanism. I've actually > considered a similar > question before > (http://groups.google.com/groups?hl=en&th=f0d53f0eb5d7c011&see > km=9s2akd%24qk > 4%241%40nntp9.atl.mindspring.net&frame=off), I never managed to come up with > anything really suitable. I did find a solution where the inmate is given a > computer and a compiler, use RC5 to key itself (very similar to Blowfish), a > 128-bit block, and 20 rounds. Should withstand pretty much any analysis work > (except "throw it in the trash" cryptanalysis). This suffers from being > difficult to calculate with a pencil and paper, and so doesn't really fit > the requirement for a jail cell cipher. > > Using full RC4 is actually doable. Take a sheet (or multiple sheets) of > paper, create 3 sets of 0,...,255 numbers. on a large table in front of you > (or in a controlled grid) place the first 0...255 set in order, that's your > state array, the other two sets are for your i and j values. If a guard is > approaching and the data must be destroyed simply blow very hard and all the > numbers are scrambled. Of course you will probably be adding and subtracting > instead of performing XOR. This is obviously pain-staking, and slow, but it > will offer the same security as a computer running the RC4 algorithm. > Joe The problem with using full RC4 is not in the actual keystream generation, but in running the key-scheduling algorithm. Even if we only ran the KSA for one round through the permutation table, estimated time is about 50 minutes (not necessarily impractical, but making many rounds to improve security or repeated trials to improve accuracy very difficult) and the chances of performing that entire round without error for my current best estimations of accuracy are about 1 in 150,000. For the modified RC4, accuracy still isn't great, but it is good enough that careful error-checking may leave the algorithm feasible in terms of both time and accuracy. Grace & Peace, Jeremy
