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

2. S N [r] ∈ B and index r is touched by at least one of the r − 1 many
j G values during the first r−1 rounds of the PRGA. Further, after the
swap(s), the value S N [r] remains in the set B. This will happen with
probability ( N + ǫ) 1−( N−1

N

b−1 ) r−1

N−1 .
3. S N [r] ∈ B and index r is touched by at least one of the r− 1 many j G
values during the first r− 1 rounds of the PRGA. Due to the swap(s),
the value S N [r] comes to the set B. This will happen with probability
(1− N

1−( N−1
N

N .
Adding these contributions, we get the total probability as given by δ.

) r−1

−ǫ)

b

N + 2 N ,

b

Lemma 6.2.14. If P(S r−1 [r] ∈ B) =

N + δ, then P(z r

∈ C) =

where C = {c ′ | c ′ = r−b ′ where b ′ ∈ B}, r ≥ 1.

Proof: The event (z r ∈C) can happen in two ways.

1. S r−1 [r] ∈ B and z r = r − S r−1 [r]. From Corollary 5.2.2, we have
P(z r = r−S r−1 [r]) =

2
N

for r ≥ 1. Thus, the contribution of this part

N ( N + δ).
2. S r−1 [r] ∈ B and still z r

2

is

∈ C due to random association. The contribu-
tion of this part is (1− N ) N .
Adding these two contributions, we get the result.

b

Theorem 6.2.15. If P(S N [r] ∈B) =

N + ǫ, then P(z r

∈ C)

r−1 r−1

b
N +

2
N

b
N + ǫ

N −1
N

N −1
N

= + 1−

r−1

b−1
N −1

− b
N

− b
N

N −1
N

,

where C = {c ′ | c ′ = r−b ′ where b ′ ∈ B}, r ≥ 1.

Proof: The proof immediately follows by combining Lemma 6.2.13 and
Lemma 6.2.14.
The above results imply that for a single value v, if

1
N + ǫ,

P(S N [r] = v) =

then

N + 2δ

1

N ,
where the value of δ can be computed by substituting b = 1 in Lemma 6.2.14.
This reveals a non-uniform distribution of the initial keystream output bytes
z r for small r.

P(z r = r−v) =