Cryptography Reference
In-Depth Information
theoretical derivation of the probability expression for Roos' observation [146].
Next, we move on to describe other biases as well.
3.1.1 Roos' Biases
Roos [146] and Wagner [185] reported the initial empirical works on the
weakness of the RC4 KSA, in which they identified several classes of weak
keys. The following important technical result appears in [146, Section 2,
Result B].
Proposition 3.1.1. [Roos, 1995] The most likely value of the y-th element
of the permutation after the KSA for the first few values of y is given by
S
N
[y] = f
y
.
The experimental values of the probabilities P(S
N
[y] = f
y
) reported
in [146] is provided in Table 3.1 below.
y
P(S
N
[y] = f
y
)
0-7
0.370 0.368 0.362 0.358 0.349 0.340 0.330 0.322
8-15
0.309 0.298 0.285 0.275 0.260 0.245 0.229 0.216
16-23
0.203 0.189 0.173 0.161 0.147 0.135 0.124 0.112
24-31
0.101 0.090 0.082 0.074 0.064 0.057 0.051 0.044
32-39
0.039 0.035 0.030 0.026 0.023 0.020 0.017 0.014
40-47
0.013 0.012 0.010 0.009 0.008 0.007 0.006 0.006
TABLE 3.1: The probabilities experimentally observed by Roos.
When y is small enough (e.g., y < the key length l), then Roos [146,
Section 2] argues that there is a high probability that none of the two elements
being swapped has been involved in any previous exchanges, and so it can
safely be assumed that S
y
[y] = y before the swap happens in round y + 1.
Thus, the most likely value of S[1] is K[0] + K[1] + 0 + 1 and that of S[2] is
K[0] +K[1] + 0 + 1 + 2. Since the probability that a particular single element
of S would not be indexed by j throughout KSA is (
N−1
N
)
N
, Roos' arguments
can be formalized as below.
Corollary 3.1.2. After the KSA, the most likely values of the second and the
third elements of the permutation are given as follows.
1. P(S
N
[1] = K[0] + K[1] + 1) ≈ (
N−1
N
)
N
.
2. P(S
N
[2] = K[0] + K[1] + K[2] + 3) ≈ (
N−1
N
)
N
.
Proof sketch of the above also appeared in [118, Section 3.4.1], but in [133,
Section 2], the expressions for the probabilities P(S
r
[y] = f
y
) for all values
of the index y in [0,N − 1] and for all rounds r, 1 ≤ r ≤ N, were theoreti-
cally derived for the first time. Related analysis in this area was performed
