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

of one step in RC4 PRGA, the output after the execution is z. ψ(i G ,j G ,z)
is computed by conditioning on the values i G , j G , z, u and v in a tree-like
fashion. At the root level, we condition on i G . In the next level, given i G , we
condition on j G . Similarly, we move down the hierarchy as follows: given i G
and j G , we condition on z; given i G , j G and z, we condition on u; and finally
at the leaf level, given i G , j G , z and u, we condition on v. Given i G ,j G and z
corresponding to any internal node A of the tree, ψ(i G ,j G ,z) is calculated by
adding the contributions of each leaf of the subtree rooted at A. For example,
if at some leaf, z, u and v are all distinct and can have n z , n u and n v many
values respectively, then the contribution of that leaf toward ψ(i G ,j G ,z) is
given by

(N −3)!.
Though we need to condition on i G ,j G ,z to compute ψ(i G ,j G ,z), we involve
only z in counting the permutations, since z is generated from one of the
permutation bytes.

n z n u n v

Theorem 5.4.1. Let N be even. Then we have the following.
(1) If i G is even, then

if z = j G ,i G + 1−j G ; (N −1)!−(N −2)!

ψ(i G ,j G ,z) =

(N −1)! + 2(N −3)! otherwise.

(2) If i G is odd and j G = i G +1
2

, i G +1+N
2

, then

8
<

if z = j G ;

: 2(N −1)!−(N −2)!

ψ(i G ,j G ,z) = if z = j G + 2 ; (N −1)!−2(N −2)!

(N −1)!−(N −2)! + 2(N −3)! otherwise.

(3) If i G is odd and j G = i G +1
2

, i G +1+N
2

, then

8
<

if z = j G ,i G + 1−j G ,
i G +1
2

: (N −1)!−(N −2)! + 2(N −3)!

ψ(i G ,j G ,z) =

, i G +1+N
2

;

(N −1)! + 4(N −3)! otherwise.

See [9] for the detailed proof.

Corollary 5.4.2. Considering that the permutations appear uniformly at ran-
dom before any step of RC4 PRGA, we have the following biased probabilities.

1. P(j G = z | i G odd) ≥ N +

1

N 2 .

2. P(j G = z | i G even) ≤ N − N 2 .

3. P(j G = z | 2z = i G + 1) =

2
N

1

−

N(N−1) .

Proof: