Cryptography Reference
In-Depth Information
by
S 1 [S 1 [i 1 ] + S 1 [j 1 ]]
z 1
=
S 1 [S 1 [1] + S 1 [S N [1]]]
(since i 1 = 1 and j 1 = S N [1])
=
S 1 [S N [1] + S N [S N [1]]]
=
(reverting the swap)
( N− N ) N−x
=
S x+1 [S x+1 [1] + S x+1 [S x+1 [1]]]
N−2
=
S x+1 [x]
(by Equation (7.3))
=
S x [j x+1 ]
(due to the swap in round x + 1)
=
S x [j x + S x [x] + K[x]]
(expanding j x+1 ).
Thus, when the resolved condition is satisfied, the event
K[x] = S −1
x
[z 1 ]−j x
−S x [x]
(7.4)
N ( N− N ) N−x . For x ≥ 3 and N = 256, this prob-
ability is always greater than 0.05. Hence if one can find around 60 IVs for
which S x satisfies the resolved condition, then K[x] will be identified properly
in approximately 3 cases.
An attacker starts with some IVs and their corresponding first keystream
bytes. The attacker chooses a subset of these keys that satisfies the resolved
condition after the first x steps of the RC4 KSA. For each such key, (s)he finds
a candidate for K[x] using Equation (7.4). The value having the maximum
frequency is taken as the estimate of K[x]. Thus, the attacker knows the first
(x + 1) key bytes K[0],...,K[x]. One can then repeat the above strategy
to derive K[x + 1],K[x + 2],...,K[l − 1] iteratively for all the l − 1 − x
unknown key bytes. When all the key bytes are estimated, the resulting key
combined with a few IVs can be used to generate RC4 keystream and thus can
be verified for correctness. If the generated keystream byte does not match
with the observed keystream, at least one of the key bytes must have been
guessed wrongly. The attacker may assume that K[y] is wrong for some y (for
example, (s)he may consider the key byte whose most frequent value and the
second most frequent value differs by the smallest amount) and proceed with
the second most frequent value among the candidates for K[y] as its estimate.
The process continues until the correct key is found or a predetermined number
of attempts have failed.
The IVs that satisfy the resolved condition are termed as weak IVs. In the
WEP scenario, the attacker cannot choose the IV of a packet that a sender
is going to use. He has to collect enough samples of packets until he is lucky
to encounter some weak IVs. In practice, the attack requires 4 to 6 million
packets for a success probability of at least 50% depending on the environment
and implementation.
N−2
holds with probability
Search WWH ::




Custom Search