RC4 is a stream cipher that was developed by Rivest and has been widely used because of its speed and simplicity. The algorithm was originally secret, but it was leaked to the Internet in 1994 and has since been extensively analyzed. In particular, certain statistical biases were found in the keystream it generated, especially in the initial bits. Therefore, often a version called RC4-drop[n] is used, in which the first $n$ bits are dropped before starting the keystream. However, this version is still not recommended for situations requiring high security.

To start the generation of the keystream for RC4, the user chooses a key, which is a binary string between 40 and 256 bits long. This is put into the Key Scheduling Algorithm. It starts with an array $S$ consisting of the numbers from 0 to 255, regarded as 8-bit bytes, and outputs a permutation of these entries, as follows:

This algorithm starts by initializing the entries in $S$ as $S[i]=i$ for $i$ running from 0 through 255. Suppose the user-supplied key is $10100000\cdots$ (let’s say the key length is 40).

The algorithm starts with $j=0$ and $i=0$. The value of $j$ is updated to $j+S[i]+\text{key}[i\text{mod}40]=0+0+1=1$. Then $S[i]=S[0]=0$ and $S[j]=S[1]=1$ are swapped, so now $S[0]=1$ and $S[1]=0$.

We now move to $i=1$. The value $j=1$ is updated to $1+0+\text{key}[1]=1$, so $S[1]$ is swapped with itself, which means it is not changed here.

We now move to $i=2$. The value $j=1$ is updated to $1+2+\text{key}[2]=4$, so $S[2]=2$ is swapped with $S[4]=4$, yielding $S[2]=4$ and $S[4]=2$.

We now move to $i=3$. The value $j=4$ is updated to $4+3+0=7$, so $S[3]$ and $S[7]$ are swapped, yielding $S[3]=7$ and $S[7]=3$.

Let’s look at one more value of $i$, namely, $i=4$. The value $j=7$ is updated to $7+2+0=9$ (recall that $S[4]$ became 2 earlier), and we obtain $S[4]=9$ and $S[9]=2$.

This process continues through $i=255$ and yields an array $S$ of length 256 consisting of a permutation of the numbers from 0 through 255.

The array $S$ is entered into the Pseudorandom Generation Algorithm.

This algorithm runs as long as needed and each round outputs a number between 0 and 255, regarded as an 8-bit byte. This byte is XORed with the corresponding byte of the plaintext to yield the ciphertext.

Weaknesses. Generally, the keystream that is output by a stream cipher should be difficult to distinguish from a randomly generated bitstream. For example, the R Game (see Section 4.5) could be played, and the probability of winning should be negligibly larger than 1/2. For RC4, there are certain observable biases. The second byte in the output should be 0 with probability 1/256. However, Mantin and Shamir [Mantin-Shamir] showed that this byte is 0 with twice that probability. Moreover, they found that the probability that the first two bytes are simultaneously 0 is $3/{256}^2$ instead of the expected $1/{256}^2$.

Biases have also been found in the state $S$ that is output by the Key Scheduling Algorithm. For example, the probability that $S[0]=1$ is about 37% larger than the expected probability of $1/256$, while the probability that $S[0]=255$ is 26% less than expected.

Although any key length from 40 to 255 bits can be chosen, the use of small key sizes is not recommended because the algorithm can succumb to a brute force attack.