# RC4 S-Box and Keystream

I'm studying the RC4 algorithm and I have the following questions:

On all questions assume that an expanded (2048-bit) key is used, and that the first 4096 bytes of the KeystreamIm are discarded.

After the above process, is the resulting S-box indistinguishable from a random permutation of the numbers 0 through 255?

Assuming the above process, are the bytes generated indistinguishable from random data?

-

As for your first question "is the S-box indistinguishable from a random permutation?", well, there are likely some subtle biases. For one, we know that, after exactly 4096 steps, the combination $j=1$ and $SBox[1] = 1$ is impossible; that's because $i=0$ after 4096 steps, and the combination $j=i+1$ and $SBox[j]=1$ is known to be impossible (given the standard RC4 key setup; this was first observed by Hal Finney). Because of this, there is likely a bias away from $SBox[1] = 1$ after exactly 4096 steps, and so this would appear likely to be a distinguisher (albeit not a strong one) from a random permutation.

As for your second question "are the bytes generated indistinguishable from random data?", the answer for that is "definitely not". We know how to distinguish a roughly Gigabyte output of RC4 from a random stream; see this paper for the details; note that discarding an arbitrary amount of RC4 keystream before you start sampling does not affect this attack.

-
Thanks, might I ask, how many steps must be used such that the s-box is indistinguishable from a random permutation? Also, on the second point, is it correct to assume that the Keystream cannot be successfully predicted even though it is distinguishable? – Devros Exrix Jul 15 '12 at 22:15
@DevrosExrix: as for how many steps it would take before the permutation becomes indistinguishable, well, the above logic would appear to hold for any finite number of steps. As for predicting keystream, the best the paper gives us is that occasionally there are places where the next byte can be predicted with probability $2^{-8} + 2^{-15}$ (as opposed to $2^{-8}$ for a truly random stream) – poncho Jul 15 '12 at 23:32
i wonder if it is correct to call RC4's S S-box, technically.. – mykhal Feb 19 '15 at 17:26
The "S" box in RC4 is known to be a permutation box. – Iam Nick Feb 12 at 15:54