2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Devros Exrix
    Jul 15, 2012 at 22:15
  • $\begingroup$ @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) $\endgroup$
    – poncho
    Jul 15, 2012 at 23:32
  • $\begingroup$ i wonder if it is correct to call RC4's S S-box, technically.. $\endgroup$
    – mykhal
    Feb 19, 2015 at 17:26
  • $\begingroup$ The "S" box in RC4 is known to be a permutation box. $\endgroup$
    – Iam Nick
    Feb 12, 2016 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.