Re: 802.11 Wired Equivalent Privacy (WEP) attacks

[Arnold G. Reinhold]

The draft paper by Borisov,  Goldberg, and Wagner 
http://www.isaac.cs.berkeley.edu/isaac/wep-draft.pdf presents a 
number of practical attacks on 802.11 Wired Equivalent Privacy (WEP). 
The right way to fix them, as the paper points out, is to rework the 
802.11 protocol to use better encryption and message authentication 
algorithms.  Unfortunately a huge infrastructure has grown up around 
802.11 and large numbers of transceiver/modems are installed. If I 
understand things correctly, the encryption and authentication is 
done in firmware, so any changes to these algorithms requires new 
hardware.

Thus there is a need for a short term remedy that can work with the 
existing standard.  The BGW paper suggests changing keys more 
frequently. Here are a couple of suggestion for fairly simple ways to 
do this that I believe would significantly improve the security of 
802.11, without requiring changes to the protocol or obsoleting all 
existing equipment.  They consist of a couple of higher security 
modes,  I'll call them WF1 and WF2 (WF stands for WEP Fix).

WF1

In WF1 the 802.11 WEP keys would be changed many times each hour, say 
every 10 minutes. A parameter, P , determines how many time per hour 
the key is to be changed, where P must divide 3600 evenly. The WEP 
keys are  derived from a master key, M,  by taking the low order N 
bits (N = 40, 104, whatever) of the SHA1 hash of the master key with 
the date and time (UTC) of the key change appended.

      WEPkey = Bits[0-N](SHA1(M | yyyymmddhhmmss))

M can be any size, up to, say, 256 bytes. This allows direct entry of 
a passphrase.

WF1 would eliminate the dictionary attack described in the paper. 
Note that since the master key is not limited to 40 bits,  WF1 would 
also reduce the value of direct attacks on 40-bit keys.  In this 
regard, it is worth noting that IV collisions also facilitate a 
direct attack on the encryption.  If an attacker accumulates n 
packets with the same IV, he can attack all the packets at the same 
time, reducing the time required by a factor of n, if n isn't too 
big.  Since the time required to crack 40-bit RC4 on a single 
workstation is on the order of a week, even a factor of 3 reduction 
is significant.

WF1 does not completely eliminate the problem of IV collisions. With 
a 24-bit IV, some are inevitable.  Each IV collision has the 
potential of compromising the data in both packets. But WF1 does 
allow the rate at which they occur to be reduced and controlled. The 
rate of collisions varies linearly with the period between key 
changes. If there are R packets per second and the time between key 
changes is T (T =3600/P) then the expected number of collisions in 
the time interval T is roughly (T*R)^2/2^25,  so the rate of 
collisions is roughly T*R^2/2^25.

WF1 also does not eliminate the authentication attacks described in 
part 4 of the paper. However most of the attacks described there 
require multiple attempts to succeed and the shortened key window 
might make them more difficult to mount.

Clearly good synchronization of the time-of-day clock on each node is 
essential in WF1,  but protocols already exist that can do this over 
a network. Small synchronization discrepancies can be handled by the 
802 retry mechanism and should look very much like a short RF outage. 


The BGW paper mentions that some 802.11 modems reset their IV counter 
when they are initialized. I don't know if a key change counts as an 
initialization. If so then my proposal runs the risk of creating 
additional collisions.  However it should be possible to test modems 
for this property and refuse to enter the key changing security mode 
if such a modem is installed. Manufacturers could eliminate this 
behavior with a firmware change and there would be no impact on other 
uses of the modem.  Similarly modems that do not change the IV for 
each packet could be barred.

Unless I have missed something, WF1 could be implemented as an option 
in 802.11 driver software. It might also be possible to implement WF1 
with currently available 802.11 software by using a scripting 
language. Note that a crude version of WF1 can be implemented today 
with no new software at all: just change the WEP key every night. A 
weekly WEP key list could be distributed to authorized users by paper 
mail or encrypted e-mail.

WF2

WF2 would change keys periodically just like WF1, however the packet 
sender's address would also incorporated in the hash.

      WEPkey = Bits[0-N](SHA1(M | Sender's address | yyyymmddhhmmss))

WF2 requires that hubs encryption programming be changed. Assuming 
most hubs are programmed in firmware, this will generally require new 
hubs. However existing  client modems can still be used. WF2 will 
essentially eliminate IV collisions if the keys are changed at least 
every few hours.

WF2 still does not eliminate the authentication attacks. However 
since we have to change the hub programming anyway, it might be 
possible to add tests to detect possible attacks.

Neither WF1 nor WF2  eliminates data leaks from WEP, but they do 
reduce them considerably.  Stronger security measures, such as SSL 
and IPsec,  should be used to protect sensitive data traveling over 
802.11, but the same can be said of wired Ethernet.

These suggestions are base on a quick analysis of what I have gleaned 
about 802.11 from the net. I did not have access to the full 802.11 
spec.

Arnold Reinhold