2
$\begingroup$

enter image description here

The passage said that the computational load to attack DES-X can be reduced to approximately $2^{(56+64)}=2^{120}$ steps,and the storage of data sets should be $2^{64}$.

But I can't figure why it is time complexity $2^{120}$ and the (space complexity) of data sets should be $2^{64}$.

Can somebody help?

$\endgroup$
  • $\begingroup$ To avoid copyright issues et al, please edit your question and mention the source of what you quote. $\endgroup$ – e-sushi Oct 24 '14 at 17:55
5
$\begingroup$

Actually, because of DESX works, the meet-in-the-middle attack can be optimized to take $2^{119}$ $DES$ (and no $DES^{-1}$ operations), and no additional storage.

Here is how it works: let us assume that we have three known plaintext/ciphertext pairs $(P_1, C_1)$, $(P_2, C_2)$ and $(P_3, C_3)$. We know that:

$$C_1 = K_2 \oplus DES( K, K_1 \oplus P_1 )$$

$$C_2 = K_2 \oplus DES( K, K_1 \oplus P_2 )$$

In a standard meet-in-the-middle attack, we would rewrite the first equation as:

$$C_1 \oplus K_2 = DES( K, K_1 \oplus P_1 )$$

and create lists of the two sides (using possible values of $K, K_1, K_2$), and search for common values; the lists (actually, we'd create a list only for the left side, as it's smaller) would account for the additional storage.

However, in the case of DESX, we can simplify this by combining the two equations as:

$$C_1 \oplus C_2 = DES( K, K_1 \oplus P_1 ) \oplus DES( K, K_1 \oplus P_2 )$$

We know the value on the left side; with $2^{119}$ DES operations, we can go through all possible combinations of $K, K_1$ that make this equation work (note: why $2^{119}$ and not $2^{121}$? Because there are two separate artifacts that allow us to reduce the search space by a factor of two each: the first is the observation if a value $K_1$ makes it work, so does the value $K'_1 = K_1 \oplus P_1 \oplus P_2$; hence if we test one $K_1$ value and it doesn't work, we can skip the corresponding $K'_1$ value; the second is the key complementation property of DES; that is, if $K, K_1$ satisfies the above equation, so will $\bar{K}, \bar{K_1}$; hence if we test one $K$ and it doesn't work, we know that $\bar{K}$ wouldn't either. So we test the above with $2^{55}$ $K$ values and $2^{63}$ $K_1$ values, and each test involves 2 DES operations, for a total of $2 \times 2^{55} \times 2^{63} = 2^{119}$ DES evaluations). And, because we're not explicitly making any lists, we don't use any extra memory.

When we find a $K, K_1$ pair that makes this work, we can compute the correspond $K_2$ values, and test it out with our third known plaintext/ciphertext pair; this additional checking is rare (once out of $2^{64}$ pairs tested), and so can be ignored when doing complexity computations.

And, this observation can be extended to show that the attack against DESX can be performed even faster if we have more plaintext/ciphertext pairs.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I am trying to understand the why "$2^{119}$ and not $2^{121}$" part and am getting lost at this point -- "if a value $K_1$ makes it work, so does the value $K'_1 = K_1 \oplus P_1 \oplus P_2$". Where does the $K'_1$ come from? $\endgroup$ – golem Mar 5 '17 at 5:08
  • $\begingroup$ @golem: $K_1'$ satisfies $C_1 \oplus C_2 = DES( K, x \oplus P_1 ) \oplus DES( K, x \oplus P_2 )$ if and only if $K_1$ does; hence if we test a value $K_1$, and find that it doesn't, we have no need to test $K_1'$. $\endgroup$ – poncho Mar 5 '17 at 22:11

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.