2
$\begingroup$

We know that 3DES is created with $E_{K_3}(D_{K_2}(E_{K_1}(m)))$ to extend DES's key length. Is it possible to extend it further by repeating this pattern? Perhaps using $E_{K_5}(D_{K_4}(E_{K_3}(D_{K_2}(E_{K_1}(m)))))$ for a 280 bit key.

$\endgroup$
  • $\begingroup$ of course, but why would you want to considering how slow DES is, and that its block size is only 64-bits? $\endgroup$ – Richie Frame Feb 16 '16 at 7:22
  • $\begingroup$ @RichieFrame This is more theoretical than practical. However, I can imagine a scenario where technology has moved on and 128-bit keys are considered too small, but legacy systems still only support DES. $\endgroup$ – Daffy Feb 16 '16 at 7:24
6
$\begingroup$

There is a very interesting paper that relates to this exact question (but you wouldn't guess it from the title). The paper is titled Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems. In Section 3, the paper considers the multiple encryption problem and gives novel attacks that are better than what you would expect (for a general multiple encryption $r$ times). For example, for 2DES there is an attack taking about $2^{56}$ time and $2^{56}$ space. You would therefore expect that 4DES would give you $2^{112}$ time and $2^{112}$ space. However, they show an attack that takes time $2^{112}$ and only space $2^{56}$.

In any case, in practice there is no good reason to use this. You are far better off using AES. DES's block size is too small, and it is very slow as it is (repeating 4 or 5 times will completely kill you).

$\endgroup$
  • 2
    $\begingroup$ Isn't 2^112 time and 2^56 space what you'd expect to get from extending the 2DES meet-in-the-middle attack to 4DES? $\endgroup$ – immibis Feb 16 '16 at 8:30
  • $\begingroup$ extending the 2DES MITM isn't straightforward due to the fact that meeting in the middle of 4DES does not mean all the 4 keys are the same . Such a property holds with high probability for 2DES, after testing another PC pair to make sure it's not a spurious meet in the middle collision. This kind of complication happens in the known MITM attack on 3DES as well. So something more sophisticated is most likely going on in the linked article. $\endgroup$ – kodlu Feb 16 '16 at 8:59
  • $\begingroup$ Indeed, something MUCH more sophisticated than the regular MITM is happening in the paper. $\endgroup$ – Yehuda Lindell Feb 16 '16 at 9:13
  • $\begingroup$ Hmm, tried it but I'm still alive. Although it doesn't make much sense generally, I can think of quite a few applications that could benefit from X-DES if DES is all that's available (in e.g. hardware). $\endgroup$ – Maarten Bodewes Feb 17 '16 at 0:13

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.