Wired Equivalent Privacy

Overview

WEP (Wired Equivalent Privacy) is a standard to secure wireless networks. Wireless networks are generally insecure due to physical reasons: the reception area is a sphere around the sender, therefore traffic is by default public to everyone within the sphere, wanted and unwanted listeners.

According to a paper by Erik Tews, Ralf-Philipp Weinmann and Andrei Pyshkin of the Technical University Darmstadt it is possible to retrieve WEP passwords within one minute.

Introduction

The WEP standard was ratified in September 1999 by the IEEE as 802.11. It contains two variants, one with 64-bit keys (3 byte initialization vector, 40-bit effective key length) and 128-bit keys (3 byte initialization vector, 104-bit effective key length). The 64-bit encryption was planned for slow computers and the 128-bit one for high security.

In 2001 Fluhrer, Mantin and Shamir presented an attack against RC4, which is the stream cipher being used in WEP, but for this attack specific IVs (initialisation vectors) were needed.

In 2004 Stubblefield, Ioannidis and Rubin applied this attack to the WEP standard and with approximately 4 million packets the key could be retreived.

In consequence WEP+ (WEP-plus) was introduced avoiding those "weak" IVs but it never found its way to being commonly used. In 2007 Klein improved the RC4 attack so that it works regardless of the IVs being used.

Although WEP being known as insecure, (not representative) statistics in middle Germany show that WEP is still the most commonly used WLAN-protection.

IEEE 802.11 Standard

The IEEE 802.11 standard was published 1997 by the Institute of Electrical and Electronics Engineers (IEEE). The standard specifies the two lowest layers of the OSI (Open System Interconnection) model for local wireless networks. This specification of the two lowest layers (Physical & Media Access Control) is known as WLAN or WIFI. Common protocols like the TCP/IP or ARP operate on top of these two layers.

Basic Service Set

A WLAN consists of a minimum of two communication partners, also called stations. These stations can communicate with each other using electro-magnetic waves, that have a scope of 20m – 300m. This communication area is known as Basic Service Set (BSS). In order to increase the scope of a wireless network, it is common to introduce access points to the network. These access points relay the traffic from stations and thereby increase the overall communication scope. Anyone in the scope of the Basic Service Set can listen to the traffic of the wireless network.

Packet Design

The first part of a packet is unencrypted and contains the 802.11 header, the basic service set identifier, an initialization vector chosen by the sender of the packet and the destination hardware address. The initialization vector is transmitted unencrypted, because it is used along with a secret password to initialize a pseudo number generator. The receiver of the packet only knows the secret password, and must be able to initialize the pseudo random number generator with the same value the sender did.

The second part of the packet is encrypted and carries the data of the above protocols like TCP/IP or ARP, as well as an CRC32 integrity check value.

The following picture illustrates the design of WEP packet.

Packet Encryption & Decryption

Because anyone can listen to the communication of a wireless network, the IEEE 802.11 includes a cryptographic method to secure the communication between stations and access points. To prevent unauthorized access to the network, all packets sent between the communication partners are encrypted. The encryption and decryption of packets is done using a stream cipher which is explained in the following sections.

Stream Cipher

The stream cipher is used to to encrypt and decrypt packets of arbitrary length. In order to communicate with each other, the sender and receiver have to generate key streams for each packet. The sender uses the XOR operation on the unencrypted packet and the key stream to generate the cipher text. This cipher text is sent over the network to the receiver. The receiver on the other side has to generate the same key stream the sender used to encrypt the message. Using the XOR operation again on the cipher text and the generated key stream results in the plain text.

Encoding

All communication partners that have access to the wireless network share the same secret key KBSS, which is used to generate the key stream. If only the secret key KBSS would be used to generate the key stream for a packet, packets with the same content would have the same encrypted representation. Therefore the sender calculates a packet key by choosing a different random initialization vector, appended by the secret key KBSS for each packet. This packet key is then used as a seed to initialize the pseudo number generator PRNG, that generates for the same seed always the same key stream. A CRC32 checksum for the plain text is appended to the original message. The message is XOR'ed with the key stream to calculate the cipher text. Now the encrypted message is ready to be sent to the receiver. Because the receiver also needs to know the initialization vector to compute the seed for the pseudo number generator, the encrypted message is sent with the unencrypted initialization vector to the receiver.

Decoding

When the receiver gets an encrypted packet, the unencrypted initialization vector is read from the packet to build the seed for the pseudo number generator along with the secret key KBSS. This seed is the same one the sender used to initialize the pseudo number generator. Then the cipher text gets XOR'ed with the key stream from the pseudo number generator, which results in the plain text message. A CRC32 checksum is calculated from the unencrypted message and verified against the checksum sent with the packet to ensure the packet has not been modified or corrupted.

RC4

RC4 is a widely used stream cipher invented by Ron Rivest of RSA Security in 1987. It takes a key of arbitrary length up to 256 byte and produces a pseudo-random keystream of unlimited length. RC4 can be described as a machine with internal states being defined by an 256-byte-array and two single bytes acting as pointers to elements of the array.

For every packet RC4 is newly initialized as the key (IV+KBSS) differs from packet to packet. The initalisation of RC4 creates a permutation of the array S[ ] based on the packet key according to the following algorithm:

Finally the packet's content is XOR'ed with the generated key stream as described in point 6.2.. Each generation of one byte for the key stream changes the internal state of the RC4 (to be exact, it permutes the internal array) according to the following algorithm:

Here, n is 256

Klein's attack

Klein's attack on RC4 is based on the fact, that only the (public) IV changes, but the secret root key K^BSS is fixed. Therefore the packet keys are similar to a certain extend.

K is the packet key, X is the packet key stream and we have m bytes

According to permutation theory the following can be observed: If we have the first i bytes of the packet key and the i-th byte of the key stream, we have a (higher than random) chance to calculate the (i+1)th byte of the packet key.

Multiple Key Byte Extension

Using Klein's attack it is possible to completely recover all bytes of the secret key if enough samples are available. However this attack has the following two disadvantages:

For each key byte all initialization vectors and all key streams have to be processed, which is very expensive.
Because the attack is based on some statistics and assumptions, it is possible to recover a key byte that is not correct. If this happens all key bytes after this falsely guessed key byte are also wrong and have to be recomputed.

Tews, Weinmann & Pyshkin improved the attack presented by Klein to be able to compute the secret key bytes independently from each other, which significantly reduces the overall computation time. They developed an approximation so the recovery algorithm only depends on the first three key bytes, which is the unencrypted initialization vector and is always known. Using this approximation together with a key ranking method & an error correction function for strong keys they are able to recover the correct key.

The Link Layer Control & ARP Header Problem

The above attack on the RC4 algorithm assumes that not only the initialization vector, but also some bytes from the key stream are known to an attacker. These key stream bytes are collected by exploiting another weakness in the protocol. In most networks the TCP/IP and ARP protocols are used for communication. If a station wants to connect to another computer using TCP/IP it has to know the hardware address of the communication partner. The ARP protocol is used to discover hardware addresses for given internet addresses. So if a sender wants to send something to another station and doesn't know the hardware address of the receiver, it first has to send an ARP request to the hardware broadcast address. The station with the requested internet address replies to this request with an ARP response telling the sender it's internet address.

These ARP requests and responses are packed into the encrypted data section of a WEP packet. The problem hereby is, that the length of a packet is not masked by the encryption, and that the ARP requests and responses, as well as the link layer headers are always fixed. This enables an attacker to identify encrypted ARP packets by it's length. XOR'ing these encrypted packets with the fixed protocol header values the attacker is able to extract the first 16 bytes of the key stream. Since the ARP protocol has no protection against re-injection an attacker can write a captured ARP request back to the network which results in another (or two, if an access point is involved) ARP response. All these responses to the injected ARP request can be used by the attacker to recover the first bytes of the key streams.