Columbia crypto box

Steven M. Bellovin smb at
Mon Feb 10 18:12:13 EST 2003

In message <b295ds$l66$1 at>, David Wagner writes:
>Trei, Peter wrote:
>>The weird thing about WEP was its choice of cipher. It used RC4, a 
>>stream cipher, and re-keyed for every block. . RC4 is
>>not really intended for this application. Today we'd
>>have used a block cipher with varying IVs if neccessary
>>I suspect that RC4 was chosen for other reasons - ease of
>>export, smallness of code, or something like that. It runs fast,
>>but rekeying every block loses most of that advantage.
>It's hard to believe that RC4 was chosen for technical reasons.
>The huge cost of key setup per packet (equivalent to generating 256
>bytes of keystream and then throwing it away) should dominate the other
>potential advantages of RC4.

I'm not sure you're right.  While 40-50% of packets are about 40 bytes
long -- see for some
older statistics -- most *bytes* are carried by larger packets.  From 
that same site, about 75% of the bytes are carried by packets over 500
bytes long.

A quick awk script suggests that given that packet size distribution, 
the total workload to use WEP-style encryption is about double the 
number of bytes.  The overhead is thus substantial -- but RC4's cost 
per byte is quite low, so it was probably a net win.  Other studies 
suggest that LAN packet size distribution is somewhat different, with 
more large packets; that would lower the overhead.

Note that the traffic mix on the Internet has shifted since that data 
was collected.  Audio and video files are large, and hence will use 
more large packets; that again would lower the overhead.  What's 
unclear is to what extent wireless device traffic differs.  Given the 
increasing deployment of 802.11 in the home, I suspect that there's a 
lot of big files going to wireless endpoints.

>In any case, WEP would clearly look very different if it had been designed
>by cryptographers, and it almost certainly wouldn't use RC4.  Look at
>CCMP, for instance: it is 802.11i's chosen successor to, and re-design
>of, WEP.  CCMP uses AES, not RC4, and I think that was a smart move.

A block cipher is clearly a better choice here.  But there were some 
rational reasons for selecting RC4 (even though I think that on 
balance, the choice was very wrong).

		--Steve Bellovin, (me) (2nd edition of "Firewalls" book)

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list