Wired Equivalent Privacy
IEEE 802.11 Standard
The IEEE 802.11 standard that 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 layers (Physical & Media Access Control) is kown 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 into 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 wirless 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 generater 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 integrety 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 by using the 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 reciever 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 ciphertext. This ciphertext 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 ciphertext 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 keystream 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 keystream to calculate the ciphertext. Now the encrypted message is ready to be sent to the receiver. Because the reciever 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.
Dencoding
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 ciphertext 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.
Multiple Key Byte Extension
Using Klein's attack it is possible to completely revover all bytes of the secret key if enought 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 IV and 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 keystream 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 lenght 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 keystream. Since the ARP protocol has no protection against reinjection an attacker can write a captured ARP request back to the network which results in another ARP response. If an access point is involved the access point relays this packet and generates one more packet. All these responses to the injected ARP request can be used by the attacker to recover the first bytes of the key streams.
To successfully recover a 104 bit WEP key there are 40.000 packets needed for a success probability of 50% and 85.000 packets having a success probability of 95%. Depending on the network this can usually be accomplished in less than a minute.