CRYPTOLOGY - Hacking: The Art of Exploitation - page 440

is really quite amazing. It takes advantage of weaknesses in the key-
scheduling algorithm of RC4 and the use of IVs.
There are weak IV values that leak information about the secret key in
the first byte of the keystream. Since the same key is used over and over with
different IVs, if enough packets with weak IVs are collected, and the first byte
of the keystream is known, the key can be determined. Luckily, the first byte
of an 802.11b packet is the snap header, which is almost always 0xAA . This
means the first byte of the keystream can be easily obtained by XORing the
first encrypted byte with 0xAA .
Next, weak IVs need to be located. IVs for WEP are 24 bits, which trans-
lates to three bytes. Weak IVs are in the form of ( A + 3, N − 1, X ), where A is
the byte of the key to be attacked, N is 256 (since RC4 works in modulo 256),
and X can be any value. So, if the zeroth byte of the keystream is being
attacked, there would be 256 weak IVs in the form of (3, 255, X ), where X
ranges from 0 to 255. The bytes of the keystream must be attacked in order,
so the first byte cannot be attacked until the zeroth byte is known.
The algorithm itself is pretty simple. First, it performs A + 3 steps of the
Key Scheduling Algorithm (KSA). This can be done without knowing the
key, since the IV will occupy the first three bytes of the K array. If the zeroth
byte of the key is known and A equals 1, the KSA can be worked to the fourth
step, since the first four bytes of the K array will be known.
At this point, if S [0] or S [1] have been disturbed by the last step, the
entire attempt should be discarded. More simply stated, if j is less than 2, the
attempt should be discarded. Otherwise, take the value of j and the value of
S [ A + 3], and subtract both of these from the first keystream byte (modulo
256, of course). This value will be the correct key byte about 5 percent of the
time and effectively random less than 95 percent of the time. If this is done
with enough weak IVs (with varying values for X ), the correct key byte can be
determined. It takes about 60 IVs to bring the probability above 50 percent.
After one key byte is determined, the whole process can be done again to
determine the next key byte, until the entire key is revealed.
For the sake of demonstration, RC4 will be scaled back so N equals 16
instead of 256. This means that everything is modulo 16 instead of 256, and
all the arrays are 16 “bytes” consisting of 4 bits, instead of 256 actual bytes.
Assuming the key is (1, 2, 3, 4, 5), and the zeroth key byte will be attacked,
A equals 0. This means the weak IVs should be in the form of (3, 15, X ). In
this example, X will equal 2, so the seed value will be (3, 15, 2, 1, 2, 3, 4, 5).
Using this seed, the first byte of keystream output will be 9.
output = 9
A =0
IV = 3, 15, 2
Key = 1, 2, 3, 4, 5
Seed = IV concatenated with the key
K [] = 3 15 2 XXXXX 3152 XXXXX
S []=0123456789101112131415