[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[ISN] Gone in 120 seconds: cracking Wi-Fi security


By Federico Biancuzzi
15th May 2007

Interview - 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.

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 

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.

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. ®

Federico Biancuzzi is freelancer who writes for SecurityFocus, ONLamp, 
LinuxDevCenter, and NewsForge.

Attend Black Hat USA, July 28-August 2 in Las Vegas, 
the world's premier technical event for ICT security 
experts. Featuring 30 hands-on training courses and 
90 Briefings presentations with lots of new content 
and new tools. Network with 4,000 delegates from 
70 nations.   Visit product displays by 30 top
sponsors in a relaxed setting. Rates increase on 
June 1 so register today. http://www.blackhat.com