Cryptography Reference
In-Depth Information
Proof: Let us consider two possible cases as follows.
Case I: Suppose that S
0
[j
1
] = 0. We already proved in Lemma 6.2.1 that
P(z
1
= 0 | S
0
[j
1
] = 0) = 0.
Case II: Suppose that S
0
[j
1
] = 0. Assuming z
1
is uniformly random in this
case, we have
1
N
.
P(z
1
= 0 | S
0
[j
1
] = 0) =
Combining these two cases, we get
= P(S
0
[j
1
] = 0)P(z
1
= 0 | S
0
[j
1
] = 0)
+P(S
0
[j
1
] = 0)P(z
1
= 0 | S
0
[j
1
] = 0)
P(z
1
= 0)
1
N
N −1
N
1
N
=
0 +
1
N
−
1
=
N
2
.
1
Thus, z
1
has a negative bias of
N
2
toward 0.
Theorem 6.2.2 immediately gives a distinguisher. Let X and Y be the dis-
tributions corresponding to random stream and RC4 keystream respectively
and define A as the event “z
1
= 0.” The bias can be written as p
0
(1+ǫ), where
p
0
=
N
and ǫ = −
N
. According to Theorem 6.1.1, the number of samples
required to distinguish RC4 from random stream with a constant probability
of success is O(
1
1
p
0
ǫ
2
), i.e., O(N
3
).
6.2.2 Strong Positive Bias in the Second Byte toward Zero
Currently the best distinguisher for RC4 keystream is due to Mantin and
Shamir [107], that requires around 2
8
samples. This is based on the obser-
vation that P(z
2
= 0) ≈
N
, which is two times the probability of random
association.
Theorem 6.2.3. Assume that the initial permutation S
0
is randomly chosen
from the set of all possible permutations of {0,...,N −1}. Then
P(z
2
= 0) ≈
2
N
.
Proof: PRGA starts with i
0
= j
0
= 0. In round 1, i
1
= 1 and j
1
=
j
0
+ S
0
[i
1
] = S
0
[i
1
] = S
0
[1]. In round 2, i
2
= 2 and j
2
= j
1
+ S
1
[i
2
].
Let us consider two possible cases as follows.
Case I: Suppose that S
0
[2] = 0. Now, if j
1
= S
0
[i
1
] = 2, then this 0 is not
