Cryptography Reference
In-Depth Information
y
P(S
N
[y] =
y(y+1)
2
y
+
K[x])
x=0
0-7
0.371 0.368 0.364 0.358 0.351 0.343 0.334 0.324
8-15
0.313 0.301 0.288 0.275 0.262 0.248 0.234 0.220
16-23
0.206 0.192 0.179 0.165 0.153 0.140 0.129 0.117
24-31
0.107 0.097 0.087 0.079 0.071 0.063 0.056 0.050
32-39
0.045 0.039 0.035 0.031 0.027 0.024 0.021 0.019
40-47
0.016 0.015 0.013 0.011 0.010 0.009 0.008 0.008
TABLE 3.2: The probabilities following Corollary 3.1.6.
3.1.2 Intrinsic Weakness of Shu
e-Exchange Type KSA
In the KSA of RC4, the deterministic index i is incremented by one and
the pseudo-random index j is updated by the rule
j = j + S[i] + K[i].
In our notation, we write, for 0 ≤ y ≤ N −1,
j
y+1
= j
y
+ S
y
[y] + K[y].
Here, the increment of j is a function of the permutation and the secret
key. One may expect that the correlation between the secret key and the
permutation can be removed by modifying the update rule for j. However, it
turns out that for a certain class of rules of this type, where j across different
rounds is distributed uniformly at random, there always exists significant bias
of the permutation at any stage of the KSA toward some combination of the
secret key bytes with non-negligible probability. Though the proof technique
is similar to that in Section 3.1.1, it may be noted that the analysis in these
proofs focus on the weakness of the particular “form” of RC4 KSA.
The update of j in the KSA can be modeled as an arbitrary function u of
1. the current values of i,j,
2. the i-th and j-th permutation bytes from the previous round, and
3. the i-th and j-th key bytes.
Using our notations, we may write
.
j
y+1
= u
y,j
y
,S
y
[y],S
y
[j
y
],K[y],K[j
y
]
(3.1)
For future reference, let us call the KSA with this generalized update rule the
GKSA.
