Cryptographers have identified many flaws in WEP. The designers specified the use of RC4, which is widely accepted as a strong cryptographic cipher. Attackers, however, are not limited to a full-frontal assault on the cryptographic algorithmsthey can attack any weak point in the cryptographic system. Methods of defeating WEP have come from every angle. One notable slip was a vendor who shipped access points that exposed the secret WEP keys through SNMP, allowing an attacker to ask for just the key. Most of the press, though, has been devoted to flaws beyond implementation errors, which are much harder to correct.
Cryptographic Properties of RC4
Reuse of the keystream is the major weakness in any stream cipher-based cryptosystem. When frames are encrypted with the same RC4 keystream, the XOR of the two encrypted packets is equivalent to the XOR of the two plaintext packets. By analyzing differences between the two streams in conjunction with the structure of the frame body, attackers can learn about the contents of the plaintext frames themselves. To help prevent the reuse of the keystream, WEP uses the IV to encrypt different packets with different RC4 keys. However, the IV is part of the packet header and is not encrypted, so eavesdroppers are tipped off to packets that are encrypted with the same RC4 key.
Implementation problems can contribute to the lack of security. 802.11 admits that using the same IV for a large number of frames is insecure and should be avoided. The standard allows for using a different IV for each frame, but it is not required.
WEP incorporates an integrity check, but the algorithm used is a cyclic redundancy check (CRC). CRCs can catch single-bit alterations with high probability, but they are not cryptographically secure. Cryptographically secure integrity checks are based on hash functions, which are unpredictable. With unpredictable functions, if the attacker changes even one bit of the frame, the integrity check will change in unpredictable ways. The odds of an attacker finding an altered frame with the same integrity check are so slim that it cannot be done in real time. CRCs are not cryptographically secure. CRC calculations are straightforward mathematics, and it is easy to predict how changing a single bit will affect the result of the CRC calculation. (This property is often used by compressed data files for repair! If just a few bits are bad, they can sometimes be identified and corrected based on a CRC value.)
Design Flaws of the WEP System
WEP's design flaws initially gained prominence when the Internet Security, Applications, Authentication, and Cryptography (ISAAC) group at the University of California, Berkeley, published preliminary results based on their analysis of the WEP standard.[*] None of the problems identified by researchers depend on breaking RC4. Here's a summary of the problems they found; I've already touched on some of them:
[*] The report is available on the Web at http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html. Items 36 on the following list are summarized from that report.
[*] To be fair, WEP was originally developed with the goal of being exportable under the then-current U.S. regulations for export of cryptographic systems. A longer key could not have been used without jeopardizing the commercial viability of U.S.-built 802.11 products.
] 802.11 requires frame retransmissions in the case of loss, so it may be possible for an attacker to retransmit a frame and cause a replacement injected frame to be accepted as legitimate.
The Fluhrer-Mantin-Shamir attack, or FMS attack for short, assumes the ability to recover the first byte of the encrypted payload. In many cryptographic systems, that would be a big assumption. WEP, however, is used to protect 802.11 frames, and the 802.11 frame body begins with a SNAP header. Therefore, the cleartext value of the first byte is known to be 0xAA. Because the first cleartext byte is known, the first byte of the keystream can be easily deduced from a trivial XOR operation with the first encrypted byte.
The paper's attacks are focused on a class of weak keys written in the form (B+3):FF:N. Each weak IV is used to attack a particular byte of the secret portion of the RC4 key. Key bytes are numbered from zero. Therefore, the weak IV corresponding to byte zero of the secret key has the form 3:FF:N. The second byte must be 0xFF; knowledge of the third byte in the key is required, but it need not be any specific value.
A standard WEP key is 40 secret bits, or 5 bytes numbered consecutively from 0 to 4. Weak IVs on a network protected by standard WEP must have a first byte that ranges from 3 (B=0) to 7 (B=4) and a second byte of 255. The third byte must be noted but is not constrained to any specific value. There are 5 x 1 x 256=1,280 weak IVs of this type in a static WEP network. Additional classes of weak IVs have been exploited since the publication of the paper, bringing the total number of weak IVs to about 9,000; this is approximately 5% of the total number of IVs. These new classes depend on the relationships between IV bytes. Readers who are interested in the other classes of weak IVs should refer to the source code of WEP cracking tools.[*]
[*] For example, see the classify() function in Airsnort's crack.c.
Each weak IV leaks information about a key byte. By applying probability theory, Fluhrer, Mantin, and Shamir estimated that about 60 weak IVs need to be collected for each key byte. Furthermore, and perhaps worst of all, the attack gains speed as more key bytes are determined. Guessing the first key byte helps you get the second, and so on. Success cascades through the attack, and it works in linear time. Doubling the key length only doubles the computational time for the attack to succeed.
With such a tantalizing result, it was only a matter of time before it was used to attack a real system. In early August 2001, Adam Stubblefield, John Ioannidis, and Avi Rubin applied the FMS attack to an experimental, but real, network with devastating effect.[*] In their testing, 60 resolved cases usually determined a key byte, and 256 resolved cases always yielded a full key. It took less than a week to implement the attack, from the ordering of the wireless card to the recovery of the first full key. Coding the attack took only a few hours. Key recovery was accomplished between five and six million packets, which is a small number for even a moderately busy network.
[*] This work is described more fully in AT&T Labs Technical Report TD-4ZCPZZ.
Reporting on a successful attack, however, is nothing compared to having a public code base available to use at will. The hard part of the Fluhrer-Mantin-Shamir attack was finding the RC4 weakness. Implementing their recommendations is not too difficult. In late August 2001, AirSnort, an open source WEP key recovery program, was released. Many tools have followed AirSnort.
Key recovery defenses
Longer keys are no defense against key recovery attacks. The time required to recover a key can be broken up into the gathering time required to collect enough frames for the attack, plus the computational time required to run the program and get the key. Computational time is only a few seconds; gathering time generally dominates the attack. Longer keys require slightly more computational time, but do not require different gathering time. As the key length increases, more weak IVs are caught in the dragnet.
One defense adopted by many vendors is to avoid using weak IVs. Most vendors have now changed products so that each IV to be used is first checked against a classifier, and any weak IVs are replaced by non-weak IVs. Unfortunately, reducing the size of the IV space may cause IV re-use to happen earlier.
Network administrators have responded to key recovery attacks by using stronger protocols, such as the 802.11i protocols discussed in Chapter 7. For many organizations, this is a solution. However, newer protocols may not be as compatible as dynamic WEP with existing equipment. To mitigate the use of WEP, most network administrators set a re-key time of between 5 and 15 minutes, depending on the acceptable overhead on the network.
Introduction to Wireless Networking
Overview of 802.11 Networks
11 MAC Fundamentals
11 Framing in Detail
Wired Equivalent Privacy (WEP)
User Authentication with 802.1X
11i: Robust Security Networks, TKIP, and CCMP
Contention-Free Service with the PCF
Physical Layer Overview
The Frequency-Hopping (FH) PHY
The Direct Sequence PHYs: DSSS and HR/DSSS (802.11b)
11a and 802.11j: 5-GHz OFDM PHY
11g: The Extended-Rate PHY (ERP)
A Peek Ahead at 802.11n: MIMO-OFDM
Using 802.11 on Windows
11 on the Macintosh
Using 802.11 on Linux
Using 802.11 Access Points
Logical Wireless Network Architecture
Site Planning and Project Management
11 Network Analysis
11 Performance Tuning
Conclusions and Predictions