Cryptographic Background to WEP

Before discussing the design of WEP, it's necessary to cover some basic cryptographic concepts. I am not a cryptographer, and a detailed discussion of the cryptography involved would not be appropriate in this book, so this chapter is necessarily brief.[*]

[*] Readers interested in more detailed explanations of the cryptographic algorithms involved should consult Applied Cryptography by Bruce Schneier (Wiley, 1996).

To protect data, WEP requires the use of the RC4 cipher, which is a symmetric (secret-key) stream cipher. RC4 shares a number of properties with all stream ciphers. Generally speaking, a stream cipher uses a stream of bits, called the keystream. The keystream is then combined with the message to produce the ciphertext. To recover the original message, the receiver processes the ciphertext with an identical keystream. RC4 uses the exclusive OR (XOR) operation to combine the keystream and the ciphertext. Figure 5-1 illustrates the process.

Figure 5-1. Generic stream cipher operation

Most stream ciphers operate by taking a relatively short secret key and expanding it into a pseudorandom keystream the same length as the message. This process is illustrated in Figure 5-2. The pseudorandom number generator (PRNG) is a set of rules used to expand the key into a keystream. To recover the data, both sides must share the same secret key and use the same algorithm to expand the key into a pseudorandom sequence.

Because the security of a stream cipher rests entirely on the randomness of the keystream, the design of the key-to-keystream expansion is of the utmost importance. When RC4 was selected by the 802.11 working group, it appeared to be quite secure. But once RC4 was selected as the ciphering engine of WEP, it spurred research that ultimately found an exploitable flaw in the RC4 cipher that will be discussed later.

Figure 5-2. Keyed stream cipher operation

 

Stream Cipher Security

A totally random keystream is called a one-time pad and is the only known encryption scheme that is mathematically proven to protect against certain types of attacks. One-time pads are not commonly used because the keystream must be perfectly random and the same length as the data that will be protected, and it can never be reused.

Attackers are not limited to attacking the underlying cipher. They can choose to exploit any weak point in a cryptographic system. One famous Western intelligence effort, code-named VENONA, broke Soviet messages encrypted with one-time pads that were reused.[*] It is easy to understand the temptation to reuse the one-time pads. Huge volumes of keying material are necessary to protect even a small amount of data, and those keying pads must be securely distributed, which in practice proves to be a major challenge. One data bit must have a corresponding one-time pad bit. A 54 Mbps network can move about 25 Mbps of user data. If the network operates at just 10% of that capacity, the data transfer in an 8-hour workday is still 9 gigabytes. Distributing multiple gigabytes of keying material to every access point is totally impractical.

[*] The United States National Security Agency has made some information on the project public at http://www.nsa.gov/docs/venona.

Stream ciphers are a compromise between security and practicality. The perfect randomness (and perfect security) of a one-time pad is attractive, but the practical difficulties and cost incurred in generating and distributing the keying material is worthwhile only for short messages that require the utmost security. Stream ciphers use a less random keystream but one that is random enough for most applications.

Cryptographic Politics

No discussion of cryptography would be complete without a passing reference to some of the many legal and regulatory concerns surrounding its use. Three major issues impinge upon the use of WEP, though the effect of these issues has diminished over time.

WEP requires the use of the RC4 cipher to encrypt the frame. When the first edition of this book was written, WEP was optional and not incorporated into all products. Host software could incorporate RC4 code, but open source projects had concerns about including code that infringed on the intellectual property of RSA Security, Inc. In the time since the first edition was published, this concern has faded into the background. All the major chipset vendors have licensed RC4 encryption and incorporated hardware support for RC4 into 802.11 chipsets. Device drivers are responsible for pushing WEP keys down to the hardware. Performing encryption in hardware on the card means that software no longer needs to risk infringing on RSA's intellectual property.

WEP was initially designed with short keys to satisfy the U.S. export regulations regarding cryptographic products. Initially, the standard required short 40-bit keys, but every product on the market supports at least 104-bit keys now. For a brief time, long keys looked like an important extension to the standard, though the additional security proved illusory.

Finally, some governments strictly regulate the use of any cryptographic system, WEP included. In addition to United States export regulations, many countries have import regulations that restrict importing cryptographic equipment. Other governments are also free to require additional cryptographic measures. The government of China has developed an alternative security system called WLAN Authentication and Privacy Infrastructure (WAPI), and has made it optional for wireless LAN equipment sold in China.