# 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$ 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$ after exactly 4096 steps, and so this would appear likely to be a distinguisher (albeit not a strong one) from a random permutation.
• @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