Cryptography Reference
In-Depth Information
0.00393
Experimental (16 byte key)
Theoretical
Probability 1/N (ideal case)
0.00392
0.00391
0.00390
3
32
64
96
128
160
192
224
255
Index r of RC4 keystream bytes.
FIGURE 6.2: P(z
r
= 0) versus r during RC4 PRGA (3 ≤r ≤ 255).
Proof: Let X
r
be a random variable taking values X
r
= 1 if z
r
= 0, and
X
r
= 0 otherwise. Hence, the total number of 0's in rounds 1 to 255 excluding
round 2 is given by
255
C =
X
r
.
r=3
We have E(X
r
) = P(X
r
= 1) = P(z
r
= 0) from Theorem 6.2.9. By linearity
of expectation,
255
255
E(C) =
E(X
r
) =
P(z
r
= 0).
r=3
r=3
Substituting the numeric values of the probabilities P(z
r
= 0) from Theo-
rem 6.2.9, we get E(C) ≈ 0.9906516923. Hence the result.
One may note that for a random stream of bytes, this expectation turns
out to be E(C) =
254
256
= 0.98828125. Thus, the expectation for RC4 is
approximately 0.24% higher than that for the random case. The inequality
of this expectation E(C) in a RC4 keystream compared to that in a random
stream of bytes may be used to design a distinguisher.
In a similar line of action of Mantin's broadcast attack based on the second
byte, we may exploit the bias observed in bytes 3 to 255 of the RC4 keystream
to mount a similar attack on RC4 broadcast scheme. Notice that we obtain
a bias of the order of
1
N
2
in each of the bytes z
r
where 3 ≤ r ≤ 255. Thus,
roughly speaking, if the attacker obtains about N
3
ciphertexts corresponding
to the same plaintext M (from the broadcast scheme), then he can check the
frequency of occurrence of bytes to deduce the r-th (3 ≤ r ≤ 255) byte of M.
The most important point to note is that this technique will work for each
r where 3 ≤ r ≤ 255, and hence will reveal all the 253 initial bytes (number
