Slashdot Mirror
Wireless LAN Encryption Standard Broken
doug13 writes: "A Rice University student cracks 802.11x encryption protocol in a week. Here is how he did it." We mentioned the cryptographic paper that underlies this attack a few days ago.
← Back to Stories (view on slashdot.org)
There's no reason it has to be OTA programmable; requiring that the user physically possess the device should be a reasonable level of security.
The problem is that on a large network, you have to get all of the equipment working with the same encryption scheme. As the number of nodes increases, it's tough to move everyone up to the new scheme at the right time. So you've basically reinvented the key management problems that the military has with their secure radios, for example. There are ways around this, but they're generally going to make the card more expensive and move it out of the range of your average business or college campus that's using 802.11b.
Your right to not believe: Americans United for Separation of Church and
You won't find many similarities. The paper that you link to documents a number of flaws in the way WEP is used. These are really generic flaws that apply to the use of any stream cipher. They are not RC4 specific, and focus on two main points. One, the IV is only 24 bits, so there are only 2^24th different key streams. Building a dictionary of all of these is quite doable in a reasonable amount of space. Also, the CRC check on WEP encrypted packets is linear. Bascially it means that you can flip bits in the packet, and know which bits to flip in the CRC portion of the packet so that it will be accepted as valid. This lets you do things like capture a packet, change it's destination address, and resend it. You can use this trick to get the AP to decode the packets for you. Quite slick. I don't know that anybody ever implemented any of these. And again, they are not RC4 specific, and tend to have certain practical problems. You pretty much have to have some knowledge about the network to begin these attacks, such as knowing what addresses are in use.
The new attack is a whole different game. It's based on a RC4 specific attack published by Scott Fluhrer, Itsik Mantin, and Adi Shamir (the 'S' in 'RSA'). It's titled Weaknesses in the Key Scheduling Algorithm of RC4. I don't have a URL offhand. Basically, RC4 has a lot of weak keys. If one of these keys is being used, then knowledge of a few key bits and the output of the cipher lets you determine a little bit more about the key bits you don't know. They theorized that WEP could be attacked with their method.
The latest paper discusses implementation of the new RC4 attack. In a nutshell, they could take the knowledge of the IV (which is used as 24 bits of the key) and the first byte of output from the cipher (easy to determine since all the packets are 802.2 encapsulated SNAP packets making the first byte 0xAA in ALL packets) to determine if the key was likely to be a weak key. They would analyze the packets whose IV indicated it is probably a weak key, and use that to determine the most likely value for the 'secret' key bits.
This is a slick attack for two reasons: it scales linearly with the size of the key. So, a 128-bit key is only about 3 times as hard to crack as a 40-bit key. Ouch. Also, it requires no previous knowledge of the network and is completely passive. Just sniff the packets until you know the key. They found it usually took about five or six million packets.
So, the newest paper is really new. None of the content is related to the paper you link to. It's not just a rehash. That's the amazing thing about WEP. It doesn't just have problems, it has a lot of them. If I had been on the design team, I would be embarrased to admit it. Almost every aspect of the protocol is broken. Almost any part that hadn't been probably will be soon.
What sophisticated equiment? These guys are using a laptop with a $100 802.11b card in it! Any card based on the Intersil Prism2 chipset will work. D-Link, Compaq. There's a bunch of them, and they tend to be the cheaper cards. They happened to use the Linksys. Since when is anything made by Linksys "sophisticated quitement that isn't readily available"! If you are talking about the antenna to pick up the signal at a distance, there are many ways to make a homemade antenna or convert an old dish for cheap.
>Interesting, here is an even older story about guys from the University of California in Berkeley breaking 802.11 security...
kinda sorta. that older article (which is very good, i used it for research i was doing on wireless security) talks specifically how one could attack WEP encryption. but the implementation is left as "an excercise for the reader". this, i believe, is merely an implementation of the attack.
Actually, the DMCA restricts the design or production of devices produced for the purpose of "circumventing a technological measure that effectively controls access to a work..." An effective technological measure such as encryption is very different from the "copy protection scheme" that isn't even mentioned in the DMCA
Anyway, there is an exemption for encyrption research, so the DMCA is not applicable here anyway.
This is the old WEP proticol that we knew was broken. This is not the new encryption that is supposed to be secure.
This isn't the first time Adam Stubblefield has done something like this. He's also involved with the Rice group that worked with Princeton and Xerox Park to crack SDMI. Here's the bibliographic entry from the Usenix paper they want to submit (pending the outcome of their lawsuit):
Scott A. Craver, Min Wu, Bede Liu, Adam Stubblefield, Ben Swartzlander, Dan S. Wallach, Drew Dean, and Edward W. Felten, Reading Between the Lines: Lessons from the HackSDMI Challenge, 10th Usenix Security Symposium (Washington, D.C.), August 2001, to appear, pending legal action.
Here's an original link:
http://www.cs.rice.edu/~dwallach/pubs.html
Not that it matters, but Adam Stubblefield is an undergraduate student (CS and Math), and also part of the famous Princeton/Rice SDMI Challenge team. He also broke the mp3.com beam-it protocol. Quite an impressive start to this guy's career.
RRF!
Lovett 2000
Mr. Stubblefield was kind enougth to provide the paper in three different formats and you choose to point to only the PDF version on Slashdot?
The intro page is at http://www.cs.rice.edu/~astubble/wep/ which points to the paper in PostScript, PDF, & HTML formats.
As a side note, Lucent prohibited the use of 802.11 wireless networks at any of it's facilities a few months ago. Stated reason: complete lack of security. Hell, Lucent MAKES lots of these cards!
e d-worm-pub.shtml had an article on 802.11 security and what a joke it and the process to develop it was.
The March 2001 Cryptogram http://www.cisco.com/warp/public/707/cisco-code-r
Learning HOW to think is more important than learning WHAT to think.
Some PDF encryption is strong, some is weak. What was attacked by Dmitry was the plugin protocol, which is weak. Adobe itself isn't really in the market of encryption, but in a protocol that allows restricion of usage in certain ways. Many vendors provide plugins that use the protocol, and many of their plugins have cryptographic weaknesses. The plugins themselves are moot, however, as the protocol blows.
The REAL sam_at_caveman_dot_org is user ID 13833.
Actually, he'll probably go to jail for breaking SDMI first -- he was part of Prof. Felton's team too. Smart guy.
And here is a link to their paper and additional information ... it would sure be fun to compare those for "similarities" ... ;)
The latest firmware available for your wavelan cards will force them to randomize the initialization vector used in WEP. For those of you that read the paper on breaking it, this is part of what makes it trivial. I would like to see this test run again with the random IV's. I'm sure it doesn't increase the difficulty by too much.
Interesting, here is an even older story about guys from the University of California in Berkeley breaking 802.11 security...
If you're thinking about the DMCA, you're mistaken. Breaking encryption schemes is not illegal, even not under the DMCA. It's only breaking the encryption of "copy protection schemes" that is illegal, which Wireless Ethernet is not.
Sorry, this won't be a test case for the DMCA.
Claus
SSL uses RC4, same as WEP.
I don't know what encryption PDF uses, but I think it is pretty strong.
In both WEP and PDF, the problem is not with the algorithms, but with their implementation. WEP uses a pitifully bad IV generator, plus uses the key straight up, rather than hasing an ASCII string to a binary value.
PDF simply cannot be made secure since it relies on transfering the key to the users computer and decrypting the PDF with it. Once you get the key, you can decrypt it yourself.
DeCSS was cracked because Xing forgot to swizzle their key in the binary, and it was extracted. At that point, another weakness allowed the extraction of more keys -- I don't know if that was a protocol or algorithm problem.
The lesson here is that security is much harder than just encrypting things. SSL, SSH, PGP, etc. were all designed as secure protocols. That was their entire goal, and the designers knew a lot about security. DeCSS, PDF, and WEP were all designed as bullet-item features within other products, and no special attention was paid to the overall security of the system.
It is also a question of mentality. Encryption algorithms are designed by academic researchers or the like, who expect the algorithm to be publically examined by their peers for any possible weakness. Software (and hardware) engineers usually don't believe in their hearts that people will try very hard to break their products, or that it would be "practically impossible" without the necessary documentation.
802.11 is based on RC4, but it's used in a very insecure way:
For each session, there's a session key (which may update periodically, I'm not sure). The session key may be of just about any length you want (up to 2024 bits, in theory).
For each packet, there's a 24-bit IV (initialization vector). This is supposed to be different for each packet. This IV is prepended to the session key, and the result is used to encrypt the packet with the RC4 algorithm. The encrypted packet is then sent wirelessly, along with the IV (the IV isn't encrypted).
Based on the attacks in Fluhrer, Mantin, and Shamir's paper, it is possible to use the IVs and the ciphertext packets to reconstruct an arbitrarily selected byte of the session key. The actual cryptanalysis is a little too involved to go into here. Suffice to say, if you can actually write the code to do it, the attack takes very little time. Note that the attack recovers an arbitrary key byte each time it is run-- thus giving us the linear attack complexity.
It should be noted, however, that not using an IV would have led to a simpler attack. The IV prevents the same key stream from being used for different packets. If the same key stream were used for each packet, then simply XORing two packets together and performing some basic analysis would allow an attacker to recover the plaintext of both packets and hence the keystream used to encrypt both. As it stands right now, using the same IV for two packets allows the same attack, but can only recover the two packets in question. Given that there are 2^24 possible IVs, this is guaranteed to work on at least two packets in a pool of 2^24+1 encrypted with the same session key. On a pool of 2^12 packets, the attack will work roughly 50% of the time for two packets within the pool.
Why didn't 802.11 use other algorithms? I don't know. RC4 is simple, and it's a stream cipher (which, in this situation, is a big advantage for implementors). 802.11 wasn't the best of all possible systems, but it wasn't exactly ROT13 or XOR with a static byte.
Does this answer your question, HaiLHaiL?
The big problem with the 802.11b folk is that in the beginning they had no security people and now they only have a couple and won't actually let them do what needs to be done.
The original WEP protocol was secure as reviewed by the NSA, then they substituted a stream cipher for the block cipher for better performance, completely breaking the scheme. Truncated IVs are not a serious problem with DES, plenty of protocols use them. Truncating the IV utterly destroys the security of RC4.
The deeper problem is that WEP attempts to provide 'equivalent privacy' to ethernet. But a wired network does not just provide some privacy it provides authentication. The big problem with WEP 1 or 2 is that there is no way to stop a fired employee surfing from the car park.
At present the (sensible) companies that are deploying 802.11b on a large scale are wrapping IPSEC arround it.
The best way to solve the problem however is to fix the protocol itself, and use a different key for each card instead of the same key for every card in the network. The 802.11b chumps keep rejecting this idea because it prevents the use of broadcast - the idea of having a separate shared key for broadcast haveing not occurred.
In order to make a separate key for each device viable it would be necessary to use some public key technology. But this is pretty easy, manufacturers of cable modems are already installing private keys and certificates in each device. Use of a modern PKI interface such as XKMS means that the card does not need to be at all complex.
It would be a good plan to swap out the RC4 algorithm in favor of AES. The chips in the cards are not up to 3DES at 11Mbs but they should be up to AES.
Nothing I have described cannot be implemented as an upgrade to the firmware of existing hardware. The extra lines of code would be relatively small.
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/
Read the paper. It does not matter how often you rekey or whether you buy the 40bit or 128 bit cards. The algorithm used is a stream cipher and will XOR your plaintext with one of 2^24 ciphertext streams that are generated from your key.
The attacker can cause the gateway to act as an oracle for any given ciphertext stream.
If you rekeyed every hour you would be safe (ish). However the WEP protocol does not support rekeying and everyone in the network has to use the same key. So you would have to update all your machines manually constantly.
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/
Ian Golberg, chief architect of zero knowledge already exposed 802.11 weaknesses a long time ago (or is that something else?)
h tm l
His home page is at:
http://http.cs.berkeley.edu/~iang/
and his paper on wep are at:
http://www.isaac.cs.berkeley.edu/isaac/wep-faq.