Attacks Against the Previous IEEE 802.11 Security Mechanisms

Unfortunately, all of the security mechanisms defined in the 1999 version of the IEEE 802.11 standard have been proven ineffective. The problems range from issues with the lowest primitives up to the high-level protocols used.

Confidentiality

There are numerous flaws in both RC4 as used in WEP and in WEP itself that indicate that WEP provides no effective protection at this point.

RC4 Problems

Since 1994, researchers have identified a series of small flaws in RC4, none of which resulted in a practical attack. More recently, however, Itsik Mantin and Adi Shamir described a reliable distinguisher^[3] for RC4 ciphertext. While this flaw was not a break, it identified a statistical bias in the second output word of RC4's pseudorandom generator. Shortly thereafter, Scott Fluhrer joined Mantin and Shamir in authoring a paper that did result in a practical and complete break (key recovery) of RC4 as used in WEP, and their attack has subsequently been implemented and released in several open source projects.

^[3] Given ciphertext produced by an unknown system, a cryptanalyst uses a distinguisher to identify the cryptologic, or algorithm, that produced the given ciphertext.

Mantin and Shamir Bias Flaw

In a paper presented at the Fast Software Encryption (FSE) 2001 conference, Mantin and Shamir (2001) described a bias in the second word of the pseudorandom stream produced by RC4: Zero occurs as the second word with twice the expected probability (1/128 instead of 1/256) in what should be a pseudorandom sequence with all values equally likely. While this may seem a minor problem, it allows ciphertext produced by RC4 to be easily distinguished from ciphertext produced with random cipher systems and it lays the groundwork for a much larger result described below.

Fluhrer, Mantin, and Shamir Key Schedule Attack

Several months later, Scott Fluhrer and colleagues found a devastating attack against a class of keys used in RC4 that leak information about the secret key. Unfortunately for WEP, the class of weak keys found by Fluhrer, Mantin, and Shamir were exactly those used by WEP (Fluhrer et al., 2001).

Fluhrer and his colleagues found that when RC4 is used with an initialization vector appended or prepended to the secret key, certain values of the IV produce a weak key. An adversary who collects enough of these weak keys passively through eavesdropping can recover the secret key in linear time with respect to the key size; in other words, an attack against 104-bit WEP is only slightly more difficult than an attack against 40-bit WEP. Furthermore, the attack relies only on the first byte of output from the RC4 pseudorandom generator, as determined by the equation: S[S[1] + S[S[1]]], where S is the S-box used in the implementation of RC4.

In most cases, determining the first pseudorandom byte would be difficult because of the variability of the underlying plaintext. But because WEP is used in an IP data-networking environment, the first byte of the vast majority of packets is 0xAA, a value in the LLC header. Thus, we have known plaintext and can easily recover the first pseudorandom byte.

Recovering the secret key now involves passively collecting enough packets of the form <keybyteindex+3, 0xFF, N>, where keybyteindex is the index of the secret key we are trying to recover and N is any byte value. This form of packet lets us guess the true key byte with an accuracy of 5%, and the trick is to collect enough such packets to ensure a correct guess. Fluhrer et al. estimate that approximately 60 such packets are required, and Stubblefield et al. (2002) found that 256 packets always selected the correct key byte. This process is iterated until all key bytes are determined.

Fluhrer et al. estimated they would need approximately four million packets to recover a 104-bit key. However, Stubblefield et al. implemented the attack and found they needed between four and six million packets to recover each key byte in an unoptimized attack. Stubblefield also optimized the attack so as to reduce the number of required packets to one million. Recovering this quantity of packets depends on the network load and can range from less than one hour in a moderately to heavily used network (300 or more packets per second) to several hours in a lightly used network.

Other WEP Problems

In addition to the problems with RC4, WEP itself has a number of flaws running the entire range of field elements in the protocol.

IV Space

WEP uses a pitifully small 24-bit IV space (2²⁴ or 16,777,216).^[4] Assuming a moderate to heavy network load, this space is exhausted within a few hours and creates an IV collision that is, the same <IV,K> pair is used to encrypt two different plaintexts. When multiple hosts share the same encryption key in a network, the time between collisions is obviously much shorter.

^[4] An interesting side note is that the attack by Fluhrer, Mantin, and Shamir would have been easier if the IV space were larger solving one problem makes another worse. This is a good example of why security is difficult.

The consequence of an IV collision is significant with a stream cipher. Because of the linearity of the XOR combining function, deriving the underlying plaintext is much easier.

Given two ciphertexts produced with the same <IV, K> pair:

C₁ = RC4(IV,K) P₁

C₂ = RC4(IV,K) P₂

XORing the two ciphertexts together removes the pseudorandom stream generated by RC4 and produces the XOR of the two plaintexts (Borisov et al., 2001).

C₁ C₂ = (RC4(IV,K) P₁) (RC4(IV,K) P₂)

C₁ C₂ = P₁ P₂

The XOR of two plaintexts makes it significantly easier to recover the two plaintexts because of their well-known structure.

Replay Attacks

The WEP protocol provides no form of message authentication; thus, it allows intercepted messages to be replayed or sent again without modification (Borisov et al., 2001). While replaying packets will not permit an adversary to become a peer on the network, it can result in a significant denial-of-service attack and can also be used to reduce the cost of other attacks. This lack of message authentication also permits attackers to create man-in-the-middle attacks.

WEP Message Modification

WEP uses a 32-bit CRC that is a linear function of the plaintext. Although WEP's RC4 encryption covers the ICV, the stream encryption also uses a linear combiner, XOR. As a result, we can manipulate an intercepted packet by flipping bits in the data and CRC portions of the packet to create a new but still valid packet with a different plaintext than the original (Walker, 2000; Borisov et al, 2001).

Recall how WEP produces ciphertext C by XORing the plaintext with the key stream. The attacker's goal in this attack is to produce a new ciphertext C´that decrypts to a new valid message with a valid ICV. Unfortunately, the attacker can accomplish this without knowing the value of the secret encryption key. Because both the RC4 encryption and the ICV are linear in nature, the attacker can modify an intercepted message by XORing the appropriate bits in the message portion of the ciphertext, and then calculating a new CRC of the changes and XORing this new CRC with the CRC portion of the datagram. The following equations, taken from Borisov et al. (2001), show this process mathematically.

C' = C < D, CRC(D) >

C' = RC4(IV,K) < M,CRC(M) > < D, CRC(D) >

C' = RC4(IV,K) < M D, CRC(M) CRC(D) >

C' = RC4(IV,K) < M', CRC(M D) >

C' = RC4(IV,K) < M', CRC(M') >

The above derivation works because the WEP CRC is linear that is, CRC(M) CRC(D) = CRC(M D). An example message modification is shown in Appendix B.

An Active Implementation of Fluhrer, Mantin, and Shamir

The research literature has not discussed the possibility of using active measures to speed the process of obtaining enough packets for a successful Fluhrer, Mantin, and Shamir attack. Obviously, active measures only make sense on lightly loaded networks.

The two possible approaches are simple. In the first and easiest approach, traffic analysis identifies an address resolution protocol (ARP) request packet. The ARP request is replayed continuously (remember WEP has no replay protection) until it collects enough packets from the ARP responses to determine the RC4 key. The second approach involves slightly more work. Here, we wait until we see an ARP request message and build upon it until it provides enough known plaintext to recover an adequate pseudorandom stream to forge Internet Control Message Protocol (ICMP) ping packets (Petroni, 2003). Ping packets are forged and the responses collected until the RC4 key can be collected.

Experimentation indicates that approximately 450 ping packets and replies can be sent per second between a station (STA) and an AP, and thus we can collect the required one million packets in approximately thirty-seven minutes. Of course, this attack fully loads the network, but if done during off-hours, it would likely remain unnoticed.

Several vendors, however, are now filtering most of the Fluhrer weak IVs in their firmware. This prevents the attacker from collecting enough weak IVs to recover the WEP secret key, but it reduces the cost of a previous attack against WEP, as described next.

An Inductive Chosen Plaintext Attack

This attack leverages several poor design aspects of WEP. The first is the lack of replay protection, the second is the nature of the CRC used, and the third is the fact that WEP is a stream cipher rather than a block cipher. The attack involves two steps (Arbaugh, 2001 and Petroni, 2003). The first step, or base phase, involves recovery of an initial amount of pseudorandom stream from traffic analysis (eavesdropping). The second step, the inductive phase, then forges messages with the recovered pseudorandom until a dictionary of all IVs is created.

Base Phase

During the base phase, we need to collect enough pseudorandom stream for a given IV so that we can begin to forge packets. The commonly used Dynamic Host Control Protocol (DHCP) makes this easy. We simply wait until we see a DHCP discover or request message that provides us with a base of known plaintext. This base is 38 bytes in length, composed of the following known elements:

LLC header:	6 bytes
IP header:	20 bytes
UDP header[5]:	8 bytes
DHCP header:	4 bytes

^[5] The 2 bytes of the UDP checksum are usually set to all zeros in most DHCP implementations. Thus, we do not need to calculate that field.

This provides us with a total of 38 bytes of pseudorandom stream, which is sufficient to forge ICMP echo request packets, also known as ping packets. We use a ping packet because it elicits a response from the targeted host, and it permits an arbitrary amount of data to be appended to the echo request.

Inductive Phase

Once we've recovered enough pseudorandom stream, we can begin the inductive phase. The inductive phase has two parts: recovery of the maximum transmission unit (MTU) and building the dictionary.

MTU Recovery

We need to recover a full MTU of the pseudorandom byte stream so we can recover a full MTU of the pseudorandom byte stream for every ping packet transmitted. The method that we use is the most complicated aspect of this attack, and it leverages the fact that the CRC provides redundant information about the underlying plaintext and the fact that WEP is a stream cipher rather than a block cipher. Our goal is to recover the MTU 1 byte at a time by guessing the next byte, and waiting for confirmation that we guessed correctly.

We begin by crafting a ping packet in a very specific fashion. We start with the 38 bytes recovered in the inductive phase, and we set n = 38. A proper ping packet without any additional payload is 34 bytes (38 bytes when the CRC or ICV is added), but we want to send a packet of 39, or n + 1 bytes. We do this by guessing the 39th byte and constructing the ping packet as shown in Figure 15.4.

Figure 15.4. MTU Recovery Process

We create a packet of n 3 bytes (or 35 bytes ping packet plus 1 payload byte). This is the data portion in Figure 15.4. We next calculate the CRC/ICV over this data portion, but we append only the first 3 bytes of the result. Now, we XOR this data with the n bytes of the pseudorandom stream, and prepend the IEEE 802.11 header and the appropriate IV, which results in a packet of n bytes. Finally, we guess the n + 1 byte and append it to the packet. Now, we have the specially crafted ping packet. We transmit it, and wait a small amount of time for a response. If we get a response, we know we guessed the correct n + 1 byte and we can proceed to recover the corresponding pseudorandom byte. If we don't get a response, then we guessed incorrectly and we continue to try the remaining 255 byte possibilities. Once we get a response, we need to recover the n + 1 pseudorandom byte, as shown in Figure 15.5.

Figure 15.5. Recovery of the n + 1 Byte

Because the host we pinged responded with an ICMP echo response packet, we know that the byte we guessed was the correct ciphertext byte for our packet. We also know the corresponding plaintext byte the fourth byte of the ICV that we didn't use in creating the packet. We now XOR these 2 bytes together (known plaintext with corresponding ciphertext), and we recover the n + 1 pseudorandom byte.

Now because we recovered the n + 1 pseudorandom byte, we continue this process (increasing n by one to recover the n + 2 pseudorandom byte) until we recover a full MTU usually 1,500 bytes for Ethernet.

Building the Dictionary

Once we've recovered the full MTU, we need to build a dictionary of all of the 2²⁴ (16,777,216) possible IVs used. This dictionary (assuming an indexed flat file) will be approximately 23.5 gigabytes well within range of today's laptop computers.

The actual recovery of the pseudorandom stream for each IV leverages the fact that the ICMP echo response returns exactly the same data that was appended to the ICMP echo request. Thus, if we send a ping equal in size to the MTU, we'll get a response of exactly the same size. But, it will be encrypted with a different IV than the one in which we transmitted the IV. Therefore, we once again have known plaintext (the data we appended to the ping request) along with the corresponding plaintext. This permits the recovery of a full MTU's worth of pseudorandom for the returned IV. To build the full dictionary, we continue the above process until we have every IV.

Cost of the Attack

The cost of the inductive chosen plaintext attack depends on how aggressive the attacker wants to be. We'll assume a moderately aggressive attacker in our calculations so we can approximate worst case for the defender.

In an implementation of the attack, the average time of recovery for a single byte in the inductive phase was 1.7 seconds/byte, and the average time to recover a full MTU (1,500 bytes) was 42.8 minutes. Once a full MTU is recovered, we need to build the dictionary. A current implementation of the attack recovers IVs at a rate of 11.5 msec/IV, or 53.7 hours to recover all 2²⁴ IVs with a single host a fairly significant amount of time. However, building the dictionary is embarrassingly parallel and the total time to build the dictionary can be found by dividing 53.7 hours by the number of attacking hosts. Thus, an attacker using eight different hosts in the attack can reduce the time to around six hours something to worry about, especially because the time required is completely independent of the key size. In other words, it takes approximately six hours to build the dictionary (or seven hours total) for both 40- and 104-bit WEP keys.

Effects of Filtering IVs

A number of vendors are now filtering IVs to protect against the multiple open source implementations of the Fluhrer et al. attack (see Chapter 16). The most aggressive filtering reduces the IV space by 6 bits to 2¹⁸ (262,144) a significant reduction in IV space, and a significant reduction in the overall time of the inductive chosen plaintext attack. The reduction in time occurs only with building the dictionary so we still must take 42.8 minutes to recover a full MTU. But now instead of taking over 53 hours to build the dictionary with one attacking host, we can build the dictionary in 50.3 minutes a serious reduction in time and the size of the dictionary shrinks considerably as well.

Ironically, the countermeasure to one attack makes another attack significantly better better in some respects than the attack the countermeasure was designed to prevent.

Access Control

While the 1999 version of the IEEE 802.11 standard does not define a mechanism for access control, most implementations use MAC address-based access control lists. In addition, a major vendor has implemented a proprietary access control mechanism entitled Closed Network. This section describes the significant flaws found in each.

Problems with MAC-Based Access Control Lists

In theory, ACLs provide a reasonable level of security when we use a strong form of identity. Unfortunately, MAC addresses do not provide strong identity for two reasons. First, an attacker can easily observe MAC addresses because they must appear in the clear even when WEP is enabled. Second, some wireless cards allow their MAC address to be changed via software. As a result, an attacker can easily eavesdrop to determine valid MAC addresses and program the desired address into the wireless card, bypassing access control and gaining access to the network.

Problems with Proprietary Closed Network Access Control

In most IEEE 802.11 wireless networks, the access point broadcasts the network identity using a text string called SSID. This allows a mobile device to search for specific networks by listening to broadcasts called beacons. The idea of the closed network is to treat the network name or SSID as a secret so the mobile device must have prior knowledge of the SSID before connecting. In practice, security mechanisms based on a shared secret are robust, provided the secrets are well protected when in use and when distributed. Unfortunately, although the SSID can be hidden in the beacon, there are several other management messages in IEEE 802.11 that contain the network name in the clear. (The actual messages containing the SSID depend on the vendor of the access point.) As a result, an attacker can easily sniff the network name to determine the shared secret and gain access to the network. This flaw exists even with WEP-enabled networks because management frames are not protected.

Authentication

As previously discussed, the 1999 version of IEEE 802.11 provides only two forms of authentication. Obviously, the open method of authentication provides no security as all stations are permitted to associate. Unfortunately, although the shared-key authentication method was designed with security in mind, it is not secure.

Shared-Key Authentication

An attacker can easily exploit the original IEEE 802.11 shared-key authentication through a passive attack by eavesdropping on one leg of a mutual authentication. The attack works because of the protocol's fixed structure, wherein the only difference between authentication messages is the random challenge, and the weaknesses in WEP (Arbaugh et al., 2001; Arbaugh et al., 2002). The attacker first captures the second and third management messages from the authentication exchange. The second message contains the random challenge in the clear, while the third message contains the challenge encrypted with the shared authentication key. Because the attacker now knows the random challenge P, the encrypted challenge ciphertext C, and the public IV, the attacker can derive the pseudorandom stream produced using WEP^{K, IV}_PR, with the shared key K and the public initialization variable, IV, as shown below:

The recovered pseudorandom stream, WEP^{K, IV}_PR, is the same size as the authentication frame because all the frame's elements are known: algorithm number, sequence number, status code, element ID, length, and the challenge text. Furthermore, all but the challenge text will remain the same for all authentication responses. The attacker now has all of the elements to successfully authenticate to the target network without ever knowing the shared secret K. The attacker requests authentication of the AP it wishes to associate/join. The AP responds with an authentication challenge in the clear. The attacker uses the random challenge text R and the pseudorandom stream WEP^{K, IV}_PR to compute a valid authentication response frame body by XORing the two values together. The attacker then computes a new ICV, as described by Borisov et al. (2001). Finally, the attacker responds with a valid authentication response message and associates with the AP to join the network.