Chopchop theory

A 802.11 WEP frame consists of many fields: headers, data, ICV, etc. Let's consider only data and ICV, and assume a constant IV.

ICV algorithm is an implementation of CRC32. It is calculated incrementally for every byte of data the frame has. Each step in C:

 crc = crc_tbl[(crc ^ data[i]) & 0xFF] ^ ( crc >> 8 );

ICV is stored little-endian and frame is xor'red with RC4 keystream. From now on, we'll represent XOR operation with `+'.

Frame 1:

_____ DATA ___ ____ICV ___
D0 D1 D2 D3 D4 I3 I2 I1 I0
 +  +  +  +  +  +  +  +  +
K0 K1 K2 K3 K4 K5 K6 K7 K8
 =  =  =  =  =  =  =  =  =
R0 R1 R2 R3 R4 R5 R6 R7 R8

Where D is data, I is ICV, K is keystream and R is what you get. If we add a data byte we get Frame 2:

_____ DATA ______ ____ICV ___
D0 D1 D2 D3 D4 D5 J3 J2 J1 J0
 +  +  +  +  +  +  +  +  +  +
K0 K1 K2 K3 K4 K5 K6 K7 K8 K9
 =  =  =  =  =  =  =  =  =  =
S0 S1 S2 S3 S4 S5 S6 S7 S8 S9

Where J is ICV and S is what you get.

It is possible to go from Frame 2 to Frame 1 just by guessing the value of the sum I3+D5, that we will call X (one of 256 chances). X=I3+D5

• D0 to D4 remain the same.
• R5 = I3 + K5 = I3 + (D5+D5) + K5 = (I3+D5) + (D5+K5) = X + S5.
• R6 to R8 are computed by reversing one crc step based on the value of X. There's a correspondence among I2-I0 and J3-J1 because crc shifts them back but D5 “pushes” them forward again. They are not necessarily keeping the same values, but their difference depends only on X, which we have guessed.
• J0 depends only on X. K9 = S9 + J0. We have guessed the last message byte and the last byte of keystream.

We will guess X by trial and error. The access point must discard invalid frames and help us in guessing the value of X.

By doing this, we have found a valid frame 1 byte shorter than original one, and we have guessed one byte of keystream. This process can be induced to get the whole keystream.

For additional detailed descriptions see:

• Chopchop Attack in the original Netstumbler thread.
• Byte-Sized Decryption of WEP with Chopchop, Part 1 and Byte-Sized Decryption of WEP with Chopchop, Part 2