Chosen plain-text Attack on DES-X with roughly $2^{64}$ DES operations

Question

Here is the quote from P. Rogaway,The security of DESX

"the effective key length of DESX with respect to key search is at least 55 + 63 - lg(m) bits"

where m is the number of chosen plaintext/ciphertext pairs.

So how can I attack DES-X with roughly $2^{64}$ DES operations assume we have unlimited storage?

I know that a simple exhaustive key search(~ $2^{120}$ DES operations) can be optimized to $2^{118}$DES operations by the key complementation property.

How can this property help if we have more plaintext/ciphertext pairs?

If we have $2^{64}$ $(p,c)$ pairs, how do we use that to recover all 3 keys? I can only think of using 2 $(p,c)$ pairs to get rid of $k_2$ by simply xor them.

Answer 1

I'll take the question as: with all plaintext/ciphertext pairs $(p,c=\operatorname{DESX}(p))$ at hand, how do we efficiently find the DESX key $(K_1,K_2,K_3)$?

The main idea is to observe that (independently of the DES complementation property), for any fixed $\delta\ne0$, $\operatorname{DESX}(p)\oplus\text{DESX}(p\oplus \delta)$ matches $\text{DES}_{K_2}(0)\oplus\text{DES}_{K_2}(\delta)$ when $p=K_1$, but few if any other values. We can compute the second quantity as a function of a candidate $K_2$, and search which $p=K_1$ matches in the plaintext/ciphertext pairs (there's in the order of one), then check if that guess is right.

The DES complementation property states that $\operatorname{DES}_{\overline K}(\overline p)=\overline{\operatorname{DES}_K(p)}$. This suggests using preferentially $\delta=\overline0$, which helps since $\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(\overline 0)=\operatorname{DES}_\overline{K_2}(0)\oplus\operatorname{DES}_\overline{K_2}(\overline 0)$.

The attack will thus go:

• Compute¹ all $\Delta(p)=\operatorname{DESX}(p)\oplus\text{DESX}(\overline p)$ for $p$ having its high-order bit clear, and keep track of them in a data structure allowing efficient search of which $p$ yields a given $\Delta(p)$. There's on average $1$ such 64-bit $p$ for each 64-bit $\Delta$, and always an even number since $\Delta(p)=\Delta(\overline p)$.
• For $K_2$ with the high-order bit clear and the other $55$ significant bits varying sequentially:
  • Compute² $\Delta=\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(\overline 0)$.
  • If a $p$ matches $\Delta$ (which has probability $\approx1-e^{-1/2}\approx39\%$ ):
    • Compute² $\Delta_1=\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(1)$.
    • For each candidate $p$ with $\Delta(p)=\Delta$ (our data structure lists those with the high-order bit clear, and we complement to get them all):
      • Test¹ if $\operatorname{DESX}(p)\oplus\text{DESX}(p\oplus1)=\Delta_1$. When that holds (which is extremely rare):
        • Test¹^,² if $\operatorname{DESX}(p)\oplus\text{DESX}(p\oplus2)=\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(2)$. When that holds, we almost certainly have³ the right $K_2$ and $K_1=p$. The matching $K_3$ is $\operatorname{DESX}(p)\oplus\operatorname{DES}_{K_2}(0)$.

Expected computational cost is $\approx(3-e^{-1/2})\,2^{54}\approx0.6\times2^{56}$ DES operations, ignoring memory and memory accesses (which in practice would likely dominate). The DES complementation property has halved the work by allowing to restrict to $K_2$ with high-order bit clear.

---

¹ Using our $(p,c)$ pairs.

² Using a DES engine.

³ Within polarity, which we can't find, because the DES complementation property implies that DESX key $(\overline{K_1},\overline{K_2},\overline{K_3})$ is equivalent to $(K_1,K_2,K_3)$.

Answer 2

There is an attack that has almost this complexity, without relying on any specific properties of DES. A standard meet-in-the-middle attack would have time complexity $2^{56+64}$. A more advanced meet-in-the-middle attack can improve this to $2^{56+64-\log m}$.