3
$\begingroup$

What is the best attack here?

$E_k(m)=DES_{k1}(DES_{k2}(m)) \oplus k3$

$\endgroup$
  • 2
    $\begingroup$ What research have you done? What have you tried? See, we do expect you to do a significant amount of research before asking here, including searching this site for DES-related Q&As that might shed light on your question. At worst it will help you frame a better question; at best it might even answer it. $\endgroup$ – e-sushi Jan 23 '16 at 9:54
  • $\begingroup$ The answer is same resources as double des. and I cant understand why... Hope someone here knows. $\endgroup$ – org Jan 23 '16 at 10:02
  • 1
    $\begingroup$ The best attack I see is brute-forcing $k_1$ and $k_2$ at the same time and xor-ing out $k_3$, for a total cost of $2^{112}$ with little memory. But that's pretty far from your 2DES claim. $\endgroup$ – CodesInChaos Jan 23 '16 at 10:32
  • $\begingroup$ @CodesInChaos So this would be as strong as TDES? That's pretty interesting if it is the case. $\endgroup$ – Maarten Bodewes Jan 23 '16 at 11:43
  • 1
    $\begingroup$ @otus Could be, but I made the title describe the method explicitly. With just one XOR I'm not 100% if whitening applies. Given the question, I'm not sure if we should use the term "key whitening" in the question title (it's fine in answers of course). $\endgroup$ – Maarten Bodewes Jan 23 '16 at 12:30
1
$\begingroup$

I cannot think of how to attack this using exactly the same resources as the classic meet-in-the-middle attack against double-DES, but there is a way to solve it with similar computational and memory resources (i.e. with about $2^{57}$ time and memory), but using $2^{56}$ chosen plaintexts and $2^{56}$ (adaptive) chosen ciphertexts.

First, notice that if we ask for the encryption of $m$, xor the ciphertext with a known constant $T$, and then ask for the decryption of $E_k(m) \oplus T$, the following equality holds: $$E_k^{-1}(E_k(m) \oplus T) = DES_{k2}^{-1}(DES_{k1}^{-1}(DES_{k1}(DES_{k2}(m)) \oplus k3 \oplus T \oplus k3))$$ $$= DES_{k2}^{-1}(DES_{k1}^{-1}(DES_{k1}(DES_{k2}(m)) \oplus T))$$ So we don't have to worry about the third key, and now we only need to figure out how to conduct a MitM attack against that construction using four applications of DES and two keys. We are going to do this in an inside-out fashion.

Step one: pick any 64-bit value, $A$, and for all $2^{56}$ possible candidate values of $k2$ (which I will denote $k2^*$), do the following:

  1. compute $B = DES_{k2^*}^{-1}(A)$,
  2. request $C = E_k(B)$,
  3. request $D = E_k^{-1}(C \oplus T)$.
  4. compute $F = DES_{k2^*}(D)$.

Store all $2^{56}$ values of $F$ in a hash table, along with the $k2^*$ candidate values associated with each.

Step two: For all $2^{56}$ possible candidate values of $k1$ (denoted $k1^*$), do the following:

  1. compute $G = DES_{k1^*}^{-1}(DES_{k1^*}(A) \oplus T)$,
  2. check if there is any $F$ such that $F = G$.

Any such collision will 'suggest' that $k1 = k1^*$ and $k2 = k2^*$ (the stored $k2^*$ candidate value for $F$), a suggestion that can be easily tested in the following manner:

If you know $m$, $m'$, and $E_k(m)$ and $E_k(m')$, then compute $DES_{k1^*}(DES_{k2^*}(m)) \oplus DES_{k1^*}(DES_{k2^*}(m'))$ and check if that equals $E_k(m) \oplus E_k(m')$. If so, then you almost certainly have the right keys. From there, $k3$ is trivially deducible.

| improve this answer | |
$\endgroup$
  • $\begingroup$ It is quite common that people think that chosen or adaptive attacks are helps in practice. No!. Neither linear nor Differential attacks are never implemented for DES. Only practical attack on DES is brute-force. Also one must consider the storage for MITM attack. Sorting as claimed can be performed with counting sorting, it will require 2x more space. $\endgroup$ – kelalaka Jan 23 '16 at 21:25
  • $\begingroup$ @user1820553 - the attack I outlined does not use linear or differential cryptanalysis. The attack does have time and memory requirements that are about the same as the classic MitM attack on double-DES (to within small constant factors). But unfortunately it must use chosen plaintext and ciphertext requests, which again have nothing at all to do with linear or differential attacks on single-DES. $\endgroup$ – J.D. Jan 23 '16 at 21:38
  • $\begingroup$ @MeysamGhahramani - a brute force attack with two plaintexts would use $2^{113}$ time, whereas my attack uses about $2^{58}$ time. Of course, the brute-force attack doesn't need chosen plaintexts and ciphertexts, and the memory requirements are basically nill, so in that sense the brute-force attack is greatly superior. But it is much slower. $\endgroup$ – J.D. Jan 23 '16 at 22:01
  • $\begingroup$ @J.D. Time complexity of step one is $2^{120}$, is it true? $\endgroup$ – Meysam Ghahramani Jan 23 '16 at 22:10
  • 1
    $\begingroup$ Nice, this seems to work. Of course, quite unrealistic in practice due to all the ciphertext queries. $\endgroup$ – otus Jan 24 '16 at 8:48

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.