RC4 is a stream cipher designed by Ron Rivest (the R in RSA). Compared to a block cipher like AES, it's really simple. All it does is maintain a permutation of all 256 possible bytes that is updated for each output byte. RC4 *used to* be popular, but is no longer considered secure for reasons you will soon see. First I will go on detour to explain what PRG security even means.

In order for a pseudo random generator to be considered secure, its output must be indistinguishable from a "real" random process such as flipping a fair coin. Because PRGs have finite state, some states must eventually repeat (pigeonhole principle). Once the PRG has been in the same state twice, all future output will follow a period pattern because PRGs are deterministic. For this reason, no PRG can even be completely indistinguishable from "real" randomness.

Luckily, "eventually" is a really long time for any halfway decent random number generator. For example: the Mersenne Twister has a period of 2^{19937} - 1^{[1]}. Even 2^{64} output bytes is overkill for a typical application such as encrypting a TLS connection (streaming a movie from Netflix requires ~1GB of bandwidth).

PRG output cannot be and does not need to be absolutely indistinguishable from "true" randomness. What we need is indistinguishablilty from the perspective of any adversary who sees "plausible" amounts of output and has "plausible" computing power. Sadly, RC4 does not fit the bill. The reason is the first bytes of RC4 output are biased (ie: the probability distribution of possible values is no uniform). Specifically, the second byte of output is 0 with probability 1/128 instead of 1/256^{[2]}.

The simulation runs RC4 with different keys and tallies up the frequency of various values of the second output byte. Here is the probability distribution derived from the simulation output:

It turns out more of the early output bytes are biased. One remediation is to discard the first 256 output bytes. The best remediation is to use something else (Salsa or ChaCha anyone?). The example of RC4 shows that running even simple statistical tests to evaluate PRG output is a good idea. This is what Ron Rivest did when designing the newish stream cipher Spritz^{[3]}. Also check out Dieharder with is a series of tests for random number generators.

- [1] Mersenne Twister
- [2] Wikipedia - RC4
- [3] Spritz - a spongy RC4-like stream cipher and hash function
- Full sample code (rc4_bias_demo.cpp)

Written by Adrian Stoll on 29 Apr 2017