Webster1913 below gives an interesting derivation of WEP, the Wireless Equivalent Privacy protocol: it comes from "to weep". WEP is a link layer protocol for encrypting the portion of your traffic from an antenna to the base station which receives it. WEP tries to claim it only tries to give "equivalent privacy" to stuffing wires through the walls. What exactly would be considered equivalent is unclear; however, one would hope that an actually illegal activity would be required to break down WEP. In practice, WEP fails, and I would like to think the WEP committee wep abundantly more than once.
Johnath abundantly explains many of the many shortcomings of WEP. Leaving key management essentially as an exercise to the reader was a nice trick, and causes the most difficulties; Johnath discusses them. Fortunately, WEP is so horrible a protocol from the cryptographic point of view that there is room for more about its security, or lack thereof. Almost every step of the design of WEP deserves to be studied as an example of how not to design a protocol. Its designers (I use the term loosely) appear to have made every mistake in the book, and even, by some freaky weird Jungian synchronicity, to fall into a trap that's quite hard to fall into, and was only discovered later!
The right way to encrypt wireless packets is with a block cipher
Stream ciphers can really be good. If you have a stream of data to encrypt with a peer, a good stream cipher (or a block cipher in some streaming mode, such as CTR mode) lets you pre-compute large chunks of keystream ahead of time, and then encrypt and transmit data at very high speed. For encrypting a TCP connection, stream ciphers can be a great choice. Indeed, SSL (or TLS, if you prefer) by common default does just that, and does it well. RC4, used by both SSL and WEP, may have been a reasonable choice of stream cipher.
IP traffic in general, and wireless traffic in particular, are nothing like a stream of data -- it is comprised of individual "packets", each of which may be lost. Remember we're at the link layer here: we cannot assume any retransmission!
Whenever the data stream is interrupted, both peers must resynchronize their keystreams. When encrypting the link layer, the sender has no way of knowing which packets will be lost; the only solution is to resynchronize at the beginning of each packet. For RC4, that would involve changing the key: bye-bye precomputed keystream! Worse, while emitting keystream bytes with RC4 is cheap, loading a new key is quite expensive. And IP packets can be quite small. So RC4, while cheap, is actually not so cheap when used in WEP. (But it's still probably cheaper than, say, an AES candidate would have been...).
Had a block cipher been chosen, no resynchronization would have been necessary. CBC mode (and even CTR mode!) are specifically designed to encrypt individual messages, rather than a stream of data. Block ciphers are ubiquitous; it's unclear why the WEP committee decided to do the opposite of the obvious. The only excuse might be that RC4 has some very fast implementations. But the setup for using a new key can be expensive, and many TCP packets in typical use are very short -- the setup costs probably cancel out much of the time gained from fast encryption.
In fact, there already was a pretty good protocol for encrypting IP packets. It's called "IPsec", and it uses any one of a wide range of block ciphers; there's even a way to define new block cipher encryption suites to use. IPsec is at level 3 of the OSI stack and WEP is at level 2, so the WEP designers may have thought it inappropriate. But it is impossible to understand why they didn't steal the ideas of IPsec for their own encryption.
Don't send a stream cipher to do a block cipher's job. (The converse is doable.)
Use a key only once!
So WEP needed some way to generate many keys. Of course, a stream cipher is based on a single key. WEP doesn't include any mechanism for key exchange or other key management, so there's no way to transmit the per-packet keys. WEP decided to borrow an idea from block ciphers (did I mention they should have used a block cipher?): have a shared secret key, but encrypt each packet on the basis of the key combined with some initialization vector (IV).
The WEP committee decided to concatenate a 40-bit key with a 24-bit IV, to get a 64-bit RC4 key. 64 bits of RC4 were actually at the time quite reasonable. Not high security, but definitely the equivalent of a wire in a wall. Coincidentally, the 40 bits of key were just enough to fit in the export regulations common at the time. The 24 bits of IV are transmitted with each packet, while the 40 key bits are secret.
As an aside, the phrases "40 bit key" and "64 bit key" bandied about by vendors refer to the same thing, as do "104 bit key" and "128 bit key" for the later WEP2 proposal.
40 bit security is not too shoddy, actually, and might actually be your idea of privacy equivalent to wires in the wall. Of course, using a simple concatenation of key and IV, rather than something more secure cryptographically speaking, does mean that any key recovery performed for a specific packet immediately recovers the encryption key. This is not so much a fundamental design error as an overly optimistic view of cryptographic techniques. Unfortunately, it is also had serious consequences (see below).
How does a WEP transmitter decide on the 24 bits of IV? It picks them randomly.
For a single packet, this does indeed give you 64-bit security. For 2 packets, if you managed to pick distinct IVs, then it's still 64-bit security for each packet. (Well, a related key attack might weaken this, but if your cipher has known related key attacks then you should be using a different cipher.)
But what if we happen to choose the same IV for 2 different packets? Well, each encrypted packet is the plaintext packet, XORed with the keystream. And you're using the same key, so you're using the same keystream for both encrypted packets. So the XOR the 2 "ciphertext" packets is the XOR of the 2 plaintext packets. This is no security at all. It's the basic "don't do" of stream ciphers ever to use the same keystream twice.
But what are the odds of picking the same IV? For 2 packets, it's one in 224, or about 1 in 16000000. Not too bad. For ~4000 packets, the birthday paradox sets in, and the chances are around 1 in 2. Not too good. Worse yet, if we listen in on WEP traffic with the same key, we collect more and more IVs. As time goes on, more and more traffic becomes readable.
WEP traffic is essentially readable without breaking the code.
Another class of attacks on encrypted protocols is by changing the traffic as it goes through. If I can copy a legitimate user's WEP ciphertext and I have a pretty good idea of what it says, I can XOR it with what I want to say (maybe even change the IPs on the packet), and transmit that. If I can replace the legitimate user's WEP ciphertext with my own, it's even more fun! (At least if, say, changing "ls" with "rm" in a telnet session is your idea of fun.) WEP is carried over radio, so it might be possible actually to do this (say to a user with weak signal strength).
To combat this, all encryption protocols also use authentication. A strong hash function is used with a separate key to sign all packets. There is some argument whether it is better to sign-then-encrypt or to encrypt-then-sign, but all agree that signing is a necessity. Lucky that WEP includes authentication, then!
Unfortunately, WEP's authentication is a CRC. I can just picture the committee members: "After all, we then encrypt it, so a CRC is good enough, right?". Well, wrong. CRC is known to be a bad choice for authentication (security isn't a design goal), but also a horrible choice for authentication when a stream cipher is used. One can essentially mask any bit flips made in the ciphertext by flipping the same bits in the CRC! And, since bit flipping commutes with stream cipher encryption, for once it doesn't matter if you "sign"-and-encrypt or encrypt-and-"sign".
Even if CRC weren't this horrible, 32 bits are far too small a space for a secure hash, again due to the birthday paradox.
If you can change WEP encrypted packets "in the air", you can make sure they still decrypt correctly.
An unforseeable shortcoming
The crème de la crème of WEP's inadequacy cannot be blamed on the designers. They made almost all the mistakes in the book, but the best chapter in the book hadn't been written when they made them.
WEP uses RC4 in a manner susceptible to an attack discovered in 2001 (progress towards the attack may have been made during 2000). The Fluhrer-Mantin-Shamir attack on RC4 is a related-key attack which allows recovery of the key from ciphertext+plaintext for certain weak keys. The problem for the attacker is to determine when a weak key is used: knowledge of several bits at the beginning or the end of the key helps.
When the key used for a packet is the concatenation of an IV and a secret key (in either order), the FMS attack works. The designers of RC4 couldn't have known this, but the consequence is bad: RC4 key recovery is possible. That is, it is possible to recover an RC4 key merely by examining encrypted packets. The enclosed IV tells you when a weak key is being used. Some plaintext is also known: IP packets have a simple structure, so many bits of plaintext are immediately known, even without access to plaintext (which would require sniffing the output of a WLAN base station). The FMS attack recovers bits of the key, and since the packet key is a simple concatenation of secret key and IV, it can be recovered!
A more conservative way to chose the per-packet key would have been to hash together the secret key and the IV. This would have dramatically increased the strength of the secret key used in WEP. It wouldn't have been ideal, but it would have worked. Unfortunately, the WEP designers were overly optimistic about their chosen cipher. You can download 2 programs which crack WEP keys from encrypted traffic (see below).
This attack is the most devastating. It's also the only one for which there is some excuse: The designers knew (or should have known) about the previous flaws, but they had no way of knowing of this flaw. On the other hand, SSL (or TLS, take your abbreviational pick) also uses RC4 by default, and is safe from this attack.
Designing crypto protocols is hard. WEP traffic is readable just by examining traffic. You can even determine the key, and join in!
- IEEE P802.11 Wireless LANs Unsafe at any key size; An analysis of the WEP encapsulation (Oct 27, 2000), Jesse R. Walker, Intel Corporation. (The XORing attacks based on waiting for a birthday paradox event on the IVs)
- Weaknesses in the Key Scheduling Algorithm of RC4 (2001),
Scott Fluhrer, Itsik Mantin, Adi Shamir
Lecture Notes in Computer Science 2259
- Using the Fluhrer, Mantin, and Shamir Attack to Break WEP (2001),
Adam Stubblefield, John Ioannidis, Aviel D. Rubin
- WEPCrack (http://wepcrack.sourceforge.net/), RC4 cryptanalysis in Perl
- AirSnort (http://airsnort.shmoo.com/), a nicer tool (but it's more insulting to be broken in Perl...)