Cryptography Reference
In-Depth Information
and given the above chain, the relation
K[x] = S
−1
x
−S
x
[x] (7.7)
holds with probability 1. When the above chain does not occur, Equation (7.7)
holds with probability
[N + 1−z
N+1
]−j
x
1
N
due to random association. Thus,
−S
x
[x]) ≈
2
e
3
N
1−
2
e
3
N
1
N
P(K[x] = S
−1
x
[N + 1−z
N+1
]−j
x
1 +
≈
1
N
2
e
3
1 +
≈
1.1
N
.
As reported in [108], the empirical estimate of the above probability is
1.075
N
and this attack recovers a 16-byte key with 80% success probability from 2
25
chosen IVs. If choice of IVs is not possible, then the attacker needs to test
approximately 2
48
different keys for correctness.
7.4 Klein's Attack
Both the FMS and Mantin's attacks require certain weak IVs. Klein im-
proved these attacks in [86] by showing how to attack RC4 in the WEP mode,
without requiring any weak IV condition.
As before, suppose for x > 1, K[0],...,K[x−1] (and hence S
x
and j
x
) are
all known and the goal is to to find K[x]. In round x+1, we have i
x+1
= x and
j
x+1
= j
x
+S
x
[x]+K[x] and the swap moves S
x
[j
x+1
] = S
x
[j
x
+S
x
[x]+K[x]]
into S
x+1
[x].
Now, we consider two possible cases in which the event (x−z
x
= S
x+1
[x])
can occur.
Case I: S
x−1
[x] = S
x+1
[x].
After round x of the KSA, we need to wait for N − x − 1 remaining
steps of the KSA and the first x-1 steps of the PRGA for index i (i.e.,
the index i
x
) to visit the index x again. Thus, S
x−1
[x] would remain
the same as S
x+1
[x] if the index x is also not visited by j in those
N−x−1 +x−1 = N −2 rounds (not visited by j
r
in rounds r = x + 2
to N of the KSA and not visited j
r
in rounds r = 1 to x− 1 of the
PRGA), the probability of which is (
N−1
N
)
N−2
. We also have
P(x−z
x
= S
x+1
[x] | S
x−1
[x] = S
x+1
[x])
= P(x−z
x
= S
x−1
[x])
2
N
(according to Corollary 5.2.2).
=
