Cryptography Reference
In-Depth Information
independently in [180, Section 4] and [184, Section 3] around the same time
of [133]. However, these efforts are mostly tuned to exploit the WEP scenario,
where the secret key is used with IV.
Below we are going to present the general formula (Theorem 3.1.5) that
estimates the probabilities with which the permutation bytes after each round
of the RC4 KSA are related to certain combinations of the secret key bytes,
namely f
y
. The result gives a theoretical proof explicitly showing how these
probabilities change as functions of y. Further, the result holds for any arbi-
trary initial permutation (need not be an identity permutation).
Though j is updated using a deterministic formula, it is a linear function
of the secret key bytes. If the secret key generator produces the secret keys
uniformly at random, which is a reasonable assumption, then the distribution
of j would also be uniform.
The proof of Theorem 3.1.5 depends on the following results.
Lemma 3.1.3. Assume that the index j takes its value from Z
N
independently
and uniformly at random at each round of the KSA. Then, for 0 ≤ y ≤N−1,
1+
y(y+1)
2
y
y
N −1
N
1
N
.
P
j
y+1
=
S
0
[x] +
K[x]
≈
+
x=0
x=0
Proof: For y ≥ 0, let E
y
denote the event that
y
y
j
y+1
=
S
0
[x] +
K[x]
x=0
x=0
and let A
y
denote the event that
S
x
[x] = S
0
[x]
for all x∈ [0,y].
A
y
stand for the complementary event of A
y
. We have
Let
| A
y
)P( A
y
).
P(E
y
) = P(E
y
|A
y
)P(A
y
) + P(E
y
| A
y
) ≈
N
We also have P(E
y
|A
y
) = 1 and P(E
y
due to random association.
We show by induction that
y(y+1)
2
N −1
N
P(A
y
) =
.
The base case P(A
0
) = 1 is trivial. For y ≥ 1, we have
P(A
y
)
= P
A
y−1
∧(S
y
[y] = S
0
[y])
≈ P(A
y−1
)P(S
y
[y] = S
0
[y])
(y−1)y
2
P(S
y
[y] = S
0
[y]).
N −1
N
=
