Cryptography Reference
In-Depth Information
1.5
1.0
0.5
0.0
3
32
64
96
128
160
192 224 255
Index r of RC4 keystream bytes.
FIGURE 6.1: Value of c
r
versus r during RC4 PRGA (3 ≤ r ≤ 255).
Corollary 6.2.10. For 3 ≤ r ≤ 255, the probability that the r-th RC4
keystream byte is equal to 0 is
N
+
1.3471679056
1
≥ P(z
r
= 0) ≥
1
N
+
0.2428109804
.
N
2
N
2
Proof: We calculate all the values of c
r
(as in Theorem 6.2.9) for the range
3 ≤ r ≤ 255 and find that c
r
is a decreasing function in r where 3 ≤ r ≤ 255
(one may refer to the plot in Fig. 6.1). Therefore, we get
3≤r≤255
c
r
= c
3
= 1.3471679056 and
max
3≤r≤255
c
r
= c
255
= 0.2428109804.
min
Hence the result.
Fig. 6.2 depicts a comparison between the theoretically derived vs. exper-
imentally obtained values of P(z
r
= 0) versus r, where 3 ≤ r ≤ 255. The
experimentation has been carried out with 1 billion trials, each trial with a
randomly generated 16-byte key.
Denote X and Y to be the distributions corresponding to random stream
and RC4 keystream respectively and define A
r
as the event “z
r
= 0” for r = 3
to 255. From the formulation of Theorem 6.1.1, we can write p
0
=
1
N
and
c
r
ǫ =
N
. Thus, to distinguish RC4 keystream from random stream based on
the event “z
r
= 0,” one would need samples of the order of
−2
≈ O(N
3
).
−1
1
N
c
r
N
We can combine the effect of all these distinguishers by counting the number of
zeros in the initial keystream of RC4, according to Theorem 6.2.11, as follows.
Theorem 6.2.11. The expected number of 0's in RC4 keystream rounds 3 to
255 is approximately 0.9906516923.
