Message IntegrityMichael

Message Integrity Michael

Michael works by computing an 8-byte check value called the message integrity code (MIC) and appending this to the MSDU prior to transmission. The MIC is computed over the entire (unencrypted) data in the frame and also the source and destination MAC addresses. Michael was invented by Neils Ferguson (2002) and was designed specifically to address the special needs of TKIP, in particular the need to be implemented using a relatively low power processor and without high-speed hardware multiply.

The adoption of Michael by the standards group was somewhat controversial. The algorithm is new, and "new" is considered a bad word by cryptographers. Cryptographers like well-studied algorithms. Furthermore, the security level, measured by the equivalent key bit size, is low the design goal is only 20 bits of security, so a randomly chosen MIC value has about a one in a million chance of being accepted as valid. One in a million is not considered to be very rare by cryptographic standards. As a result of this weakness, mandatory countermeasures were added to stop an attacker from making rapidly repeating attempts with random MIC value.

There are several well-known ways to implement a MIC with very high levels of security; the problem is that these methods are just too processing intensive to be run by older equipment already in the field. Because the whole point of TKIP was to allow upgrade of that equipment, these attractive methods were simply not viable. The weaknesses of Michael are in no way criticisms. The IEEE 802.11 task group (i) could have chosen to design an approach as strong as any known. The weaknesses come from the need to design an approach that could be used with existing WEP hardware. In the end, the standards group felt that this was the best solution within these constraints and that the countermeasures overcome any risk from attacks on the basic method.

Countermeasures

Let's elaborate on what is meant by countermeasures. Suppose you are an attacker and you want to get a forged message past the MIC check. The most likely scenario is that you have captured a previous message and modified it in some way. You want the modification to go unnoticed. It is already going to be hard to get the message accepted to the point at which the MIC value is even checked you have to get past the IV replay protection and the ICV decryption check first. But let's suppose you have figured out how to do that. The 8-byte MIC value is encrypted in the frame along with the data so you won't know what the original value is. However, you do know where it is because RC4 encrypts each byte separately and therefore you are able to substitute random values into the field where you know the MIC bytes will be. When the message is decrypted, your inserted random bytes will certainly be changed to another value. However, because they are random, you don't really care about that. You just think about that one in a million chance that the inserted bytes will happen to be right.

In most cases your replacement MIC bytes will not match the message contents and the message will be thrown away. However, there is a small chance that the bytes will match the message and, bingo, you've succeeded in your attack. The message is delivered as valid despite having been altered.

A chance of one in a million doesn't sound too good; but remember, people do actually win the lottery, although it will never (statistically) be you. If an attacker is able to try this trick a million times, all the odds change. Sooner or later, the attack will succeed if it is not detected. The purpose of countermeasures is to detect such an attack and stop the attacker having too many plays at the game.

The purpose of countermeasures with Michael is to reliably detect an attack and close down communication to the attacked station for a period of one minute. This simple action limits the attacker to one try per minute, meaning that on average it would take one year of continuous trying to get a random packet through. Unless you have a particularly bad network administration department, someone will notice the network going up and down once per minute all year long ("ours wouldn't," I hear some cynics say).

The actual countermeasures used with Michael are a little more sophisticated. The object is to prevent the attacker from making repeated attacks, but also to try to keep the network going as long as possible. We don't want to tear everything down on the first detected problem.

The approach is to disable the keys for a link as soon as the attack is detected. The compromised devices are then unable to communicate until new keys are generated. Typically the new keys are generated immediately and the network can recover quickly. However, Michael has a 60-second "blackout" rule that says that, if there has been any MIC attack within the last 60 seconds, generation of new keys must be delayed until the 60-second period has expired. This limits the attacker to one try per minute for the entire network.

MIC Failure at Mobile Device

There are two cases in which the supplicant (in the mobile device) can detect a MIC failure. The first is received multicasts (broadcasts) that indicate an attack on the group keys. The other is received unicast messages in which a failure indicates an attack on the pairwise keys. The required behavior is similar in both cases:

For a MIC failure on a multicast message:

1. Delete the local copy of the group key.

2. Request a new copy of the group key from the authenticator using an EAPOL message (indicates MIC failure).

3. Log the event and inform system manager if possible.

For a MIC failure on a unicast message:

1. Drop any received frames and block any transmitted frames except for IEEE 802.1X messages (to allow new key exchange).

2. Request new pairwise keys by sending EAPOL message to the authenticator.

3. Log the event and notify the operator if possible.

MIC Failure at Access Point

Although the access point does not receive multicast messages (and hence can't discover a MIC failure for the group key), there are still two cases to consider. The first is a MIC failure detected in a received unicast message, and the second is notification of a group key MIC failure due to receiving an EAPOL key message from a mobile device. The actions to take in each case are as follows:

For a MIC failure related to the group key

1. Delete the existing group key and stop sending multicast messages.

2. Log the event and notify the operator.

3. If there has been another MIC failure within the last 60 seconds, wait until the 60-second blackout period expires.

4. Create a new group key and distribute to all stations.

For a MIC failure related to pairwise keys:

1. Log the event and notify the system operator.

2. Drop any received frames and block any transmitted frames except IEEE 802.1X messages (to allow new key exchange).

3. If there has been another MIC failure within the last 60 seconds, wait until the 60-second blackout period expires.

4. Initiate a four-way key exchange to establish new pairwise keys.

On first encountering these countermeasures, many people express a concern that an attacker could cause untold disruption to the network. On the face of it, if an attacker sends a forged multicast message every 59 seconds, the network would be permanently in blackout period and unable to operate. In principle, this is true and is another class of denial-of-service attack. However, it is important to note that, in practice, it is extremely difficult to forge a frame to do this. The frame must first pass the TSC check and must decrypt correctly before the MIC is even looked at. Consider these issues:

1. You have to forge a frame where the TSC (TKIP sequence counter) is correct so the frame is not immediately dropped as "out of sequence."

2. The TSC is also part of the IV, and the IV is mixed into the per-packet encryption key. So if you change the TSC, the frame will not decrypt correctly; the ICV will not give a good value and the frame will be deleted.

So to mount the denial-of-service attack, you have to capture a valid frame during transmission, prevent it being delivered to its intended destination, modify the MIC (to make it invalid), recompute the ICV so that it matches the changed MIC value, and finally deliver the message so as to trigger the MIC failure.

Frankly there are many ways to the mount denial-of-service attacks, and most of them are much simpler than trying to trigger the Michael countermeasures. The simplest way to mount a DoS attack is just to send disassociate messages for each of the connected stations. By its very nature, wireless communications is subject to DoS attack. Look at the way the Soviet Union successfully denied its population access to western TV stations by jamming. DoS is a service attack rather than a security attack; and while the countermeasures give one more mechanism, triggering countermeasures is by no means the easiest approach for the enemy.

Computation of the MIC

The computation of the MIC in Michael uses only substitutions, rotations, and exclusive OR operations. There are no multiplies. The units of data that are handled are based on 32-bit words. These characteristics make the method suitable for implementation on lower-power processors. Many of the access points shipped between 1998 and 2002 were based on low-cost 32-bit CISC processors such as the Intel I486. Consistent with this, operations that are endian dependent are defined to be little endian (as for Intel processors).

The data to be protected by the MIC includes the actual payload and the source and destination address fields. These are ordered as shown in Figure 11.6.

Figure 11.6. Data for MIC Computation

The first part of the algorithm is to organize the data into 32-bit words. This is done for both the key and the data. The 64-bit key is divided into two 32-bit words called K0 and K1. This task must be done in the right order and is designed to be easy for Intel x86 processors. The conversion to two 32-bit words is shown in Figure 11.7 where the 64-bit key is treated as 8 bytes, stored sequentially in memory.

Figure 11.7. Little Endian Key Splitting

The least significant byte of the information is always stored in the lowest memory address and K0 is stored lower than K1. After splitting the key, the data must also be split into 32-bit words. To guarantee this, the data must be padded to a multiple of 4 bytes. First, a single byte value of 0x5a is added to the end of the data. Finally, extra pad bytes with a value of 0 are added. At least four 0 bytes must be added and the total length of the data must be a multiple of 4 bytes. Thus, between four and seven zeros are always added.

As an example, if the original user data was 1 byte:

• MSDU data is 13 bytes (two 6-byte addresses plus 1 user data byte).

• Value 0x5a is added to give 14 bytes.

• Six 0 bytes are added, giving a total of 20 bytes (5 x 32-bit words) to be processed by Michael.

Note that these extra bytes are not really added to the data or ever sent over the link. They are just added for the purpose of computing the MIC and are then discarded. Now we have two 32-bit key words K0, K1, and a set of data words M0, M1… Mn. The last word Mn is always 0 and the second to last word is always non zero (because of the 0x5a that was added). Our object is to compute a 64-bit MIC value comprising two 32-bit words, V0 and V1, which will be appended to the data prior to encryption.

The algorithm works as follows:

1. Make a copy of the key: l = K₀ and r = K₁.

2. Exclusive OR the first data word M₀ with l.

3. Call the Michael block function with the values of l and r; new values are returned.

4. Repeat steps 2 and 3 for all the remaining data blocks.

The final values of l and r form the MIC result V₀ and V₁, respectively. In programming language style, this sequence can be represented as follows::

 (l, r)  (K0, K1) for i=0 to N-1 do    l  l  Mi    (l, r)  FnMichael(l, r) V0 = l V1 = r 

The Michael block function FnMichael takes two words (l, r), processes them together, and produces two new values of (l, r). The details of the computations are provided in programming language style here:

 (l, r)  FnMichael (l, r) r  r  (l <<< 17) l  (l + r) mod 232 r  r  XSWAP(l) l  (l + r) mod 232 r  r  (l <<< 3) l  (l + r) mod 232 r  r  (l >>> 2) l  (l + r) mod 232 return (l, r) 

The key to the operations here is:

: Exclusive OR

+: twos compliment addition

<<<: rotate left

>>>: rotate right

mod(2ⁿ): discard any bits of higher significance than n

XSWAP: given a 32-bit word, swap the lower 16 bits and the upper 16 bits (hexadecimal 12345678 becomes 56781234)

The resulting two words can now be appended onto the actual MSDU data (nonpadded) as 8 bytes of extra data. Notice that, because this process occurs at the MSDU level, it is completely transparent to the rest of the 802.11 MAC and encryption.