1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This sounds like a homework exercise. Have you looked into meet-in-the-middle attacks? $\endgroup$ – user6584 Mar 22 at 0:12
  • $\begingroup$ @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. $\endgroup$ – Maarten Bodewes Mar 22 at 19:06
  • $\begingroup$ @fgrieu I edited that in from a comment from joseph as I found it important enough for it to be in the question. $\endgroup$ – Maarten Bodewes Mar 22 at 21:42
1
$\begingroup$

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

| improve this answer | |
$\endgroup$
0
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ $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}$ $\endgroup$ – fgrieu Mar 29 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.