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

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.

• This sounds like a homework exercise. Have you looked into meet-in-the-middle attacks? – user6584 Mar 22 at 0:12
• @user6584 joseph answered: "Yes, I get to the point where I can add 2 cipher- texts to eliminate k2. However I don't think MITM will work in this case? Since we cannot directly calculate DES^-1(k,c) ", sorry, cannot move comment at this point in time. – Maarten Bodewes Mar 22 at 19:06
• @fgrieu I edited that in from a comment from joseph as I found it important enough for it to be in the question. – Maarten Bodewes Mar 22 at 21:42

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)$$.

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}$$.

• $2^{56+64}$ is not almost the same as $2^{64}$ or $2^{56}$. And that answer does not give any hint at that more advanced meet-in-the-middle attack improving to $2^{56+64-\log m}$ – fgrieu Mar 29 at 6:40