Gone in 120 seconds: cracking Wi-Fi security

[Alpine]

WEP is dead

WEP is dead - and here's the proof.
Cracking the Wi-Fi security protocol WEP is a probability game. The number of packets required to successfully decrypt the key depends on various factors, luck included.

When WEP was compromised in 2001, the attack needed more than five million packets to succeed. During the summer of 2004, a hacker named KoreK published a new WEP attack (called chopper) that reduced by an order of magnitude the number of packets requested, letting people crack keys with hundreds of thousands of packets, instead of millions.
Last month, three researchers, Erik Tews, Andrei Pychkine and Ralf-Philipp Weinmann developed a faster attack (based on a cryptanalysis of RC4 by Andreas Klein), that works with ARP packets and just needs 85,000 packets to crack the key with a 95 per cent probablity. This means getting the key in less than two minutes.
Here's an interview with the three researchers. All three are studying at Darmstadt University of Technology, Germany. Tews, 24, is a Bachelor student; Pyshkin, 27, and Weinman, 29, are PhD students in Professor Johannes Buchmann's research group.
How did you develop the attack?

Ralf-Philipp Weinmann: Andrei, Erik, and I share a room. We've basically seen Andreas Klein's RC4 attack in late 2005 when he presented a talk here in Darmstadt at local workshop (Kryptotag).
We didn't realise the potential of the attack until early 2007 when I realised that apparently nobody outside of Germany was aware of the attack since the preprint was only available in German until then. Erik and I then bounced ideas back and forth about the applicability of the attack against WEP and quickly realised that it was more than an order of magnitude faster than any previous key recovery attack. Erik wrote some code, Andrei improved it.
Simultaneously, we became aware that an improved version of Andreas Klein's paper had been submitted to the Workshop on Coding and Cryptography, this time in English. First attempts against a demo network showed that the code indeed did work as expected on our side. We began writing the paper and put it on the IACR ePrint server. Simultaneously, Erik released the code for people to verify our results.
What type of speedup does your attack provide over previous attacks?

Erik Tews: The old attack needed between 500,000 to 2 million packets to "work usually". We (Erik Tews, Andrei Pychkine and Ralf-Philipp Weinmann) showed that our attack has a success probability of 50 per cent with 40,000 packets and success probability of 95 per cent with 85,000 packets. So perhaps the speedup is a factor of 15 or so in the number of packets required.
CPU-Time of our attack is about three seconds on a consumer laptop. I think the CPU-Time of the original attack was longer, but could vary very much.
We found out that a rate of about 764 data packets per second can be reached using ARP injection. So to make it a little bit easier for the reader we can say that 60 seconds are enough to collect 40,000 packets and crack the key with a 50 per cent success rate. If the rate of packets is lower, then we need longer.
How does your attack work?

Erik Tews: Step 1: Find the enemy (this is the test-network you created in your lab, to verify our results). You can use kismet or airodump to find it.
Step 2: Generate some traffic. To generate some traffic, use aireplay-ng in ARP injection mode. Aireplay will listen to the network until it has found an encrypted ARP packet. By reinjecting this packet again and again, you will generate a lot of traffic, and you will know that most of the traffic was ARP-traffic. For an ARP-Packet, you know the first 16 Bytes of the clertext and so the first 16 bytes of the cipherstream.

Step 3: Write this traffic to disk using airodump-ng or so. This will create a tcpdump-like capture file with the traffic.
Step 4: Launch our algorithm. You need the aircrack-ptw (by the way, aircrack-ptw has been integrated in the 0.9-dev version of aircrack-ng, which is currently in svn, but not released).

From a theoretical point of view, our algorithm is based on the following ideas. Andreas Klein, a German researcher, showed that there is a correlation in RC4 between Keybytes 1 to i-1, the keystream and the keybyte i. If the keybytes 1 to i-1 and the keystream are known, it is possible to guess the next unknown keybyte with a probability of about 1.36/256 which is a little bit higher than 1/256. We where able to show that it is also possible to guess the sum of keybytes i to i+k with a probability of more thatn 1.24/256.

In a WEP environment, the first three bytes of a packet key are always known and are called IV. Our tool tries to guess the sum of the next 1, 2, 3, ... to 13 keybytes for every packet. If enough packets have been captured, the most guessed value for a sum is usually the right one. If not, the correct value is most times one of the most guessed ones.
Aircrack-ptw try to find the key, using this idea described above. If you have about 40,000 to 85,000 packets, your success probability is somewhere between 50 per cent and 95 per cent.


Page 1/3

[Alpine]

What can affect the speed of your attack?

Erik Tews: There are some keys we call strong keys. A key is a strong key if it has at least one strong keybyte. A strong keybyte is a keybyte which fulfills a special equation or condition. (Equation (10) in section 6.2 in our paper)
If a key has just 1-3 or perhaps 1-4 of these strong keybytes, our attack will still work, but perhaps take some more packets. The probability that a randomly chosen key has more strong keybytes is below one per cent.
Even if a key has the maximum of 12 strong keybytes, our attack can be modified so that it will still work, just need some more cpu-time or packets. This is currently not implemented in our tool, but we know how to fix that and we are going to implement it soon. With our modification, we will perhaps need three to five minutes with an optimal packet rate for a key with 12 strong bytes (this is a guess, hasn't been exactly tested yet).
What about the keys with a bigger size than 104 bit?

Erik Tews: There are some vendors which implemented a 232/256 bit WEP. I think these keysizes are very uncommon. Currently, only 40/64 and 104/128 bit keys have been implemented.
There are currently some other attacks, which allow us to recover more than the first 16 bytes of the keystream. Combining our attack with these attacks would even allow us to break WEP512. This has not yet been implemented, but could be added in future.
How does your attack performance scale with increasing WEP key size?

Erik Tews: We did only benchmark the 104 bit version of WEP. If just a 40 bit key is used, we know the attack is faster, but we didn't do exact benchmarks. Perhaps it can be done in 30 seconds if the packet rate is high.
Do 256 bits stop you from using just ARP packets to succeed?

Erik Tews: For an ARP-Response, the first 16 bytes are constant. What follows are IP and MAC-Adresses. These values are not globally fixed, but if the same request is sent again and again, these values will be always the same because the response is the same again and again.
There is another attack called chopchop which should be able to find out what these unknown values are. On the other hand, these values could perhaps be guessed too.
Using such a technique, it should be possible to attack WEP256 too. This is currently not implemented in aircrack-ptw, but could be added easily.

Page 2/3

[Alpine]

Can't it be stopped by filtering and/or rate limiting ARP packets?

Erik Tews: If you ratelimit ARP packets, it will just slow down the attack. We think the attack can be modified to work with other traffic than ARP. ARP was just the easiest method to implement and it works very well in a real world environment, because everybody uses ARP.
Can it work in a passive way?

Erik Tews: I will now go a little bit into detail. What we need to perform the attack are a lot of packets where we know the IV (this is transmitted in plaintext) and we need to know a certain part of the keystream. If you know the plaintext of the packet, you can get it by just xoring the plaintext with the ciphertext in the packet.
For an ARP request or response, the first 16 bytes of the plaintext are known, which gives you the first 16 bytes of the keystream.
If X = X[0] || ... || X[k] is a keystream, and you are going to attack an i BYTE long WEP key, you should know the keystream from X[2] to X[i +1]. It is still sufficient if you've got a method to guess the keystream correct with a high probability, the attack still works if some keystreams where guessed incorrectly. So if somebody writes some code which guesses the plaintext/keystream of usual ip-traffic right, or guesses more parts of the keystream in most of the cases, it would work with longer keys or in a passive way.
Would using WEPplus be better?

Erik Tews: No. WEPplus was originally designed to defend against the so-called FMS attack, an attack on RC4 which was published in 2001. The FMS attack works a little bit differently to our attack. For FMS the IV needs to fulfill a special condition, which is for a 104 bit WEP environment: first byte must be 16 (decimal) and the second one must be 255 (decimal). The third byte doesn't matter. This is sometimes called the "resolved property".
WEPplus skips all IVs that match that condition. This makes the original FMS attack impossible. There are some modified versions of the FMS attack which even work if these IVs are skipped.
Our attack is different to the FMS attack. Or attack doesn't care about this "resolved property", so filtering out all these IVs shouldn't change anything. This make WEPplus as attackable as normal WEP.
Your paper states that Linux avoids weak IV and doing so slows your success rate by less than five per cent.

Erik Tews: What we were trying to say was the following. In an old attack on WEP, some "weak IVs" where used. Our attack does not profit from these "weak IVs", so skipping them won't protect you.
There is almost no slowdown. If you look at the plot, both lines, the one with the randomly chosen IVs and the IVs chosen by the Linux generator, are nearly identical. Additionally, the Linux generator doesn't choose IVs randomly and skips the weak IVs, it generates the IVs using a counter.
This results in minor differences, but there is nearly no slowdown if the Linux IV generator is used.
In all previous pages, we assumed that IVs are randomly chosen. We tried to show that this attack even works if IVs are not randomly chosen.
If we have hardware that can't be upgraded to support WPA, what is the best way to configure it?

Erik Tews: We think that WEP is DEAD now, there isn't much left to fix. If your hardware cannot speak WPA and you need wireless security, you should replace your hardare (which costs money) or alternatively configure any kind of VPN.
WPA still uses RC4. Is there any type of attack that could take advantage of your speedup to successfully crack WPA?

Ralf-Philipp Weinmann: Before anybody jumps to conclusions: although TKIP is also based on RC4, keys change per packet (!) for this protocol. From my current understanding one would have to be able to efficiently guess a large part if not all of the per-packet keys with a high probability for multiple packets to invert the key hash and obtain the temporal key [there is work by Havard Raddum on this subject].
Furthermore, the Michael integrity protection, together with the strictly monotonous counter IV in the header, will successfully foil re-injection attacks. While WEP can be seen as an glaring example of how _not_ to design a crypto system, the design of TKIP is sound and was done by actual cryptographers. This doesn't mean it's infallible, but it's a lot better.
TLS and SSH also use RC4 but aren't affected by Klein's attack either. Klein's attack needs multiple key streams encrypted generated by "similar" keys. By similar I mean that keys share a common prefix or suffix. This, however, isn't the case with these protocols. Both use a hash function (yes, they actually use two, MD5 and SHA1) to generate the session key under which the data is encrypted under. Again, to successfully attack these protocols, you'd need an attack on RC4 that recovered the key for single key stream.
Please note however that RC4 should not be used in future designs. RC4 is a weak algorithm. Distinguishers exist that allow any contiguous RC4 output stream to be distinguished from random [see Golic's work]. Although these attacks are not practical, remember the old proverb: attacks only get better.

The REGister