Regarding number of packets needed to crack WEP

Question

One of the major weaknesses of WEP is a short 24-bit IV, which means that only 2²⁴ packets are needed to exhaust all IVs. 2²⁴ translates to about 16.5 million IVs (or packets for that matter).

Although we need this many packets to start having repeating IVs, I see the best attacks require about 100K packets (orders of magnitude less than the 16.5 million).

Does it mean that the state-of-the-art attacks do not require IVs to repeat? Its clear that we will not have repeating IVs after just 100K packets. If this is so, why the are repeating IVs always presented as the main weakness of WEP?

Answer 1

Yes it does, but you have to take into consideration the probability of collision not only size of key space.

As you said the key space for WEP is 2²⁴, with this key space there is a 50% collision after only 2¹² packets, so you don't actually need to go over the 2²⁴ packets to find a collision. After only 12430 frames you get 99% collision probability, so from there you can see that 2²⁴ key space is a really low number in order to secure WEP.

To go through the math you'll need to check out the Birthday attack which is uses the birthday paradox probabilistic model to reduce the complexity of finding a collision. It's actually pretty interesting to have a look at (it's also used in order to compute MD5 collisions). Basically it's based in the probability of finding 2 people that have the birthday in the same day in a set of N people randomly chosen.

As you can see probability reaches 100% with 367 persons since there are 366 possible birthdays but with only 23 people you get 50% chance of collision!

The problem is that WEP uses RC4 which is a steam cipher, that means that no cipher key can be reused. This would mean that BSS would need to change its cipher key as soon as all 2²⁴ keys have been consumed, but WEP protocol doesn't implement something like this.

WEP uses the same base key for all users so the security of WEP is based on never recycling a pair of [Base_Key,IV].

For the given scheme WEP would need an avoidance algorithm to avoid to different nodes to reuse the same IV, but again WEP doesn't implement something like this.

What WEP does is randomly selecting an IV from the 2²⁴ key space, and this is where the Birthday paradox comes into play.

Answer 2

That is correct. The PTW technique leverages the mathematical correlation between RC4's output bytes and individual packet keys. This was present in Klein's attack on the RC4 cypher.

From this excerpt we gather that we can guess the value for a specific byte of the RC4 key we are attempting to crack, provided that:

• We know first bytes of the individual packet keys (IVs associated to each one, as the packet key is IV + RC4 master key). Gathering IVs is done through ARP requests and is the first phase of the PTW attack.

• We know given number of bytes of individual key streams. This is where capturing packets comes into play, second phase.

  A refined version of this approach is implemented in Aircrack-PTW.

Aircrack-ptw attack

Aircrack-ptw is able to extend Klein's attack and optimize it for usage against WEP. Using aircrack-ptw's version, it is possible to recover a 104 bit WEP key with probability 50% using just 40,000 captured packets. For 60,000 available data packets, the success probability is about 80% and for 85,000 data packets about 95%. Using active techniques like deauth and ARP re-injection, 40,000 packets can be captured in less than one minute under good condition. The actual computation takes about 3 seconds and 3 MB main memory on a Pentium-M 1.7 GHz and can additionally be optimized for devices with slower CPUs. The same attack can be used for 40 bit keys too with an even higher success probability.

General Notes of interest

This paper is a great resource to understand RC4 cipher weaknesses. This would take you to the Related-key attack on RC4, thus affecting WEP encryption.

Here is an interesting resource regarding the limitations of PTW.