Possible fixes for 802.11 WPA message authentication

[Arnold G. Reinhold]

Here are some thoughts that occur to me for improving the security of 802.11 WPA message authentication (MIC), based on what I read in Jesse Walker's paper http://cedar.intel.com/media/pdf/security/80211_part2.pdf.

One approach is to second guess Niels Ferguson and try to find a different combination of operations that will produce greater security than his Michael algorithm. That is a worthy research idea and might even be automated, since there are relatively few possibilities given the tight computation time budget. My guess is that Niels has done a good job and, in any case, revisiting the Michael design not likely to produce anything that can be implemented before WPA is introduced. So this doesn't seem the most productive place to look right now.

A different approach might be to select an MIC algorithm that is much stronger but breaks the bank on computing time for older access points, yet still works on existing cards. One could then have two variants, WPA and WPA-XS (extra strength). Sites that wanted the best security would have to junk older access points. XS could also be required for 802.11a, the new, faster standard for the 5 GHz band, which will presumably require beefier access points anyway.

A third approach for the short term would be to leverage Michael, i.e. use Michael as is and add stuff that makes the WPA MIC harder to break. Then all the cryptoanalytical work done to date on Michael remains valid. Here are several approaches I have come up with. For this discussion call the Michael key produced under WPA as it exists K. I am not proposing any change in the way K is generated or distributed.

1. Shuffle the order of the message words stirred into Michael. For example, divide the message payload into four blocks. Let L be the length of the payload in words (after padding). Compute M = L/4 (a shift). Then the blocks are [0 to M-1]. [M to 2M-1], [2M to 3M-1] and [3M to L]. At the time a new K is created, compute a randomized permutation of 4 elements and four randomized "order-determining" bits, all derived securely from K. Then for each packet, compute the Michael hash of the blocks in the order of the permutation, with the additional wrinkle that each block is hashed in either ascending order or descending order, based on the value of the corresponding bit. Note that each word is hashed exactly once and the added overhead is modest and outside the Michael inner loop.

A 4 element permutation has 4.5 bits of entropy, with the four order-determining bits, that adds at total 8.5 bits to Michael's strength. The same concept with 8 blocks would add 23 bits. The source and destination addresses are also hashed. They can simply be considered part of the payload, or they can be hashed separately, before any of the blocks or at the end, again determined by K, to add additional variability.

Since the MIC generated here is exactly the same as the original Michael MIC of the permuted message, there is no reduction in Michael security. This method breaks down for very short packets, however computation time is presumably less of an issue for short packets, so we should be able to come up with something in these cases. Perhaps we could apply the permutation to data word bytes and use the order determining bits to specify a shift.

2. Refresh the Michael key frequently. This proposal rests on WPA's need to keep packet order in sync for the IV counter. I propose generating a sequence of 64-bit sub-keys derived from K using a reasonably secure algorithm and using them instead of K to key Michael. Since each sub-key gets very little exposure, breaking Michael become much more difficult.

2a. Here is one way to generate the sub-key sequence: Create an instance of RC4 in software and initialize it using K as the RC4 key. Then generate 8 cipher bytes each time a new sub-key is needed. One could do this for every MIC that is generated. This would require eight RC4 cypherbyte generations per packet. A 258-byte RC4 state {i, j, S} will be required for each active K and the RC4 key setup will need to be performed each time K is changed. For extra credit, one can discard the first 256 cipherbytes, though I think that is overkill here.

2b. If that is too much overhead, one could generate one cipherbyte for each packet and change keys every time eight had been accumulated. Each Michael key only gets used eight times. This computation and storage load does not seem like a lot to me, but If it is too much here is a yet another approach:

2c. This one makes me a bit nervous, but it is worth putting on the table. A new RC4 key is generated for every packet fragment sent. Borrow one bit from each such key. The bit number used might be derived from K. Accumulate the bits in a series of 32 bit word, say 8 of them. When you have accumulated them, use them to compute a new sub-key, either by adding them pair-wise, or, better, using Michael keyed by K or the previous sub-key. This takes very little overhead and limits Michael to 256 uses on any one sub-key. What makes me nervous is that the per-packet keys are related and that this could introduce a new weakness into the packet encryption.

3. Do MIC chaining. Xor (or add) the MIC output block from the previous packet to K (or to the previous sub-key) to form the Michael sub-key for the current packet. This costs very little and makes it much more difficult to figure out K without breaking the WPA encryption.

Obviously there may be reasons of which I am not aware why each idea above is unsuitable. They are presented for what they are worth and in the hope that they stimulate additional thinking.


Arnold Reinhold

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]