Is the RC4 keystream random or not?

Question

I have cause to use the PRNG half of RC4, but am seriously confused as to the randomness of its output. (Only the PRNG half.)

On the one hand, there is a large body of literature finding ever greater biases in RC4's keystream. It appears that both weak and strong distinguishers can identify RC4 from a truly random sequence. These analyses are performed by clever people.

On the other hand, an RC4 keystream passes most accepted randomness testing suites. I've personally run the Dieharder tests against a 100 GB file of output and it passed. These test suites are designed to identify biases in allegedly random bit sequences and are written by clever people.

Can anyone square this circle?

EDIT:

Having reviewed the answers/comments, I'm minded to believe that the PRNG portion of the RC4 algorithm is better than it appears initially from cursory inspection. In saying this, I'm excluding the so called key scheduling algorithm which clearly is quite broken. I would make the following observations:

• The fact remains that a singular keystream passes the best statistical tests for randomness. This cannot be ignored. If there was significant deviation from randomness, of any type, standard testing would discover it. The only hypothesis that matches the evidence is that long term bias is within typically acceptable levels.
• The below referenced paper accepts that major statistical biases occur only within the first 512 bytes of the keystream, and are fully attributable to the key scheduling algorithm/key length.
• Long term biases are 500 times lower than the initial ones, and the authors highlight the uncertainty with which long term biases were determined, with $2^{-16}$ biases difficult to fully assess or categorise.
• The decimal expansion of pi shows similar magnitude biases (10e-6) even out to 2 trillion digits — that's the nature of randomness.
• If the same degree of extensive scrutiny were applied to other PRNGs, would they too show similar biases?

In summary, it appears to me that with a fully randomised and manually injected state array (thus bypassing the inherent key scheduling component), RC4 is a good PRNG.

Answer 1

Like fkraiem's answer points out, passing a statistical test does not prove a PRNG is cryptographically random, or even statistically random with regard to other tests.

In the case of RC4 the biases are most prominent in the beginning of the keystream. To borrow a useful illustration from Vanhoef and Piessens' "All Your Biases Belong To Us: Breaking RC4 in WPA-TKIP and TLS" (pdf, page 6), dubbed the RC4 NOMORE attack:

The biases will require more and more samples to detect, the further along the keystream you are. To explain your findings:

On the other hand, an RC4 keystream passes most accepted randomness testing suites. I've personally run the Dieharder tests against a 100 GB file of output and it passed.

If you did that by using a single RC4 keystream of that size, only the beginning would likely have detectable biases. By generating billions of short keystreams instead, you might be able to detect biases using even some generic statistical test (or you might not, depends on what exactly is tested).

(Additionally, it is common practice to drop the initial keystream to get rid of the largest biases that were found in earlier cryptanalyses. If your RC4 already does this, that may help hide the biases from a statistical test. Not because they do not exist in the trimmed output, but because they require even more data to see.)

The reason these biases may be hard to detect generically is that they are specific relations between particular bytes of the keystream (see section 2.3.3 in the linked paper) and testing for all such equalities would impossibly time-consuming. Adding a specific test for those biases to a suite, on the other hand, would only help you prove that the input is RC4 (known broken) – other inputs would be unlikely to have those exact biases.

Answer 2

Statistical tests have no value to evaluate randomness in a cryptographic sense, because an attacker is not required to use any specific test. The fact that a stream passes some set of predetermined tests tells you nothing about how it fares against tests which are not in the set.