Gone in 120 seconds: cracking Wi-Fi security
WEP is dead
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.
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 were 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.