Cryptography Reference
In-Depth Information
of the probabilities are much higher. In case of Proposition 5.5.1, this is 0.37
and in case of Theorem 5.5.2, this is
N
(1 + φ
N
) ≈
1
1
(1 + 0.37)
≈ 0.0053.
256
It is important to note that the bias in S observed by Roos (Proposi-
tion 3.1.1, item 2 of Corollary 3.1.2) and extended in Proposition 5.5.1 do not
necessarily imply the bias in z
1
. For example, suppose S
0
[2] (or S
1
[2]) equals
some combination of the secret key bytes with probability 1. The output z
1
may still be unbiased, if the index t
1
, where z
1
is selected from, is uniformly
random. However, it has been proved (Theorem 5.3.1) that t
1
is not uniformly
random. In other words, there may exist some bias in S
0
[2] due to the weak-
ness of the KSA. But it is the bias in t
1
due to the weakness of the PRGA that
propagates the bias from S
0
[2] to z
1
. The proof of Theorem 5.5.2 connects
the bias in S
0
[2] and that in t
1
and relates them to the bias in z
1
.
5.5.2 Results for Secret Keys Whose First Two Bytes Sum
to Zero
Recall that Theorem 5.3.1 demonstrated a significant bias in the index
in S, where the first byte of the keystream output is selected from. In this
section, Theorem 5.5.3 shows that this bias is increased significantly if the first
two key bytes satisfy the condition K[0] + K[1] = 0. Further, Theorem 5.5.2
proved a bias in the first byte of the output toward the first three bytes of
the secret key. All the three results, i.e., Theorems 5.3.1, 5.5.3 and 5.5.2 were
discovered in [131]. On the other hand, Roos [146] experimentally observed
that given any RC4 key with the restriction K[0] + K[1] = 0, the probability
that the first keystream byte generated by RC4 will be K[2]+3 ranges between
12% and 16% with an average of 13.8%. The work [131] used Theorem 5.5.3
to derive a conditional variant of Theorem 5.5.2. This variant, presented as
Theorem 5.5.4 in this section, provides a theoretical justification of Roos'
observation.
Theorem 5.5.3. Assume that the first two bytes K[0], K[1] of the secret key
add to 0 mod N. Then the bias of the output index t
1
, that selects the first
byte of the keystream output, is given by
N
N −1
N
P(t
1
= 2 | K[0] + K[1] = 0) >
.
