The Temporal Key Integrity Protocol (TKIP)

The first new link layer encryption protocol to be widely implemented was the Temporal Key Integrity Protocol (TKIP).[*] The major motivation for the development of TKIP was to upgrade the security of WEP-based hardware. Typically, chipsets capable of WEP offered hardware support for RC4 encryption. With the heavy lifting of encryption implemented in hardware, software and firmware upgrades make the rest possible. TKIP retains the basic architecture and operations of WEP because it was designed to be a software upgrade to WEP-based solutions.

[*] TKIP was initially called "WEP2" as it worked through the standards organizations. When WEP was shown to be fundamentally flawed, the protocol was renamed to try to distinguish it from WEP.

TKIP Differences from WEP

TKIP incorporates several new protocol features to defend WEP's weak points against attack. TKIP retains WEP's basic architecture and operation, but adds "safety belts" around WEP's most vulnerable points:

Key hierarchy and automatic key management

Rather than take the WEP approach of only a single master key that is used directly, TKIP uses master keys. The keys that are ultimately used to encrypt frames are derived from master keys. TKIP was also developed with key management operations so that master keys can be refreshed in a secure manner.

Per-frame keying

Although TKIP retains the RC4-based frame encryption of WEP, it derives a unique RC4 key for each frame (from the master key) to mitigate attacks against weak WEP keys. The process by which a unique key is derived for each key is called key mixing.

Sequence counter

By numbering each frame with a sequence number, out-of-order frames can be flagged, mitigating against reply attacks, in which attackers capture valid traffic and re-transmit it at a later time.

New message integrity check (MIC)

TKIP replaces WEP's linear hash with a more robust cryptographic integrity check hashing algorithm called Michael. More robust hashing makes it easier to detect frame forgeries. Additionally, the source address is among the items protected by the integrity check, which makes it possible to detect forged frames that claim to be from a particular source.

Countermeasures on message integrity check failures

TKIP was designed to be implemented on existing hardware, and suffers from a number of limitations. Michael can be compromised in an active attack with relative ease, so TKIP includes countermeasures to limit the damage from an active attack.

TKIP is also commonly used in tandem with key management protocols based on 802.1X, which enables the TKIP master keys to be derived from authentication transactions.

TKIP initialization vector use and key mixing

WEP's construction of WEP seeds from the initialization vector (IV) and the WEP key introduces major weaknesses. By simply concatenating the IV and the key to build the seed, the IV itself reveals a significant amount of key structure. Attackers can notice that IV re-use, and note that therefore, the key stream used to encrypt the frame is identical. With a 24-bit IV, the IV space lasts for 16 million frames. On a busy network, 16 million frames is not very many. To make matters worse, the IV space is specific to the scope of the key in use. On a network that uses static WEP, the IV space is shared by all stations on the network. Finally, and most famously, the IV is the initial 24 bits of the key, and makes WEP keys vulnerable to recovery with the Fluher/Mantin/Shamir attack discussed in Chapter 5.

To mitigate the attacks against initialization vectors, TKIP doubles the length of the IV from 24 to 48 bits. This increases the size of the initialization vector space from 16 million to 281 trillion, which effectively prevents exhausting the IV space during the limited lifetime of a key.

TKIP also performs key mixing to counter attacks against WEP. Key mixing changes the RC4 key used to encrypt each frame. Every frame in TKIP is encrypted with an RC4 key unique to that frame. Key mixing, which will be discussed in more detail later, further extends the initialization vector space. By incorporating the sender's MAC address into the mixing calculation, two stations can use the same initialization vector, yet still derive different RC4 keys to encrypt frames. Key mixing also helps to counter the Fluhrer/Mantin/Shamir attack. Successful application of the principles of the attack require a collection of "weak keys" with the same secret bits. By changing the key for every frame, TKIP prevents an attacker from gathering enough data to attack any of the per-frame keys.

TKIP sequence counter and replay protection

In addition to its larger size, the TKIP initialization vector serves as a sequence counter. When a new master key is installed, the initialization vector/sequence counter is set to one. Each frame transmitted increments the sequence counter by one.

To defend against replay attacks, TKIP maintains the most recent sequence counter value received from each station. When a frame is successfully received, the sequence counter is checked against the most recently received sequence counter. If it is larger than any previous value, the frame is accepted. If it is smaller than the most recently received sequence counter value, it is rejected.

Task group E is developing quality of service extensions. Current 802.11e drafts contain a block acknowledgment protocol feature that uses a single frame to acknowledge multiple transmissions. In the January 2005 draft of 802.11e, re-ordering due to block acknowledgments must complete before applying replay detection.

802.11 unicast frames must be acknowledged. If either the original frame or its acknowledgment is lost, the frame will be retransmitted. At the receiver, this may result in the same sequence counter being received twice. Duplicate sequence numbers may simply represent evidence of an error on the link and do not necessarily indicate an active attack in progress.

The Michael integrity check and countermeasures

WEP's integrity check is a linear hash value, which is totally unsuitable for cryptographic applications. One of the major design challenges faced by TKIP was strengthening the integrity check while retaining reasonable performance. Most 802.11 chipsets in use at the time TKIP was designed used a relatively low-power processor, and were thus not capable of performing mathematical operations fast enough to do integrity checks at "air-speed." Michael is implemented entirely with bitwise operations such as swaps, shifts, or even discarding bits. As a result, it can run without deleterious performance effects, even on the tiny microprocessors found in most 802.11 interfaces. (Michael is discussed in detail later in this chapter.)

The corollary to Michael's design is that it does not provide a great deal of security. It is significantly better than a cyclic redundancy check, but it does not offer security against a sustained and determined attack. TKIP incorporates countermeasures to detect and respond to an active attack by shutting down the network and refreshing the keys in use.

Michael's countermeasures are an admission of the weakness of the underlying cryptographic fundamentals. Design of Michael was constrained by the need to be backwards-compatible with most of the existing RC4-based hardware on the market. Michael's design is elegant and accomplishes a great deal within its severe design constraints, but it is still built on a foundation of sand. Time will tell whether Michael is sufficiently secure; I would not be surprised to see a major attack against it in the next year. However, the improved protocol design of TKIP limits the negative consequences of an attack. I expect that a compromise of Michael would result in denial-of-service attacks, but would not lead to wholesale network compromise.

TKIP Data Processing and Operation

Like WEP, TKIP provides support for encryption and integrity protection as part of the same process, as shown in Figure 7-1. TKIP's design as a set of safety features around WEP is quite clear from the diagram.

As input, TKIP takes the following items:

• The frame, naturally.
• A temporal key used to encrypt the frame.
• A MIC key used with Michael to protect the frame contents. TKIP derives a pair of keys so that the station-to-AP MIC key is different from the AP-to-station MIC key. One of the ways that TKIP differs from WEP is that the MIC uses a key.
• The transmitter address is used as an input to TKIP because it is required to perform origin authentication. The transmitter address is supplied with the frame and does not need to be supplied by higher level software.
• A sequence counter, maintained by the driver or the firmware.

Figure 7-1. TKIP frame processingencryption

TKIP key mixing and key construction

TKIP derives a unique key for each frame transmitted. The key is derived from the initialization vector/sequence counter, the address of the transmitter of the frame (which may not be the source of the frame), and the temporal key. Key mixing ensures that the key used varies significantly from one frame to the next, and prevents any attacks which assume that the secret component of the WEP key are constant from frame to frame. By including the transmitter address in the mixing computation, two stations can use the same initialization vector yet derive different two RC4 keys.

Limited processing power of the 802.11 controllers dictated the design of the key mixing function, which is shown in Figure 7-2. TKIP splits the computation of the mixed key into two phases. Phase one takes, as input, the transmitter address, the high-order 32 bits of the sequence counter, and the 128-bit temporal key. As output, it gives an 80-bit value. Although the computation is somewhat involved, it consists entirely of "easy" operations such as addition, shifts, and exclusive ORs, to reduce the computational load. The phase one value is constant as long as the 32 high-order bits of the sequence counter are constant, so it only needs to be computed once every 65,536 frames.

Phase two of the key mixing function must be computed for every frame. As input, phase two takes the phase one result, the temporal key, and the 16 low-order bits of the sequence counter. The only input that changes from frame to frame is the sequence counter. It changes in a well-defined way, so implementations can and do pre-compute values based on the next set of sequence counter values that will be needed as frames are queued for transmission.

Figure 7-2. TKIP key mixing

The output of the phase two of the key mixing process is a 128-bit RC4 key that can be used as a WEP seed. The 16 low-order bytes are used to generate a WEP IV. The middle byte of the WEP IV is constructed so that it avoids generating weak RC4 keys. Many 802.11 interfaces incorporate hardware assistance that can take an RC4 key as input and generate and apply the resulting keystream to encrypt the frame. The output of the phase two mixing process can be given directly to an 802.11 interface that supports this type of hardware assistance.

TKI P data transmission

When a frame is generated and sent to TKIP for transmission, the following sequence of events occur.

1. The 802.11 frame is queued for transmission. It consists of a frame header and the payload. Like WEP, TKIP protects only the payload of the 802.11 MAC, and leaves the 802.11 frame header, as well as any lower-layer headers, intact.
2. The Message Integrity Check (MIC) is computed. Unlike WEP, TKIP's MIC is a more robust cryptographic hash. It uses a secret key as part of its validation process, and protects much more than just the 802.11 frame payload. In addition to the frame data, the MIC incorporates the source and destination address as well as the addition of priority bits that will be used by the future 802.11e standard.
3. Sequence numbers are assigned to fragments. Unlike WEP initialization vectors, TKIP's sequence counter increases by one with each fragment. If no fragmentation is necessary, only one sequence counter increment will be necessary. In the case of multiple fragments, the counter will increment multiple times.
4. Each frame is encrypted with a unique per-frame WEP key. By carrying out the key mixing functions, TKIP derives the WEP key used for the frame. The per-frame key is passed to WEP as an IV plus a secret key; both components will change for every frame.
5. The frame plus Michael message integrity check value from step 2 and the RC4 key from step 4 are passed to WEP, which encapsulates the frame as described in Chapter 5. Note that this means that a TKIP-protected frame will include WEP components as well.

TKIP frames have WEP-like encapsulation. Figure 7-3 shows the encapsulation of a frame that has been protected by TKIP. The IV/KeyID is retained from WEP, but has a different interpretation. The first three bytes carry part of the TKIP sequence counter, and identify the key number in use. Although TKIP can support multiple keys, in practice, only KeyID 0 is distributed. An Extended IV (EIV) field is used to carry the remainder of the sequence counter. Following the data payload, TKIP appends the MIC. WEP adds its own integrity check value, to retain WEP in as unchanged a form as possible.

Figure 7-3. TKIP encapsulation

TKIP reception

When TKIP receives a frame, the encryption and transmission process must be reversed. TKIP's design as an expanded version of WEP adds several new checkpoints in the decryption process, and therefore it is worth treating in more detail. Figure 7-4 shows a block diagram, with all of the ways that frames may be discarded before passing up to higher protocol layers.

1. When a frame is received by the wireless interface and passes the frame check sequence to ensure it has not been corrupted, it is passed to TKIP for validation.
2. The first step TKIP takes is to check the sequence number to prevent replay attacks. TKIP's replay protection requires that frames be received in strict order. Frames that have a sequence number equal to or lower than the last received valid frame are discarded as a replay attempt. This is stricter than some other technologies, which maintain a replay window and allow "recent" arrivals to be somewhat out of order. For a link layer technology, however, it makes sense to insist on strict ordering because there is only a small possibility of out-of-order delivery on a single hop.
3. The WEP seed used to encrypt the packet is recovered. With the transmitter address, temporal key, and sequence counter, the receiver can unmix the key to recover the WEP seed.
4. With the WEP seed in hand, the outer WEP layer around the frame can be removed and the contents recovered. As part of this process, the WEP ICV is checked. Although it is a weak integrity check, it can be used to protect against applying countermeasures unnecessarily.
5. If fragmentation was applied, it may be necessary to wait for further frames to arrive before reassembling a complete payload. Fragmentation is not used often on 802.11, however.
6. Once the frame is reassembled, Michael is calculated over the contents of the frame. If the calculated MIC matches the MIC on the packet, the frame is passed to higher layers, and the sequence counter is set to the value of the sequence counter on the frame. If the MIC check fails, countermeasures are triggered.

Figure 7-4. TKIP reception process

One of the reasons for retaining the WEP encapsulation is that it enables greater backwards-compatibility with existing hardware. It also prevents unnecessary triggers of MIC failures. Frames that are corrupted due to noise on the radio link will likely fail either the 802.11 frame check sequence or the WEP integrity check value, and will be discarded before triggering a MIC failure.

The Michael Integrity Check

One of WEP's weakest points was the integrity check, which was supposed to ensure that the frame was not tampered with as it traversed the wireless medium. WEP adopted the cyclic redundancy check (CRC), which proved woefully inadequate. One of the major goals of TKIP was to design a message integrity check (MIC) with much more solid cryptographic underpinnings. The resulting algorithm, called Michael, is a compromise in many ways. Michael is stronger than a simple linear hash, but the desire of the standards committee to make it easy to implement with low overhead placed severe constraints on its design.

From an architectural point of view, Michael plugs in to the MAC service layer. That is, Michael operates on frames passed down to it from higher-layer protocols. Michael does not protect individual 802.11 frames; it protects the reassembled data unit given to 802.11 for transmission.[*] Part of the reason for implementing Michael above the MAC layer as opposed to within it is that it leaves products the flexibility to implement Michael in dedicated hardware or in driver software running on the device. Older chipsets and 802.11 interfaces did not build in specialized hardware assistance for Michael because it had not been developed; these products can implement Michael with updated drivers or host software. Newer devices designed with emerging standards in mind are able to build Michael support into the chipset if desired, and will not need driver support that is as extensive.

[*] In practice, the distinction between the MAC service layer and the MAC protocol layer is not particularly necessary. Although 802.11 can accommodate frames over 2,000 bytes, most commercial implementations limit frame size to be compatible with Ethernet to avoid higher-layer fragmentation.

Several attacks discussed previously served as the motivation for Michael. Two of the most notable are the bit flipping attack and a whole class of header modification. The former attack depends on the weak cryptographic properties of the CRC. As a linear hash algorithm, it is well known how changing the CRC input bits will change the output. Attackers could potentially flip bits in the frame to change its content, and change a bit in the WEP integrity check to compensate. In header modification attacks, malicious attackers may forge the source or transmitter address, or attempt to redirect frames by modifying the destination address.

Make no mistake, Michael is not a particularly secure cryptographic protocol. It was designed to offer breathing room to users who have an extensive installed base while they upgrade the security of their networks. It is only a short-term fix while the long-term solution is developed.

Michael data processing

Michael operates on higher-level frames passed down to the MAC. When a higher-level frame is queued for transmission, one of the first transmission steps is to compute the message integrity check (MIC) value. Michael operates on the input shown in Figure 7-5 (a). In addition to the destination address (DA) and source address (SA), Michael adds four zero bytes before the unencrypted data. The last three bytes are reserved; the first is a priority field that is reserved for future standardization work.

Michael operates on 32-bit blocks of data. Data is padded out with zeros so that it will be a multiple of 32-bit blocks. Padding is used only for the computation of the MIC. It is not transmitted. Michael computes the MIC value by working on successive 32-bit blocks of data.

Figure 7-5. Michael input

When complete, the MIC is added on to the tail of the data frame, and the data-plus-MIC is given to 802.11 for transmission. If it needs to be fragmented, it will be. During the fragmentation process, the MIC value may be split across multiple 802.11 fragments, which is acceptable. In Figure 7-5, the data-plus-MIC unit from higher layers requires fragmentation and is split across the frame boundary. This is a perfectly acceptable occurrence because the two fragments will be reassembled before validating the MIC. Figure 7-5 (b) illustrates this process. The input from Figure 7-5 (a) has been split into two frames for transmission. Each layer will get its own MAC and PLCP headers, and will be processed by the WEP layer in TKIP.

Michael countermeasures

Michael is not very resistant to attack, although it appears to be as good as one could hope, given the constraints of a great deal of legacy hardware on the market. Michael is not able to withstand a determined active attack, so it incorporates countermeasures against such attacks.

Countermeasures happen at the MIC check. To make it to that point, a frame must have passed through the replay protection and the WEP integrity check value validation. Forging a frame to pass the replay protection and the WEP integrity check is not a trivial matter, especially since the latter value depends on the value of the mixed per-frame key.

If an attacker were able to bypass replay protection and the WEP integrity check, it would be possible to mount a brute-force attack on the Michael integrity check. To guard against brute-force attempts to pass Michael, Michael's countermeasures shut down communications to limit the number of active attacks that can be made against any particular key. If an attack is sustained, countermeasures call for refreshing the key and shutting down communications.

When a station detects a MIC failure, it executes the following procedure:

1. The MIC failure is noted and logged. Before the MIC is validated, the frame must pass through the replay protection hurdle as well as the legacy WEP integrity check. Getting a frame to Michael for validation is not a trivial undertaking. Therefore, any MIC validation error is likely to be an extremely security-relevant matter that should be investigated by system administrators.
2. If the failure is the second one within a 60-second window, countermeasures dictate shutting down communications for a further 60 seconds. When the second MIC failure within 60 seconds is detected, all TKIP communication is disabled for 60 seconds. Instituting a communication blackout makes it impossible for an attacker to mount a sustained attack quickly.
3. Keys are refreshed. Stations delete their copies of the master keys and request new keys from the authenticator; authenticators are responsible for generating and distributing new keys.

Although 802.11i sets the Michael countermeasures time at 60 seconds, some vendors allow configuration of the Michael countermeasures window to other values.