IEEE 802.11 Wi-Fi LANs are designed to allow multiple devices to communicate. In practice, this means a group of mobile devices must share the radio channel and communicate with a single access point. Many LANs provide shared access. For example, conventional Ethernet LAN workstations share the wiring by transmitting one at a time and trying to avoid collisions. For efficiency, most shared LANs also provide the capability for one workstation to send data simultaneously to several others. Data sent between two workstations is called unicast and data sent from one to multiple workstations is called multicast; the case in which one workstation sends to all the others is a special case of multicast called broadcast. Multicast and unicast messages have different security characteristics.

Unicast data sent between two parties needs to be private to those two parties. This is best accomplished by using a specific key for each pair of devices communicating. We call this a pairwise key; usually it protects communication between a mobile device and the access point. This means that each mobile device needs to store one pairwise key, and the access point needs a set of pairwise keys—one for each mobile device that is associated.

By contrast, broadcast (or multicast) data must be received by multiple parties who form a trusted group. Therefore, a key must be shared by all the members of that trusted group. This is called the group key. Each trusted mobile device and the access point need to know a single group key. The concept of pairwise and group keys is shown in Figure 10.1.

Figure 10.1. Pairwise and Group Keys

The methods of managing the pairwise keys and the group keys are somewhat different so we define each as a separate key hierarchy. We refer to the pairwise key hierarchy to describe all the keys used between a pair of devices (one of which is usually the access point) and the group key hierarchy to describe the various keys shared by all the devices.

The next important terms are preshared keys and server-based keys. As the name suggests, preshared keys are installed in the access point and in the mobile device by some method outside WPA/RSN. It could be that you phone up a user and tell him the password, or send him a letter that he has to eat after reading or whatever eccentric method you choose. Most WEP systems use preshared keys—it is the responsibility of the user to get the keys delivered to the two parties who want to communicate. Preshared keys bypass the concept of upper-layer authentication completely; you are assumed to be authentic simply by proving possession of the key.

The alternative, server-based keys, requires an upper-layer authentication process that allows the mobile device and an authentication server to generate matching secret keys. The authentication sever arranges for the access point to get a copy for use in session protection. It has the major advantage that the operator can keep a single key database that can be used in conjunction with many access points. When a new employee joins, for example, the administrator has to update only one database.

Preshared keys are easier to implement in small networks. Most older WEP systems only supported preshared group keys.

The pairwise key hierarchy is the most complicated, so let's review that first. The hierarchy starts at the top with a pairwise master key (PMK) delivered from the upper-layer authentication server or with a preshared key. Let's put preshared keys aside for the moment and look at the server-key approach. The PMK is the top of the pairwise key hierarchy. There is a different PMK for each mobile device, and from this all other pairwise keys are derived. The following paragraphs show how the PMK is created and how it is used to generate the actual keys used in encryption.

Computing the Temporal Keys

In your enthusiasm to get encryption turned on, you might think at this stage that we are ready to slot the PMK into the encryption engine and get going. But we have a long way to go yet before we reach that stage. That is why it is called a hierarchy! The PMK is not used directly for any security operations. Instead it is used to derive a separate set of keys that will be used in protecting a link between two devices (for example, between the access point and a mobile device). Four separate keys are needed to do the job because there are two layers to protect—the EAPOL handshake and the user's data—and two cryptographic functions at each layer: encryption and integrity.^[1]

• Data Encryption key (128 bits)

• Data Integrity key (128 bits)

• EAPOL-Key Encryption key (128 bits)

• EAPOL-Key Integrity key (128 bits)

These are referred to as the temporal keys because they are recomputed every time a mobile device associates to the access point. The collection of all four keys together is referred to as the pairwise transient key (PTK). For RSN/TKIP and WPA, each of these keys must be 128 bits long so that the PTK is a total of 512 bits long.

The first two temporal keys sound familiar. They are the ones used to encrypt the data and protect it from modification. The second two we have not seen before. These are used to protect the communications between the access point and mobile device during the initial handshake.^[2] For the moment, just accept that these EAPOL keys are needed; we will discuss them again shortly.

Because the temporal keys are recomputed each time a mobile device connects, there has to be something that changes when the computation is done; otherwise, you'd end up with the same temporal keys every time. This is called adding liveness to the keys, ensuring that old keys no longer work. Liveness is achieved by including a couple of special values called nonces in the computation. The value of the nonce is quite arbitrary except in one respect: a nonce value is never used twice^[3] with the same key. The word “nonce” can be thought of as “N – once”—in other words, a value (N) only used once.^[4] They say lightning never strikes in the same place twice (which is not true) and similarly nonces never come up with the same value twice (which should be true by design).

The temporal keys are effectively shared between the two devices because both ends of the link compute an identical copy. It is not enough for one device to include its own nonce value. Each device must generate a nonce, pass its nonce to the other device, and then derive the temporal keys by including both nonces in the computation. Also, to make sure the identity of the two devices is bound into the keys, the MAC address of each is included in the computation. Figure 10.2 summarizes the process and shows the inputs to the temporal key computation and the four output keys. The inputs are the PMK, a nonce from each side, and the MAC address of each side. The outputs are four 128-bit keys. How the “key computation block” is implemented is described later.

Figure 10.2. Temporal Key Computation

IEEE 802.11 supports multicast and broadcast messages. One example in which multicast is useful is video distribution. If you want to send a live broadcast to many stations, you don't want to have to send to each station individually—you want to transmit one copy on the LAN and allow all the relevant stations to receive the video frames. This is an example of group multicast. A special case of multicast is broadcast, in which the message is sent to all devices on the LAN. Broadcasts are used widely in LAN protocols.

In an infrastructure network (that is, a network using an access point), multicasts are only sent from the access point to the mobile devices. Mobile devices are not allowed to send broadcasts directly; however, they can initiate a broadcast by sending the message to the access point, which then broadcasts it on the station's behalf (to both the wireless devices and any attached wired LAN). On the wireless side, we want multicasts and broadcasts to be encrypted and protected from tampering.

We cannot use the pairwise keys for broadcasts. Each mobile device has a different set of pairwise keys so it would be necessary to send multiple copies of the broadcast, each encrypted differently. While this would work, it would completely defeat the advantage of the multicast message. Therefore, a separate key hierarchy is maintained specifically for use in encrypting multicasts. This is called the group key hierarchy.

Unlike pairwise keys, all the mobile devices and the access point share a single set of group keys. This allows all the stations to decrypt a multicast message sent from the access point. While this solves a problem, it also creates one: how to handle the case in which a mobile station leaves the network.

If a mobile device chooses to leave the Wi-Fi LAN, it should notify the access point by sending an IEEE 802.11 disassociate message. When it does this, the access point erases the copy of the pairwise keys for the departing mobile device and stops sending it messages. If the device wants to rejoin later, it must go through the whole key establishment phase from scratch. But what about the group key? Even though the device has left the network, it can still receive and decrypt the multicasts that are sent because it still has a valid group key available. This is not acceptable from a security standpoint; if a device leaves the network, it should no longer be allowed any access at all.

The solution to this problem is to change the group key when a device leaves the network. This is a bit like changing the locks on your house after a long-term guest leaves; you don't want anyone to have a door key who is not living in your house. So group keys have an added complication: the need to rekey.

Negotiating the pairwise keys was complicated because we had to start with no secure connection in place and we ran the risk of all sorts of attacks from simple snooping to message forgery. The situation for group keys is easier because we can wait until the pairwise keys are established and then use the secure link to send the group key value. This provides a significant simplification and means that the actual group key values can be sent directly to each station without concern about interception or modification. Group key distribution is done using EAPOL-Key messages, as for pairwise key. However, only two messages are needed, not four.

The access point performs the following steps during group key distribution:

Because it is necessary to update the group key from time to time, a method is needed to perform the update without causing a break in the service. This would be a problem if the mobile device could store only a single group key because it takes time to go round each device and give them all the new key value. What key would you use for multicast transmissions during this update period—the old one or the new one? Whichever you chose, some of the stations would not be able to decrypt.

Fortunately, the original WEP standard made provision for multiple keys to be stored in the mobile device: Up to four keys can be installed at one time. Each transmitted frame carries a 2-bit field called KeyID that specifies which of the four keys should be used for decryption. Pairwise keys are sent with a KeyID value of 0. But we can take advantage of the other three key storage slots for group key updates.

Suppose that the current group keys are installed into KeyID 1. When we want to update, the authenticator sends the new key with instructions to put it at KeyID 2. During this key update phase, multicasts are still sent using KeyID 1 until all the attached stations have been informed of the new key. Finally, the authenticator switches over and all the multicasts from then on (until the next key change) are sent with KeyID 2.

We now know how to send the GTK, but how is the GMK generated and how is the GTK derived? In the case of pairwise keys, the PMK was produced by the upper-layer authentication method (or by using preshared keys). Clearly, this process doesn't apply for the group keys because the key is not generated per device. However, because the object of the group keys is only to protect messages and not provide authentication, there is no need to tie the key into the identity of any specific device. In fact the key can be quite arbitrarily chosen. You haven't even got the problem of ensuring that both ends of a link pick the same value because the access point simply sends its chosen value in the EAPOL-Key messages.

So the rule is as follows: The access point allocates a GMK simply by choosing a 256-bit cryptographic-quality random number. This sounds easy but there is a gotcha: the words “cryptographic-quality” are important. Many programming languages provide a function that produces a “random” number on request. Usually the numbers produced look random but actually are quite predictable. They may come from a stored table or be derived from the clock value. If an attacker knows how your “random” number is generated, he can guess your GMK. Cryptographic quality means that no one in the universe knows what the random value will be until the moment it is generated. Methods for generating such numbers are suggested in the IEEE 802.11i standard.

Once the GMK is selected, it is necessary to derive the group temporal keys. Two keys are required:

The combination of these two keys forms a 256-bit value, the GTK. This is the value that is sent by the access point to each attached station. The GTK is derived from the GMK by combining with a nonce value and the MAC address of the access point. Given that the GMK is completely random to start with, this is arguably an unnecessary step but it does provide consistency with the pairwise key case.

Most of what has been described so far in this section applies to both AES–CCMP^[5] and TKIP^[6] cipher methods. The method of deriving and delivering keys applies across the board—using the four-way handshake for pairwise keys and the two-way handshake for group keys. However, there is a difference in one respect: the size and number of keys needed is different, depending on the encryption method in use.

Given that AES–CCMP provides a higher level of security, you might expect that the AES–CCMP keys would be bigger or perhaps more numerous. However, in fact, the reverse is true. Whereas a total of 768 temporal key bits are needed for TKIP, only 512 are needed for AES–CCMP. The reason is because in AES–CCMP the integrity and encryption functions are combined into a single calculation, whereas with TKIP they are two quite distinct operations, each requiring a separate key.

For AES–CCMP, the pairwise temporal keys are:

And the group temporal key is:

The PMK and GMK are still created in the same way but, at the temporal key computation phase, fewer key bits are generated; otherwise, there is no difference in operations. While the four-way handshake is mandated for both WPA and 802.11i, it is possible that new key hierarchy schemes will be introduced for 802.11i in the future. The four-way handshake has been criticized for being slow because it can take several seconds to complete. The slow handshake presents problems for system that need rapid handover between access points such as voice-over-IP terminals.

In some cases an access point might have to support both TKIP and AES–CCMP devices in the same network. Suppose, for example, you have upgraded your old WEP systems to TKIP and now want to buy new mobile device using AES–CCMP. At least for a period, until the old cards are replaced, you will need to have both operating side by side. This is not a problem for the pairwise keys. If the access point is well designed it will know which device is using what method and store the keys appropriately. It will also know how to encrypt and decrypt messages from and to each device separately. However, a difficulty arises regarding group keys and multicasts. The access point has to send a broadcast to all the mobile devices; but if they are using different encryption methods, how can this be done? The answer is that they must all use the same encryption method for multicast reception; the standard requires in this case that TKIP should be used for multicasts even when AES–CCMP is being used for pairwise exchanges.

If you want to set up this mixed environment, you need to check that the AES–CCMP supporting product you purchase also supports TKIP, at least for broadcast reception. In practice, it is likely that most AES cards will have the option to operate entirely in TKIP mode for the foreseeable future, especially for cards operating in the popular IEEE 802.11b frequency band. Note that for security purposes, RSN also disallows the use of TKIP for pairwise if AES–CCMP is chosen for multicast

Figures 10.3 through 10.6 summarize the key hierarchy, showing how the various keys are derived. These diagrams are provided as a quick reference prior to the detailed description of how the key derivation is implemented.

Figure 10.3. TKIP Pairwise Key Hierarchy

Figure 10.6. AES Group Key Hierarchy

Figure 10.4. TKIP Group Key Hierarchy

Figure 10.5. AES Pairwise Key Hierarchy

This section describes the message formats and exchanges that are used in establishing the key hierarchies. In particular, we show the frame format used for the EAPOL-Key frames used in the four-way and two-way exchanges. The details shown here apply specifically to WPA but are basically similar for IEEE 802.11i TKIP and AES as well.

Prior to the key exchanges and temporal key derivation, several things will already have occurred. The access point will have advertised its capabilities and a mobile device will have selected a security method, associated, and initiated an authentication exchange. If upper-layer authentication is in operation, an exchange between the supplicant and authentication server will have completed, resulting in the delivery of a PMK to the access point. The access point will have intercepted an EAP-Success message and delivered it to the supplicant. Receipt of EAP-Success by the access point triggers the four-way key exchange.

In WPA, the key exchange is done using a special variant of the EAPOL-Key message, which is different from that defined in IEEE 802.1X. This variant has some extra fields and is shown in Figure 10.7.

Figure 10.7. WPA Version of EAPOL-Key Descriptor

The descriptor shown in Figure 10.7 appears in the message body section of an EAPOL frame. In practice, it would be preceded by the EAPOL header, as appropriate for IEEE 802.11. The purpose of each field is described in Table 10.1. The most complicated field is Key Information, which is divided into a number of control bits and subfields. Understanding the contents of this field is essential to understanding how the handshake works. The Key Information field is a 16-bit value divided up as shown in Figure 10.8. and described in Table 10.2. The meaning of the control bits 5 through 9 is shown in Table 10.3.

Figure 10.8. Key Information Field

The Key Data field is used differently in pairwise and group key handshakes. You might expect that this field would be used to send the actual key to the other party encrypted using the EAPOL-Key Encryption key. This is true in the case of the GTK; however, the pairwise keys are computed independently by the supplicant and the authenticator and are not sent in the key message at all.

In the case of pairwise keys, the Key Data field is used for another purpose. It is used to send a copy of the WPA/RSN Information Element. Information elements in general are described in Chapter 5 and this element in particular is discussed further in Chapter 13. For the moment, just accept that the information element needs to be transferred and that the Key Data field is used for this purpose.

The idea of the nonce values is that they are used only once with a given key. The important thing is that this should hold true even when the mobile device or access point is restarted or even if a Wi-Fi LAN adapter card is moved from one laptop to another. The combination of key and MAC address should never use the same nonce value twice. If all equipment had a calendar/clock (and could guarantee it was correct), this problem can be easily solved. For example, the nonce value could be initialized after startup, to the value of Network Time (number of seconds since midnight, Dec 31^st, 1899). Providing, on average, you don't need a nonce more than once per second, you will always get a value that has not been used before (unless time starts to run backwards, which seems unlikely).

However, not all systems have a calendar clock and the accuracy can't be guaranteed anyway. Therefore, the nonce is created from a large counter that is initialized to a random value at start up. The idea is that if the counter is large enough, the probability that you will ever reuse the same range of values is so small as to be unimportant. This counter is 256 bits long.

Suppose that an access point starts up and sets its 256-bit nonce counter to a perfectly random value. Then suppose that the access point generates ten thousand nonces before the next restart (incrementing the counter each time). New nonces are needed only when the group keys are refreshed and when a mobile device joins the network. Given the size of the nonce counter, the probability that the access point will reinitialize the counter to one of the 10,000 values it has just used is an embarrassingly low 1 in 10^-70—probably about the same probability that time will start to run backwards. There is a problem, however, because this analysis relies on generation of a perfectly random number, which can also be difficult to do.

Because of the difficulty of generating perfect random numbers, RSN and WPA specify a way to generate the starting value for the nonce counter by using a pseudorandom number generator. The formula is written using the function PRF-256. This is the random number generator function that is also used for key derivation. Operation of this function is described in the following section on key computation. Here is the formula for computing the start value of the nonce counter:

where:

If an attacker is going to base an attack on finding duplicate nonce values, he is going to have to wait a long time!

Earlier we described how the temporal keys are generated from the master keys, but we were not specific about how this is accomplished. Obviously the derivation must be done in a very specific way; any ambiguity might result in two different vendors' products deriving keys that don't match and hence failing to work together. We casually mentioned earlier that the key information needed to be expanded—getting more bits that we started with. For example, although the PMK is 256 bits, it has to be expanded into 512 bits before being divided up into the four temporal keys.

This section explains how the key generation and computation is done. In practice, both generation and expansion occur during the same process. Key expansion seems counterintuitive because it implies that additional bits are generated from “thin air.” However, the object is not to increase the size of the base key (in other words, the key entropy), but to derive several keys, all of which appear unrelated to an outside observer. For example, in the case of the four pairwise temporal keys, if an attacker knows one of the four temporal keys, it should be impossible to derive any of the others. It doesn't matter how many bits you expand the master key into, the strength against brute force attacks remains the same.

The approach to key expansion is to use a pseudorandom number generator (PRNG) and keep generating random bytes until you have enough for your key expansion. The starting condition or seed of the PRNG is based on the known information such as your master keys. Diagrammatically, this relationship is shown in Figure 10.9, which is really an expanded version of Figure 10.2, the key computation block. An important point is that, given the same seed, the PRNG always produces the same “random” output stream so two independent devices can generate the same set of keys by starting with the same seed value.

Figure 10.9. Temporal Key Computation

The PRNG function is used in several places in RSN and WPA. For example, it was used to generate the starting nonce; it is used to expand the pairwise keys and also to generate the GTK. This would create a potential problem if the same PRNG were to be used in each of these different cases. If you want a random stream of data for two different purposes in a security system, you must be absolutely sure that they will not both use an identical pseudorandom stream. On the other hand, we would like to use a single PRNG function for implementation efficiency, so what is needed is a PRNG that is guaranteed to provide a different stream for different uses even when the seed information appears the same.

To achieve this, RSN and WPA define a set of pseudorandom functions, each incorporating a different text string into the input. There are different functions, each designed to produce a certain number of bits. These are referred to as PRF-n, where n is the number of bits required. The defined choices are:

Each function takes three parameters and produces the desired number of random bits. The three parameters are:

The notation used for these functions is: PRF-n(K, A, B). So, for example, when we specify that the starting value for the nonce is:

it means that the PRF-256 function is invoked with:

In a similar way, the computation of the pairwise temporal keys is written:

Here MAC1 and MAC2 are the MAC addresses of the two devices where MAC1 is the smaller (numerically) and MAC2 is the larger of the two addresses. Similarly, Nonce1 is the smallest value between ANonce and SNonce, while Nonce2 is the largest of the two values.

The group temporal keys are derived as follows:

Here, MAC is the MAC address of the authenticator, that is, the access point for infrastructure networks.

We see how all the various keys can be derived by using PRF-n, so how is the PRF-n implemented? Obviously, this has to be carefully specified if we hope to have interoperability.

All the variants of PRF are implemented using the same algorithm based on HMAC-SHA-1.^[8] We have seen HMAC-MD5 before; it was used to produce the MIC for EAPOL-Key messages. But we are not generating a MIC here; we want a random number generator. Like HMAC-MD5, HMAC-SHA-1 is also a hashing algorithm that can be used to generate MIC values. It is approved by the US National Institute for Science and Technology (NIST; www.nist.gov), which publishes the details of the algorithm. The method of computation is different from MD5, but the effect is the same. They both take in a stream of data and produce a message digest of fixed length. HMAC-MD5 produces 16 bytes and HMAC-SHA-1 produces 20 bytes. The message digest is quite unpredictable (except by using the algorithm) and tells you nothing about the contents of the message that was “digested.” Even if you changed one single bit in input message, an entirely new digest would be produced with no apparent connection to the previous value. There's a clue to how we can make a hashing algorithm into a pseudorandom number generator.

We take a message and hash it using HMAC-SHA-1 to get a 160-bit (20-byte) result. Now change one bit in the input message and produce another 160 bits. We already know that this 160 bits appears unrelated to the first one, so if we put them together, we get 320 bits of apparently random data. By repeating this process, we can generate a pseudorandom stream of almost any number of bits. This is how HMAC-SHA-1 is used to implement the PRF-n functions. Here are the details:

After the required number of iterations, you have your random stream of bytes.

One of the weaknesses of WEP was that it had a very simple concept of keys. The key was simply a data string that was loaded into both the access point and the wireless device. The key was used directly in authentication and encryption and was not changed except by manual reconfiguration. Such usage makes the keys extremely vulnerable to attack. This chapter has shown how RSN and WPA have a much more complicated system that ensures the keys used in the actual cryptographic operations never expose the master secret held between the client and the authentication server. The system also ensures that fresh keys are established every time a session is started.

A range of keys is used, derived from a pairwise master key. The PMK may itself be generated from the upper-layer authentication method in use. Two problems are discussed and solutions shown in this chapter. The first is how to derive keys in a way that ensures they are unpredictable and different each time they are generated. The second is how, safely, to ensure that all trusted parties generate the same keys while preventing an attacker joining in the key generation process or subverting it in any way.

These problems have been solved in WPA and RSN and this chapter describes how the solutions work. Once the keys have been safely generated, they must be used within a good security cipher. The next two chapters look at the choices for security protocol: TKIP and CCMP.