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 majordomo at wasabisystems.com