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)
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.
gonna have to re-run that cat-5 into the shitter after all.
"i was saying gnu-rd"
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
In metropolitan ares, tons of companies/individuals have 802.11 networks. Could he use this to have free access just about anywhere? I think Starbucks is installing 802.11 in all their stores. This would be nice.
No, you are not correct on the CSS crack. Orginally the key was needed to decrypt the stream. However, further analysis of CSS revealed that it was possible to predict the bytes in a decryption key in a fashion similar that described in this article. It is now known that it is possible to solve the decryption functions for CSS mathematically in such a way that the key table of hexadecimal byte codes is no longer required (factored out) hence the DeCSS descrambler written with seven lines of PERL.
Too bad this is old news fellas. A group from UC-Berkeley has done an even more in-depth research project about the (in)security of wep, and can be viewed here:
Wep (in)Security
One of the important things to point out is that in the paper done by this group of people is that the also included active attacks, which is a pretty neat tool. I won't elaborate too much on this, but it is possible for a hacker (bad context) to act like a man-in-the-middle attack, sniffing your packets off the air, then doing whatever to them, then sending them to you (as if nothing every happened).
The sad thing is that most people don't even know that encryption is available on some of these models.
One other important thing to point out with wireless LANs is the new thing with war driving (similar to war dialing). What this consists mainly of is someone sitting outside in your parking lot and just surfing the net for free. There are also more complex stuff that is done out there, specifically in San Franscisco where the whole city was marked out by the http://www.dis.org guys, containing all the wireless LANs available as well as their SSID's (think of identification).
Here are some links on wardriving:
Mobile Wardriving
San Fran War Driving
General War Driving Info
One last thing to point out is that new technology that is coming out allows you to make a mobile sniffer device just using a Compaq iPaq, a Lucent wireless LAN PC Card, and a few other items (depending how sophisticated you want to get), and all of this can be done for under 1000 US dollars.
God bless Al Gore for creating the Internet.
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.
Mr. Carnes goes on to proclaim "the storage building industry may as well give up. No one will want to trust leaving their old couches in those things now."
In a related story: All over the nation, garages equipped with the Microsoft IIS Garage Door Opener have been opening spontaniously for more than 2 weeks. The owners don't seem to mind, though, as they gave up trying to actually use the garages due to their being built only wide enough to hold a Microsoft car, and nothing else.
NetInfo connection failed for server 127.0.0.1/local
Doing RC4 or AES at 11 Mbps in software is no problem.
802.11x hardware is gonna be real cheap now. If you're in the situation where you're not worried about people snooping your traffic then this could soon become a real cheap network solution - particularly with all of these paranoid companies throwing their 802.11x cards out in the rubbish.
the standard wasn't engineered to protect passwords from eventual decryption, etc. instead, it's a way that a network access point can enforce a security policy so that no traffic can get through on the lowest network layers until a client has sufficently authenticated to the access point. so a wireless hub (or even a wired hub) can say "hey, identify yourself!" and the client can say "hey, this is me!" and the hub will go to a authentication server (in Microsoft's case, they say a RADIUS server) and say "hey, is this (so and so)?" and if the authentication server says yes, then the hub will let the client's traffic through.
coupled with that is a protocol where access points can enforce a policy where clients must refresh their encryption keys on a hourly basis. so a network intruder must be able to crack these keys on an hourly basis to gain access to the network. a week is a joke... these 802.11x access points will be through several iterations of keys by the time one is cracked.
(interestingly enough, the protocol also includes provisions for someone who is wandering between wireless access points where one hub can vouch for the user and cause the newer hub to forward their traffic until authentication by the server is achieved, allowing for roaming without the 3 or so second delay that would be necessary for all of this to happen).
the point of all this is that it's not there to secure your cleartext POP password.. 802.11x is there because access points (be they wireless or ethernet or whatever) are becoming more prevalent in our society in public, physically insecure places, so a protocol has to be developed so that network admins can be sure that the right people are using it.
the protocol even allows (given 802.11x aware hardware) that user levels be granted based on the authentication server, so a guest might be allowed restricted gateway access to the Internet but their traffic may be physically restricted from reaching the LAN fileserver, whereas the admin is given the red carpet.
pretty sweet, from an admin perspective.
Just raise the taxes on crack.
The REAL sam_at_caveman_dot_org is user ID 13833.
That pretty much convinced me it was junk. I'll stick to copper for anything I particularly care about, thanks.
First, lets go over why 3DES and RSA haven't been cracked. DES was developed by IBM, for use as a commercial product. The original design was developed by a pretty bright guy, who, among other things, had attended a few NSA sponsered talks, and knew about some nifty new things (like S-Boxes). When IBM decided to turn his cipher (Lucifer) into a product, they got worried that if it was broken, they'd be mega-liable. Therefore they busted their asses trying to break it. In the process they (re)discovered many types of attacks, include differential attacks (a type of chosen plaintext attack). Somebody noticed that NIST had asked for ciphers and nobody had a good submission, so IBM submitted Lucifer. BUT they were still worried about it, and spent more time refining it. The NSA didn't want free crypto going loose, and offered to give it their seal of approval if IBM would cooperate fully. IBM didn't want to be liable if Lucifer had a small flaw, so they agreed. The NSA then also joined the groups of people attacking Lucifer, and helped the IBM team avoid differential attacks (which they had already done, but NSA offered refinements). The only bad thing the NSA did was cut the key length. Lucifer was submitted, and became DES.
Now, the whole point of this is that it took a long time and many many manhours of very bright people attacking the cipher, and coming up with design principles to help avoid the attacks, because IBM DID NOT want to release a cipher without doing it's damndest to guaruntee it was secure. They invited outsiders from all over (including the NSA) to attack and comment on it. A lot of work was put into it initially.
If DES had an easy attack against it, it would have been found, the design principles would have been revised, and hopefully the entire class of attacks would be taken care of.
RSA was similar. R and S came up with ciphers, and tried to break them. When they thought they had something good, they'd hand it over to A, who would then break it (supposedly he broke the first 31 attempts without any trouble). This is the same cycle IBM did: a team designs it, submits to others who will attack it, they get feedback and refine it. After the original RSA was OK'ed by R S and A, they gave it to colleages to try and break. Who failed.
My point is that all successful ciphers have gone through extensive work. Many many ciphers developed in the course of coming up with good ones are scraped. Only a few are secure. The best ciphers have been analysed by many people for a long time before they even see the light of day.
CSS was not put through such a process. They developed it, and never submitted it to the glare of public scrutiny. It contains glaring design flaws, that even a small amount of competitive attacking would have found. But it was never submitted to such, and therefore deployed before it was proved secure. The PDF security model (which Dmitry broke) was also not given a public vetting before release. (BTW, Dmitry didn't break crypto, he broke the protocol. However, many of the encryption schemes used in eBooks are proprietary designs that haven't been put to public scrutiny, and are therefore likely weak) I haven't chewed through the details of the 802.11 break, but 802.11, while it has been submitted to public scrutiny, hasn't been there very long.
It isn't that the codes are bad, but that most codes developed are crap. If you want a good code, take a code, and try as hard as you can to break it. Ask your friends/hire independant consultants to break it. Then, release it to the public to break it. Only then can you have any confidence that it is secure. And at that, if a new code hasn't been around for a while, it's probably crap. Most codes are easily broken. Scrutiny breaks the easily broken ones, leaving the strong ones for wider use.
I'm using wireless right now. Good thing I'm not encrypted, or someone would be able to break it and snoop on me to see that I am reading /.
Are they going to arrest this guy too?
All Troll + "offtopic" mods are meta moderated as "Unfair", because you abused the system.
Stubblefield's attempt took just under a week, which included the time taken to deliver the card, set up the testbed, perform debug and then finally retrieve the key.
Ouch.
-----
In all honesty though, this -could- be a good thing for us regarding laws. Here's an American graduate student that showed an immense weakness in a standard encryption protocol. Furthermore, he did it for no profit, without violating any copyrights, and while working with AT&T.
This could be very good. People (as in general society) would be a bit leary of Dmitry Skylarov because he is Russian and becuase it was a for-profit venture.
This student, OTOH, broke this w/o profit and without breaking any copyrights.
Hopefully (though I doubt it) this can hit at least semi-mainstream news, or, at a minimum, the ears of lawmakers and security analysts.
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
The details of how he did it are in PDF format. Doesn't that make Adobe a party to the crime of distributing a circumvention device?
i'm not very well versed in encryption schemes, but why is it that the encryption schemes in DeCSS, Adobe PDF, and now 802.11 are so 'easily' broken, as opposed to 3DES or RSA that are being used in SSH & SSL? why aren't these algorithms being applied in 802.11?
reech bee-yond ur clip-0n
It seems to me that low volume wireless LANs are pretty safe, and can be completely safe if they rekey on a regular basis.
The original paper estimates that on average either 1 million or 4 million packets need to be sniffed in order to discover a 40-bit key depending on how the IVs were generated. Adam Stubblefield's paper found that it seemed to require 5 to 6 million packets to discover a 40-bit key. That's actually quite a lot of packets for many LANs, and a huge number for a typical home LAN. Adam had to run a flood ping for several hours to collect enough packets.
Add to that the fact that the complexity scales linearly with key size. This means that, on average, discovering a 128-bit key will require somewhere between 3 million and 18 million packets.
I just checked the statistics on my home 802.11b AP and found that I average somewhere around 100,000 packets per day. That means that someone would have to continuously monitor my network for between one and six months in order to gather enough packets to determine my key, assuming I use good keys (I do).
So, as long as I'm careful to rekey every couple of weeks, I should be safe.
Obviously, if your wireless LAN pushes a couple million packets per day (20 people streaming 192Kbps MP3s for 12 hours) you'd have to rekey daily, which would be a major pain if it wasn't automated.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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/