Problems with WEP

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.

1. Manual key management is a minefield of problems. Setting aside the operational issues with distributing identical shared secrets to the user population, the security concerns are nightmarish. New keying material must be distributed on a "flag day" to all systems simultaneously, and prudent security practices would lean strongly toward rekeying whenever anybody using WEP leaves the company (the administrative burden may, however, preclude doing this). Widely distributed secrets tend to become public over time. Passive sniffing attacks require obtaining only the WEP keys, which are likely to be changed infrequently. Once a user has obtained the WEP keys, sniffing attacks are easy, especially since 802.11 analyzers incorporate decryption capabilities.
2. As standardized, static WEP offers a shared secret of only 40 bits. Security experts have long questioned the adequacy of 40-bit private keys, and many recommend that sensitive data be protected by at least 128-bit keys.[*] In the years since the initial flaws in WEP were published, the industry-standard extended key length is only 104 bits.

   [*] 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.

3. Stream ciphers are vulnerable to analysis when the keystream is reused. WEP's use of the IV tips off an attacker to the reuse of a keystream. Two frames that share the same IV almost certainly use the same secret key and keystream. This problem is made worse by poor implementations, which may not pick random IVs. The Berkeley team identified one implementation that started with an IV of 0 when the card was inserted and simply incremented the IV for each frame. Furthermore, the IV space is quite small (less than 17 million), so repetitions are guaranteed on busy networks.
4. Infrequent rekeying allows attackers to assemble what the Berkeley team calls decryption dictionaries large collections of frames encrypted with the same keystreams. As more frames with the same IV pile up, more information is available about the unencrypted frames even if the secret key is not recovered. Given how overworked the typical system and network administration staff is, infrequent rekeying is the rule.
5. WEP uses a CRC for the integrity check. Although the value of the integrity check is encrypted by the RC4 keystream, CRCs are not cryptographically secure. Use of a weak integrity check does not prevent determined attackers from transparently modifying frames.[]

   ] 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.

6. key scheduling algorithm.

   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.