Battered, but not broken: understanding the WPA crack

Finding a slim vector

Academic researchers have found an exploitable hole in a popular form of wireless networking encryption. The hole is in a part of 802.11i that forms the basis of WiFi Protected Access (WPA), so it could affect routers worldwide. German graduate student Erik Tews will present a paper at next week's PacSec in Tokyo coauthored with fellow student and aircrack-ng team member Martin Beck that reveals how remnants of WPA's predecessor allow them to slip a knife into a crack in the encryption scheme and send bogus data to an unsuspecting WiFi client.

In an interview from Germany, where he is a PhD candidate studying encryption at the Technical University of Darmstadt, Tews explained that an existing attack on Wired Equivalent Privacy (WEP) was modified to provide a slim vector for sending arbitrary data to networks that use the Temporal Key Integrity Protocol (TKIP). (Tews' collaborator Beck is a student at the Technical University of Dresden; Tews credits Beck with the discovery, after which they jointly developed the paper that Tews will present at PacSec.)

With the Tews/Beck method, an attacker sniffs a packet, makes minor modifications to affect the checksum, and checks the results by sending the packet back to the access point. "It's not a key recovery attack," Tews said, "It just allows you to do the decryption of individual packets." This approach works only with short packets, but could allow ARP (Address Resolution Protocol) poisoning and possibly DNS (Domain Name Service) spoofing or poisoning.

The paper, Practical Attacks against WEP and WPA, is now available for download.

A history of encryption weakness

The 802.11b specification from the IEEE engineering standards group came with a basic encryption mechanism built in to assuage worries that data would simply be sent in the clear. Wired Equivalent Privacy (WEP) had as its goal a simple baseline: be as secure as an Ethernet jack. It quickly failed. Cracks were seen in 2001, and it was thoroughly broken as early as 2004. Some researchers claim to be able to recover a WEP key in under a minute from an active network. (Most corporations relied on virtual private network connections, which were tunneled through access points located outside a strong firewall, to allow WiFi use without compromising the network.)

The 802.11i task group was formed to replace WEP with something stronger, and they came up with two separate solutions: one looking backwards, the other forwards. Looking back, 802.11i encompassed all WiFi devices ever shipped—starting in 1999—with TKIP. TKIP could be retrofitted to work with older cards through firmware and driver updates. The TKIP work was done first, and incorporated into a branded standard called WPA by the Wi-Fi Alliance, the organization that certifies WiFi gear for interoperability. (You can make 802.11 devices til the cows come home, but you have to be a member of the trade group and pay testing fees—and pass the tests—to label a device with the WiFi moniker.)

The 802.11i group also added Advanced Encryption System (AES) support—the AES-128 flavor—which uses, take a breath, the Counter Mode with CBC-MAC (Cipher Block Chaining Message Authentication Code) Protocol or CCMP. This flavor of AES both encrypts data and ensures its integrity. The flaw discovered by Tews and Beck cannot work against AES.

When 802.11i started winding down, the Wi-Fi Alliance updated its WPA standard to WPA2. WPA includes a requirement for just TKIP encryption; WPA2 requires support for both TKIP and AES. Almost all gear shipped starting in late 2002 could be upgraded to work with AES—all 802.11g silicon was prepared knowing that AES was coming along—and the Wi-Fi Alliance added mandatory WPA2 support for WiFi certified devices starting in March 2006.

The backwards-looking part of 802.11i is where the standard gets into trouble, according to Tews and Beck's research. By making the WPA algorithm compatible with hardware that could handle the broken WEP algorithm, the WiFi alliance left a tiny gap that the researchers could exploit.

Crack that WEP: chop, chop!

The flaw in TKIP has to do with checksums, which are used to ensure the integrity and accuracy of data. Checksums work by taking a sequence of numbers that are to be transmitted, applying a transformation to produce a short result, and appending that result to the transmission.

For instance, an ISBN that starts with 978 is 13 digits long, 12 of which represent a unique book number. The 13th is a base 10 number derived from alternately multiplying successive digits by 1 or 3, adding the results, and taking the modulo of 10. If you type in an ISBN incorrectly, a system that recalculates the checksum can determine in many cases if digits are swapped or wrong digits are entered.

With wireless transmission, the odds of missing a bit or getting it wrong are relatively high, and checksums are used both to determine whether there was an error in reception and to ensure the integrity of a packet. If the payload changes and the checksum does not, then a receiver can tell that the packet was tampered with.

This fell apart in WEP, because the checksum was so weak that techniques were developed to allow the data in a packet to be changed and a new checksum calculated. Tews mentioned the tool chopchop, which allows individual packets to be decrypted without cracking a WEP key. This program served as part of the wedge for the exploit.

Chopchop works by "chopping" out one byte of data at a time and substituting different values for that byte while calculating a new potential checksum. Chopchop sends each modified packet to an access point, and the AP rejects packets for which the decrypted checksum is invalid. WEP doesn't prevent endless testing in this manner—there's no flood control or other protection.

TKIP added a second layer of integrity through Message Integrity Code (MIC), nicknamed Michael. Michael performs a better-designed checksum that's also encrypted. To prevent the simplicity of chopchop, a client will respond after it receives two bad Michael checksums within 60 seconds: the client shuts down for 60 seconds and then requests a new key exchange with the AP. An AP, faced with the same situation, also shuts down for 60 seconds, then rekeys every client. (802.11i allows new master keys to be created on demand without changing the starting passphrase or network key.)

Here's where Tews said his colleague Beck got extremely clever: because both the WEP and TKIP mechanisms are used one after another, and because the Michael code is contained within the packet that's checksummed by the weaker WEP method, an attempt to crack a packet can first use chopchop without triggering the Michael countermeasures.