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 `+'.
_____ 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.