Analysis of Keystream Generation - RC4: Stream Cipher and Its Variants - page 114

5.4.1 One Step of RC4 PRGA
Let us characterize the input-output distribution of one step RC4. The
characterization is based on determination of the number of possible configu-
rations of the internal states S G and pointers i G and j G that can yield certain
keystream bytes at a particular time step.
We present the work for the case where N is even, as RC4 in general
works for N = 256. A similar approach works for odd N, but the detailed
calculations are different, which we omit here.
Due to the non-existence of Finney cycles (discussed in Section 5.1) for the
initialization in RC4, all the permutations may not occur before each step.
In addition to the Finney states, there may exist some other (so far undis-
covered) permutations that may not occur at the beginning of each step. In
order to make things simple, one may consider that any permutation can oc-
cur before any PRGA step. The related result is presented in Theorem 5.4.1.
Subsequently, one can count the cases for the Finney cycles in Theorem 5.4.3
which should be subtracted from the cases in Theorem 5.4.1 to get a more
complicated exact formula. Further, if some other kinds of non-existing per-
mutations become identified in future, those cases may also be analyzed similar
to Theorem 5.4.3 and then can be subtracted from the cases in Theorem 5.4.1.
The Finney cycle occurs when j G = i G + 1 and S G [j G ] = 1. The number
of permutations in the Finney cycles is (N − 1)!, which is only

1

N of the
number N! of all possible RC4 permutations. Hence, excluding the Finney
states in the computations does not change the orders of the probabilities in
Corollary 5.4.2. This is also confirmed by extensive experimentation.
We only outline the basic idea behind the proofs of Theorems 5.4.1
and 5.4.3 here. For complete proofs, the readers are referred to [9]. There
does not seem to exist a shorter proof technique than a case by case analysis
of all the possibilities that have been studied in [9]. However, the end results
presented in the statements of Theorems 5.4.1 and 5.4.3 are concise and depict
the complete view of how RC4 PRGA evolves.
During a one-step update in the RC4 PRGA, i G is incremented to

i ′G = i G + 1

and j G is updated to

j ′G = j G + S G [i G + 1].
Denote u = S[i ′G ] = S G [i G + 1]

v = S G [j ′G ] = S G [j G + u].

and

Then, after the swap,

S G [j G + u] = u and S G [i G + 1] = v.

Further, the output z is given by S G [u + v].
Let ψ(i G ,j G ,z) denote the number of permutations out of all the N! per-
mutations of Z N such that with the given values of i G ,j G before the execution