Cryptography Reference
In-Depth Information
7.3 Mantin's Attack
In [52, Section 9], the authors suggested to throw away the first 256
keystream output bytes of RC4 PRGA to resist the FMS attack. However, in
2005, Mantin proposed a WEP mode attack on RC4 [108, Section 4.2] along
the same line of the the original FMS attack [52, Sections 6,7] using Glimpse
Theorem (see Theorem 5.2.1), by exploiting the the 257th keystream byte.
As in the FMS attack, for x > 1, the key bytes K[0],...,K[x − 1] are
assumed to be known (hence S
x
and j
x
are also known) and the target is
to derive the next key byte K[x]. In round x + 1, we have i
x+1
= x and
j
x+1
= j
x
+ S
x
[x] + K[x]. After the swap in this round, S
x
[j
x+1
] moves to
S
x+1
[x]. Suppose IVs are selected in such a way that the following condition
holds.
S
x
[1] = x.
(7.5)
= 1, the probability of which is
N−1
N
If j
x+1
, then S
x+1
[1] = S
x
[1]. Thus,
N−1
= x.
S
x+1
[1]
(7.6)
In the next N − x − 1 rounds till the end of the KSA, i.e., in rounds r =
x+ 2,x+ 3,...,N, index i
r
takes values in {x+ 1,x+ 2,...,N−1} and hence
does not visit the indices 1 and x = S
x+1
[1]. If j
r
also does not visit these
two indices in those rounds, the probability of which is (
N−
N
)
N−x−1
, then the
values at indices 1 and S
x+1
[1] are not swapped. Thus, we get the following
probabilities involved.
2
N
=
S
N
[1]
N + 1−z
N+1
(according to Corollary 5.2.2)
(
N−
N
)
N−1
=
S
1
[1]
(when j
r
= 1, r = 2 to N)
S
N
[j
1
]
=
(swap in PRGA round 1)
(since j
1
= S
N
[1])
=
S
N
[S
N
[1]]
(
N−
N
)
N−x−1
=
S
x+1
[S
x+1
[1]]
N−1
=
S
x+1
[x]
(by Equation (7.6))
=
S
x
[j
x+1
]
(swap in KSA round x + 1)
=
S
x
[j
x
+ S
x
[x] + K[x]].
For x ≥ 3 and N = 256, the above chain of events occurs approximately
with probability
N−1
N−3−1
3N
2
N
N −1
N
N −2
N
N −1
N
≈
2
N
N −1
N
≈
2
e
3
N
