Cryptography Reference
In-Depth Information
One may assume that given j
ρN
, the random variables z
ρN+2
and z
ρN
are
independent. Thus, from the first part one gets
P(z
ρN+2
= 0 & z
ρN
= 0 | j
ρN
= 0)
= P(z
ρN+2
= 0 | j
ρN
= 0)P(z
ρN
= 0 | j
ρN
= 0)
≈
2
N
2
N
(from Equation (6.6) and Lemma 6.3.5)
=
4
N
2
and from the second part one has
(N −1)P(z
ρN+2
= 0 & z
ρN
= 0 | j
ρN
= 0)
(N −1)P(z
ρN+2
= 0 | j
ρN
= 0)P(z
ρN
= 0 | j
ρN
=
= 0)
(N −1)
P(z
ρN+2
= 0 & j
ρN
= 0)P(z
ρN
= 0 & j
ρN
= 0)
=
2
P(j
ρN
= 0)
2
1
N
−
N
2
+
1
N
3
=
(N −1)
(by Equation (6.7))
2
N−1
N
1
N
−
3
3
N
3
−
1
=
N
2
+
N
4
.
Adding the two expressions from the two parts, we have
P(z
ρN+2
= 0 | z
ρN
= 0) ≈
1
1
N
2
.
N
+
Thus, the distinguisher works as follows.
• Acquire z
ρN+2
when z
ρN
= 0.
• Find the probability P(z
ρN+2
= 0 | z
ρN
= 0).
According to Theorem 6.1.1, the number of samples required to mount a
distinguishing attack on RC4 using the above bias is O(N
3
), i.e., around 2
24
for N = 256.
Along the same line of analysis, it can be shown [157] that
P(z
ρN+1
= 0 | z
ρN
= 0) ≈
1
1
N
2
,
N
+
for ρ ≥ 1
and
P(z
ρN+2
= 0 | z
ρN+1
= 0) ≈
1
2
N
2
,
N
+
for ρ ≥ 0.
The above trio of best long-term biases of RC4 gives a trio of distinguishers
of approximately the same complexity.
