Distinguishing Attacks - RC4: Stream Cipher and Its Variants - page 173

• Each RC4 period starts with i 1 = 1 now.
• First period of RC4 has j 0 = 0 to start with.

• This will be repeated if j 0 mod N = 0 in any period. And if so, the new
period will be identical to the initial period of RC4, in terms of the
statistical behavior of the permutation and the keystream.

Recall that the biases in z 1 = 0 and z 2 = 0 did not depend on KSA.
Rather, they both depended on i 0 = 0 and j 0 = 0. So a natural question is
whether z ρN+1 = 0 and z ρN+2 = 0 are biased as well, for integer ρ ≥ 1.
Note that the event (j ρN = 0), for any integer ρ ≥ 1, can be safely assumed
to be random and hence happens with probability

1

N . Theorem 6.2.2 directly

implies

1
N

− 1 P(z ρN+1 = 0 | j ρN = 0) =

N 2 .

When j ρN

= 0, it is assumed that the event z ρN+1 = 0 happens due to random
association. Thus, one gets

P(z ρN+1 = 0)
= P(j ρN = 0)P(z ρN+1 = 0 | j ρN = 0)
+P(j ρN = 0)P(z ρN+1 = 0 | j ρN = 0)

≈ 1
N

1
N

− 1
N 2

1− 1
N

1
N

+

1
N

− 1

N 3 .
This bias gives rise to a very weak distinguisher and hence is not so interesting.
On the other hand, Theorem 6.2.3 implies

=

P(z ρN+2 = 0 | j ρN = 0) ≈ 2

N .

(6.6)

Lemma 6.3.5 establishes a similar result for z ρN .
Lemma 6.3.5. For any integer ρ ≥ 1, assume that the permutation S ρN is
randomly chosen from the set of all possible permutations of {0,...,N − 1}.
Then

P(z ρN = 0 | j ρN = 0) ≈ 2

N .

Proof: We have i ρN = 0. When j ρN

= 0, we have no swap in round

0 mod N and the output is

z ρN = S ρN [2S ρN [0]].

Let us consider two possible cases.

Case I: S ρN [0] = 0. Then z ρN = S ρN [0] = 0.