WEP Key Recovery Attacks

One of the juiciest targets for an attacker targeting a WEP-protected WLAN is recovering the WEP key. Because of vulnerabilities in the WEP protocol and some implementation mistakes, several attacks have been developed that compromise WEP keys. The most serious of these is the Fluhrer-Mantin-Shamir (FMS) attack, which allows a passive sniffer to recover WEP keys with as little as nine minutes of sniffing.

Dictionary-Based Key Attacks

So-called strong WEP keys are 104 bits, or 26 hexadecimal digits, which is a chore to type. Dynamic key distribution methods, such as those included in the Lightweight Extensible Authentication Protocol (LEAP) or the Protected Extensible Authentication Protocol (PEAP), overcome this chore. However, in small installations, manual WEP keys are the usual choice. Because of the difficulty of typing in such a long key, manufacturers have developed an alternative method based on a passphrase for configuring 40- or 104-bit WEP keys. To ensure interoperability, there is an unpublished standard for this "key-generation" algorithm. Unfortunately, this algorithm reduces the possible WEP keys that can be chosen and opens them up to a dictionary-based attack.

Tim Newsham introduced wep_crack, a tool that can crack these passphrase-based passwords. One technique it uses is to run all the words in a dictionary through the WEP key-generation algorithm. It operates on a file of captured packets. First the tool finds a WEP-encrypted packet. Then it tries to decrypt the packet using WEP keys based on all the dictionary words it has. If the integrity check vector of the packet is correct, the tool knows it has decrypted the packet correctly and has found the right WEP key. If the passphrase occurs in a dictionary, it will be cracked.

Newsham also noticed that the algorithm for 40-bit key generation allows only 2²¹ possible WEP keys, no matter how long or complex the passphrase is. This limits you to only 2 million keys, which an attacker can search exhaustively (called a brute force attack) in a matter of minutes on modern hardware. Newsham also wrote a simple tool called wep_decrypt, which decrypts a file of packets after you have the WEP key. The tool works independent of the manner in which you obtained the WEP key.

Figure 6-9 shows three runs of wep_crack. In the first run, it cracks a 40-bit WEP key by brute force. That passphrase was not based on a dictionary word. This attack took about 60 seconds. In the second run, it cracks a 40-bit key based on the word "test." In the third run, it cracks a 104-bit WEP key based on the word "yeomanry." The latter two attacks only took approximately 1 second.

Figure 6-9. The wep_crack Tool Rapidly Cracks Passphrase-Based WEP Keys

The Fluhrer-Mantin-Shamir Attack

The most damaging attack on WEP was discovered by three cryptographers: Scott Fluhrer, Itsik Mantin, and Adi Shamir. In cryptographic literature, the attack often bears their initials, FMS. This attack is rooted in a flaw in the key scheduling algorithm (KSA) of the RC4 encryption protocol, on which WEP is based. The KSA is the first step of RC4, and it transforms the key into a matrix from which RC4 generates its cryptographic keystream. The flaw is a slight statistical anomaly in which, given certain keys structured in certain ways, a small portion of the key is slightly more likely to end up in the keystream than other values. This sounds like a tiny flaw that would be of interest only to mathematicians, but to cryptographers, nonrandom anomalies like this are potentially fatal to cryptographic algorithms.

The attack relies on gathering large amounts of encrypted data and looking for the packets in which the key has the weak structure. These are so-called "interesting packets." In these interesting packets, there is only about a 5-percent chance that one byte of the key will be leaked. Therefore, the attacker gathers hundreds of interesting packets and keeps statistics. Over time, the leaked byte value shows up more than the other possible values and clearly shows up as the most frequent value. Figure 6-10 is a graph of the values for one of the key bytes from a sample packet dump. It clearly illustrates how obvious the bias is.

Figure 6-10. After the Attacker Gathers Enough Packets, the Flaw in WEP Reveals the Bytes of the Key, One by One

The attacker simply keeps counters for each of the 5 or 13 bytes of the keystream. After gathering enough packets, he has a reasonable assurance that the byte values with the highest totals are indeed the actual bytes of the key. The more packets he gathers, the higher the assurance that he has in fact cracked the key. Estimates are that in the worst case, an attacker can gather enough packets to crack the key with as few as 1 million packets. These can be gathered in as few as 9 minutes on a saturated network. Although the attack would likely take longer, it points to the need to have a dynamic WEP key-management scheme. With protocols such as LEAP and PEAP, WEP keys can be assigned per user and configured to be changed based on time or packet limits.

FMS Tools

Several tools implement the FMS attack:

WEPCrack (http://wepcrack.sourceforge.net) was the first publicly released tool. It requires a Prism2-based card (Linksys, SMC, and others) for sniffing. WEPCrack is actually a collection of tools that requires some attacker sophistication because the attacker must figure out how to use the prismdump tool on his own. WEPCrack then analyzes the output and tries to crack the keys.

AirSnort (http://airsnort.shmoo.com) is much better known, mainly because it is easier to use. It is a complete tool that has the ability to put the card in sniffing mode and has a front-end GUI. Airsnort implements an attack based on a subset of the FMS weak packets. Figure 6-11 shows a sample run of AirSnort.

Figure 6-11. AirSnort Recovers the 104-Bit WEP Key 12:12:12:12:12:12:12:12:12:12:12:12:12 Using Only About 1.5 Million Encrypted Packets

The bsd-airtools package includes a pair of tools for cracking WEP keys. dwepdump captures the packets, whereas dwepcrack uses the dumps to crack WEP keys while using the FMS attack.

It should be clear at this point that WEP is seriously flawed and that many tools are readily available to exploit some of these flaws. Fortunately, the solutions in WPA and 802.11i eliminate these attacks. It should also be clear why vendors strongly recommend upgrading to these solutions.