Why does DESX break if one removed post whitening?

Question

DESX uses whitening to strengthen against brute force attacks. What is an attack one could use to recover DESX's pre-whitening key with only two known ciphertext/plaintext pairs, given that the attacker can successfully disable the post-whitening step?

So far I have come up with this:

• The attacker could use an active fault injection attack to reduce DESX to return the results after round 1, effectively skipping rounds 2 to 16.
• Starting from the two ciphertexts, the attacker could then find all inputs to the s-boxes to recover all s-box input candidates.
• Starting from the two plaintexts, the attacker can find E(whiteningKey) xor roundKey combinations that produce the same s-box input candidates.

My problem now is this: The attacker has no way other than brute force to separate the whitening key from the round key in the equation above. Given the fact that brute force takes on average 2^55 attempts, this would be incredibly slow without special FPGA hardware.

Answer 1

The goal of DESX is to improve the security above the 56-bit level offered by DES. So an attack that's merely as expensive as brute-forcing the DES key is an attack, even if it's still rather expensive.

Define $E_{K,W}^\prime(P) = E_{K}(P\oplus W)$ and $D^\prime$ as its inverse. Then we can relate the two known pairs $(K_1,P_1)$ and $(K_2,P_2)$:

$$\begin{eqnarray} P_1\oplus P_2 &=& D^\prime(C_1)\oplus D^\prime(C_2) \\ &=& (D_K(C_1)\oplus W)\oplus (D_K(C_2)\oplus W) \\ &=& D_K(C_1) \oplus D_K(C_2) \end{eqnarray} $$

Since $P_1\oplus P_2 = D_K(C_1) \oplus D_K(C_2)$ only involves $K$ and not $W$ we can simply brute-force that 56-bit key, ignoring $W$, showing that using only pre-whitening does not improve security compared to plain DES. A similar argument can be applied to post-whitening. Note that this attack does not rely on the particular structure of DES (except having a key short enough to brute-force) and can be applied to any other blockcipher.

Answer 2

This is in fact a homework question for Christof Paar's lecture "Introduction to Cryptography 1" at the Ruhr University of Bochum.

In another task we had to recover the key (or parts of it) with a fault injection attack. The result was that $IP$ and $IP^{-1}$ was skipped and the output after the first round was the output of the whole encryption.

With that we could easily calculate the key (not the whitening key). We now know two pairs of $<plaintext, chiphertext>$ and the encryption key. To find the whitening key we have to check $2^{64}$ possible keys to check wether $DES(x \oplus k_{whitening}, k_{known}) == y$ for the given pairs $<x, y>$ and the recovered key.

But this seems harder than the $2^{56}$ keys we would have to check if we wanted to bruteforce the encryption key.

The question stated that Pre(or Post) whitening alone did not improve security. So maybe my thoughts are still wrong somehow.

I found another question but there is no clear answer.