Cryptography Reference
In-Depth Information
log
2
N
Since in each session we observe one sample, we need at least
∆
p
ses-
sions to reliably estimate u (here “reliably” means with probability > 50%).
The experimental observations related to various WEP attacks support this
information-theoretic lower bound.
7.2 FMS Attack
The main idea of the FMS attack [52] is as follows. For x > 1, consider that
the first x bytes of the secret key, i.e., K[0],...,K[x− 1] are known. Hence,
all the permutations S
1
,...,S
x
and the indices j
0
,...,j
x
are also known. 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+1
[x] gets the value of S
x
[j
x+1
]. Suppose we have the following.
S
x
[1] < x
(7.1)
and
S
x
[1] + S
x
[S
x
[1]] = x.
(7.2)
Conditions 7.1 and 7.2 together are called the resolved condition. If j
x+1
∈
{1,S
x
[1]} (the probability of which is
N−2
N
) then S
x+1
[1] = S
x
[1] and
S
x+1
[S
x+1
[1]] = S
x
[S
x
[1]]. Thus,
N−2
= x.
S
x+1
[1] + S
x+1
[S
x+1
[1]]
(7.3)
Recall that = means that the equality holds with probability p. In the next
N −x rounds, i.e., in
• the next (N−x−1) rounds of the KSA (corresponding to r = x+ 2,x+
3,...,N), and
• the first round of the PRGA,
index i
r
takes values in {x + 1,x + 2,...,N − 1,0} and hence does not visit
the indices 1, S
x+1
[1] = S
x
[1] < x and x = S
x+1
[1] + S
x+1
[S
x+1
[1]]. If j
r
also
does not visit these three indices in those rounds, the probability of which is
(
N−
N
)
N−x
, then the values at indices 1, S
x+1
[1] and S
x+1
[1]+S
x+1
[S
x+1
[1]] of
the permutation S
x+1
are not swapped throughout the KSA and also during
the first round of the PRGA. Hence, the first keystream output byte is given
