WEP Keystream and Plaintext Recovery

There are two means of breaking WEP-encrypted data. The most obvious is to discover the key itself. The other is to discover all possible keystreams that a key can generate. This section deals with recovering and using keystreams. The section titled "WEP Key Recovery Attacks" deals with how to crack the keys. Attack Trees 3 and 4 (from earlier in this chapter) show that recovering the key or the keystream enables reading and writing of encrypted data.

RC4 encryption involves XORing the keystream (K) with the plaintext (P) data to produce the ciphertext (C). If an attacker knows any two of these three elements, he can calculate the third. An attacker can always know C because it is broadcast. Thus, if an attacker knows P, he can get K. After he has K, he can recover P in future jackets.

Keystream Dictionaries

The security of RC4, which is the underlying encryption method in WEP, depends in part on not repeating the same keystream. WEP does this by using the initialization vector (IV) to permit 2²⁴ (about 16 million) possible keystreams for each key. As previously mentioned, an alternative to breaking the key is to break each of the keystreams. One method is to wait for repeated keystreams, known as a collision, which reveals information about the data and the keystream. Another method is to know some or all of the data that was encrypted, called a known plaintext attack. After an attacker has built up a dictionary of all 16 million keystreams, he can then decrypt anything that is sent using that WEP key. A dictionary of all keystreams that are 1500 bytes long only takes about 24 GB to store, which easily fits on a laptop hard drive. No tools, as of yet, can implement this attack. Fortunately, as the per-packet key algorithms in WPA and 802.11i become more widely implemented, the usefulness of this attack might disappear before a tool is written.

Methods for Recovering RC4 Keystreams

There are several techniques for recovering keystreams and building keystream dictionaries. The attacks that this section describes have fortunately only been practiced in the academic world. No real-world tool has yet implemented them. The likely reason is that tools that attack and recover the key itself have been more practical and perhaps easier to implement.

Known Plaintext Attack

The simplest method of recovering keystreams is the known plaintext attack. The attacker sends data over a wired network to a machine on the wireless network. The AP encrypts it and sends it to the client. The attacker captures the encrypted wireless traffic. Finally, the attacker can apply the XOR operation to the plaintext and the captured traffic and recover the keystream. There are many ways to get known plaintext sent to a wireless user, from sending ping packets to sending e-mails to getting a user to visit a known website. Because the attacker knows the content of each message, he can match it with the encrypted traffic and recover the keystreams used to encrypt it. An attacker can send data rapidly to build up his keystream dictionary. Figure 6-7 illustrates the known plaintext attack.

IV Collisions and the Birthday Paradox

The birthday paradox refers to the seemingly counterintuitive idea that if you have a room of 23 people, chances are greater than 50 percent that two of them have the same birthday (month and day). By the time you get to 50 people, the chances rise to 97 percent. This result arises from the difficulty of adding random birth dates to a list without "colliding with" one of the birth dates already on the list.

A similar concept applies to the avoidance of repeating an IV. After a small fraction of the possible IVs have already been broadcast, it becomes difficult for a random algorithm not to rebroadcast one. When you do have an IV collision, it is relatively easy to compromise the data in those two packets. It takes some cryptographic techniques, but it is considered an easy problem for a computer. If the data is compromised, the keystream corresponding to that IV can also be compromised. This can help an attacker build up a dictionary of keystreams.

The cards of several manufacturers use IVs that start at 0 and increase by 1 with each packet. These cards reset to 0 each time they lose power, which can be quite frequent on a laptop. Thus, it is virtually guaranteed that the first few thousand IVs will be reused at least once per day. It is not difficult for an attacker to build up a dictionary of these IVs.

A partial solution that avoids both the birthday paradox and the reset problem is to start at a random number on power-up and then count sequentially up. 802.11i solves these problems by replacing the IV with a longer sequence number, counting sequentially, and forbidding repeated sequence numbers.

Reaction Attack

Nikita Borisov and his colleagues at Berkeley discovered an interesting flaw in WEP based on the insecure checksum that 802.11 uses. This attack assumes that an attacker can guess some of the bits in a message, and it allows him to determine the value of the bits he does not know. Given the highly predictable nature of certain fields of TCP/IP packets, an attacker usually know some bits in the message. The attacker then flips certain bits in the message, rebroadcasts it, and views whether the packet had a valid TCP checksum by looking for a recognizably short, encrypted TCP acknowledgement (ACK) packet. Although encrypted, an ACK packet can be recognized by its length. By flipping selected bits, the attacker can deduce whether other bits were 0 or 1 by the absence or presence of an ACK response. By repeating this procedure, some or all of the keystream for a particular IV can be recovered. This is known as a reaction attack.

Inductive Attack

One of the more ingenious methods of recovering keystreams relies on methodical trial and error. Bill Arbaugh's inductive attack relies on WEP to serve as an oracle to tell the attacker when she correctly guesses parts of the keystream. The attack is a method for extending a chunk of known keystream for a given IV.

Assume that an attacker starts with a given amount, n, of keystream (K) for a given IV and a given WEP key. She can obtain this initial K by watching for an easily guessed packet, such as a DHCP request, or by conducting a known plaintext attack. Now the attacker begins the inductive attack. She creates a packet such as an ICMP ping packet or ARP request that demands a reply. She chooses the length of her packet, including the 802.11 checksum, to be n+1. But the attacker only has n bytes of keystream, so she must guess the n+1st byte. She does this by sending 256 versions of the packet with all possibilities for that last byte. The AP silently discards the incorrect ones. But the correct one has the proper encrypted checksum, and the AP accepts it and responds. The attacker now knows which was correct and knows n+1 bytes of keystream. She can repeat this process until she knows a full-length (1500-byte) keystream for that IV. Figure 6-8 illustrates one round of this process.

As you can see, the insecure ICV enables bit-flipping attacks. These enable the reaction and inductive attacks. Plaintext attacks and reuse of keystreams from IV collisions allow an attacker to recover keystream fragments and build up keystream dictionaries.

Uses for Recovered Keystreams

Now that an attacker has recovered the keystreams relating to one or more IVs, how can he use them?

Traffic Injection: Choosing Your Own IVs

In legacy systems not using WPA or 802.11i, an attacker only needs one keystream to inject packets. This is because the original 802.11 specification unfortunately allows a sender to choose his own IV and does not prohibit reuse of IVs. So an attacker can just repeatedly reuse the same IV for which he has the keystream and inject an unlimited number of packets into a network. Fortunately, some vendors, including Cisco, have implemented mechanisms that reject repeated IVs. Message integrity check algorithms, described in Chapter 8, also solve this problem.

Message Modification and Replay

A slightly weaker form of injection attack is possible if an attacker cannot get an entire keystream. This attack is called message modification, also known as a bit-flipping attack. Because the ICV can be recalculated even in its encrypted form, an attacker can take a message that he can only partially understand, flip arbitrary bits, and recalculate a proper ICV. He can then rebroadcast the message, and it is valid. An application of this attack might be for an attacker to try to change the destination IP address of a message so that it goes to his own machine instead of its intended recipient. He will then receive the entire packet, unencrypted, via a wired interface!

Another application might be to capture a single TCP SYN packet and rebroadcast it many times as a SYN flood, changing a few parameters for each packet. He could not just rebroadcast the packets unmodified because they would be dropped as duplicates. Because TCP has a fixed header, the attacker knows where in the packet the appropriate fields are and can randomly flip bits in those fields to create different legitimate packets.

An attacker who has no information about the keystream can still do a packet replay attack. He does this by simply capturing and rebroadcasting one or more packets. This attack is unlikely to do much, especially in protocols such as TCP that are designed to prevent repeated packets. However, in some protocols such as UDP, sending the same packet multiple times can have a meaning and can tie up resources on the destination machine. An attacker might be able to use this attack to affect machines on wired networks that communicate with the wireless network.

Decryption

To decrypt packets from keystreams, an attacker needs a dictionary of most or all keystreams. His ability to decrypt the packets is proportional to the completeness of his keystream dictionary for that WEP key. After the attacker has a complete dictionary, he can decrypt every packet sent with that WEP key. This is equivalent to having the WEP key itself. A sophisticated attacker could capture packets, hoping to compromise the keystream in the future. If he does compromise it, he can then go back and decrypt packets from his historical cache.

A Brief Note on Solutions

Fortunately, many of these attacks are becoming obsolete with mechanisms that Cisco and other vendors have implemented. A keyed message integrity check (MIC) eliminates traffic injection and the inductive and reaction attacks. Mechanisms that avoid IV reuse prevent collisions and thus make keystream dictionaries useless. The disadvantage is that after the maximum of 2²⁴ packets has been sent, the WEP key must be changed because the IVs are all used up. WPA and 802.11i include a MIC and a longer IV. These solutions are described in Chapter 8.