[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
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
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 || ... || X[k] is a keystream, and you are going to attack
an i BYTE long WEP key, you should know the keystream from X 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