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.