WEP encapsulation, the CRC, and why a CRC is not a MAC

(a) What a cyclic redundancy check is, and how a 32-bit one is computed

A cyclic redundancy check is an error-detecting code. Treat the message as a string of bits, and read that string as the coefficients of a polynomial over $GF(2)$ — the field with two elements, in which addition and subtraction are both XOR and there are no carries. Fix a generator polynomial $G(x)$; for a 32-bit CRC, $G(x)$ has degree 32.

To compute the check value: shift the message left by 32 bits (append 32 zeros), divide that polynomial by $G(x)$ using polynomial long division over $GF(2)$ — which is just repeated XOR of a shifted copy of the generator — and keep the remainder, which is at most 32 bits. Append the remainder to the message. The transmitted word is now, by construction, an exact multiple of $G(x)$.

The receiver divides the whole received word by the same $G(x)$ and expects a remainder of zero. Any non-zero remainder means the bits changed in transit. A well-chosen degree-32 generator catches every single-bit and double-bit error, every odd number of bit errors, and every burst of 32 bits or fewer — which is exactly what a noisy radio link throws at you.

One implementation detail matters for the exercises below: standard CRC-32, the one in zlib.crc32, is not the bare remainder. It pre-loads the register with all ones and complements the result at the end — an initial and a final XOR — which is done so that leading zeros in the message are not invisible. It changes one of the algebraic identities below, and the second exercise makes you look at exactly how.

(b) What role the CRC plays in WEP

In WEP the 32-bit CRC is used as the integrity check value (ICV). It is computed over the whole MAC data field, appended to it, and then encrypted together with the data. The intent — and the word is doing a lot of work — was that it would detect not only accidental corruption but deliberate modification, since an attacker cannot read the encrypted ICV to adjust it.

That intent fails, and part (b) of the exam question is answered properly only by saying so. A CRC is an error-detecting code with no key: anybody can compute it over any message. A message authentication code is keyed, and that is the entire difference. Encrypting an unkeyed checksum does not turn it into a keyed one, for reasons the last section makes concrete. The full-marks answer is: the CRC is WEP's integrity check value, and it gives integrity against accidental corruption only.

(c) The encapsulation — five steps

1. Select an initialization vector (IV).
2. Concatenate the IV with the shared WEP key to form the RC4 seed.
3. Compute the 32-bit CRC over the entire MAC data field and append it as the ICV.
4. Encrypt data ‖ ICV together with the RC4 keystream generated from that seed.
5. Prepend the IV in the clear.

The transmitted MPDU is therefore [ IV | Key ID ][ RC4( data ‖ ICV ) ]. Two facts carry the marks. The ICV is computed before encryption and encrypted along with the data. And the IV travels unencrypted — it has to, because the receiver needs it to reconstruct the seed, and it is the most consequential design decision in the whole scheme.

The IV is 24 bits and the shared key is 40 or 104 bits, which is where the marketing terms "64-bit WEP" and "128-bit WEP" come from: 40 + 24 and 104 + 24. The width of the IV is not stated in the course textbook — see the callout for where it comes from.

(d) De-encapsulation — the receiver's steps

1. Read the IV, which arrived in the clear.
2. Concatenate it with the shared WEP key to re-form the seed.
3. Regenerate the RC4 keystream from that seed.
4. XOR the keystream against the ciphertext to recover data ‖ ICV.
5. Recompute the 32-bit CRC over the recovered data, and compare it with the recovered ICV. Equal, accept; different, discard.

The break — two linear things stacked on each other

Here is why the construction fails, and it is a two-line argument once you see it.

RC4 is a stream cipher, so encryption is ciphertext = plaintext ⊕ keystream. Flipping bit $k$ of the ciphertext therefore flips exactly bit $k$ of the recovered plaintext, and nothing else. An attacker who cannot read the plaintext can still make a chosen, predictable change to it.

A CRC is linear. For the raw polynomial remainder, $CRC(m\oplus \Delta )=CRC(m)\oplus CRC(\Delta )$; for standard CRC-32, with its initial and final XOR, the corresponding identity for equal-length inputs is

$$CRC(m\oplus \Delta )=CRC(m)\oplus CRC(\Delta )\oplus CRC(0)$$

where $CRC(0)$ is the CRC of a same-length all-zero string. Either way, the change the ICV needs depends only on $\Delta$ — the bits the attacker chose to flip — and not at all on the message.

Stack the two. The attacker picks $\Delta$, computes the compensating ICV flip from $\Delta$ alone, XORs $\Delta$ into the data region of the ciphertext and the compensating value into the ICV region, and sends it on. The receiver decrypts, recomputes the CRC, and finds it matches. The forged frame passes the integrity check, and the attacker never knew the plaintext or the key. The third exercise below runs exactly that and prints PASS.