Information Technology Reference
In-Depth Information
This weakness makes it possible, under certain conditions, to recover the input of
RC4 (i.e., the key), knowing its first byte of output. This first byte of output is easy to
determine since the first data to be encrypted in a WEP packet is usually the SNAP
header (as with IP and ARP packets) and this header is almost always 0xAA.
A weak IV has a format of B+3:FF:X where B is the index of the shared key's byte
currently being guessed, FF is 255, and X can be any number between 0 and 255.
Given a weak IV, the first several steps of the RC4 KSA that affect the leftmost
positions of the table can be computed. There is then approximately a 5% chance
that the remainder of the permutations of the KSA occur in the right part of the table.
There is therefore a 5% chance that the portion of the table that was computed is the
table that will be the input of the PRGA. Since the value determined for this shared
key byte is only accurate 5% of the time, a number of weak IVs (usually about 60)
with varying X's have to be used to compute guessed values for that byte. The value
that is produced most often has a high probability of being the correct value. This
process is then repeated to recover the remaining bytes of the shared key. As a rule of
thumb, a few million packets generate enough weak IV traffic to recover 40-bit WEP
keys. The attack is linear regardless of the key size so it does not take that much more
traffic to recover a 104-bit key. A very good illustrated description of this process can
be found in
[6]
.
Since the IEEE standard of IV selection was so ambiguous, many wireless vendors
use sequential IV generators that begin with 00:00:00 and wrap with FF:FF:FF. This
is the worst of both worlds. Not only is this procedure guaranteed to generate weak
IVs, but it does so predictably.
WEPCrack (
http://wepcrack.sourceforge.net
)
was the first publicly released tool to
use the FMS attack. Airsnort (
http://airsnort.shmoo.com
)
is much better known and
much easier to use. Since modern WiFi cards and appliances reduce the percentage
of weak IVs that are generated (under the rubric of “WEP+” or “Advanced WEP
Encryption,” etc.), Airsnort is declining in importance as it takes an unreasonably
long time to collect enough packets to break keys.
2 . 4 E n h a n c e m e n t s t o t h e F M S A t t a c k
Subsequent to the original FMS research, a number of people have discovered
that there are more ways that weak IV's can be used to speed up the WEP cracking
process. “Using the Fluhrer, Mantin, and Shamir attack to break WEP,” Stubblefield
et al.
[17]
discusses an approach that deviates from the standard FMS algorithm
methodology of finding all the previous values for B before finding the next value.
The authors suggest that weak IVs associated with higher B values can be used to
narrow down the beginning bytes of the secret key. This can be done by testing
different values of the key and checking to see if the decrypted packet has a valid
