2
$\begingroup$

How can I apply the Meet-in-the-Middle attack to the 3DES algorithm, and why does the literature say that 3DES is more secure than DES?

$\endgroup$
  • $\begingroup$ Your combined question suggest you haven't done sufficient research. For example, 3DES uses DES as a component and involves twice the key material, which makes brute force much less practical. $\endgroup$ – Thomas M. DuBuisson May 13 '15 at 18:09
  • $\begingroup$ i did , but I can't find the appropriate answer , can you answer the first part ? how can i apply meet in the middle attack on 3DES algorithm ? $\endgroup$ – hadil da'na May 13 '15 at 18:14
  • $\begingroup$ I'm not seeing that this question is a true duplicate; various other answers do not really describe the basic MitM applied to 3DES. The closest I found is in this question but the table is built my enumerating 2 keys rather than 1, which makes it require a ludicrous amount of memory; hence my answer. $\endgroup$ – fgrieu May 14 '15 at 17:36
3
$\begingroup$

The meet-in-the-middle attack on ciphers like $C=E^2_K(P)=E_{K1}(E_{K2}(P))$ works as follows.

Let's assume you're given a known-plaintext pair $(P_1,C_1)$ and a known-plaintext pair $(P_2,C_2)$
You now build a list (by brute-force) containing the pairs $(I,K1)$ for every possible value of $K1$ ($2^{56}$ for DES) with $I=E_{K1}(P_1)$.
Constructing this list takes you $2^n$ blocks of storage with $n$ being the keysize.
You now simply call the decryption function $D_{K2}(C)$ until you obtain a value of $I$ you already stored in your table. If you find this one, which takes you at most $2^n$ operations, you simply counter-check with your second pair, using the relation: $C_2=E_{K1}(E_{K2}(P_2))$. If this holds, you can be pretty sure to have found the correct key. As you have to perform $2^n$ operations to obtain the table and $2^n$ operations to find the correct key you need $2^n+2^n=2*2^n=2^{n+1}$ operations and $2^n$ storage.

Let's see, how can I use that on 3DES (3-key)?
For the meet-in-the-middle attack to work, it is not required for the $E_K()$ to be the same. So you simply define the second one to be $E_{K2}=D_{K2}(E_{K3}(P))$. Then, in the first paragraph you'll need $2^{56}$ operations to construct the table containing $2^{56}$ entries. Now you simply perform the third paragraph of the above attack and need another $2^n$ operations with $n$ being 112 in this case as it is a double-application of DES which can't be attacked by meet-in-the-middle by itself as it is part of such an attack. The attack thus requires $2^{56}+2^{112}\approx 2^{112}$ operations and $2^{56}$ storage.

Now, how's the relation with 3DES (2-key)?
3DES is defined as $C=E_{K1}(D_{K2}(E_{K1}(P)))$. You can't apply the above attack to 3DES, as you now have three encryption / decryption operations.
The best attack to 3DES is due to van Oorschot and Wiener and goes as follows.

  1. Guess the first intermediate value, $a$.
  2. Tabulate, for each possible value of $K1$, the second intermediate value, $b$, when the first intermediate value is $a$ using known plaintext $b=D_{K1}(C)$, for all $p$ given plaintext-ciphertext pairs.
  3. Look up, for each possible $K2$, elements with a matching second intermediate value, b: $b=E_{K2}(a)$.
  4. The probability of a match is $p/{2^m}$ with $m$ being the block size.

The whole attacks requires $2^{n+m}/p$ time and $p$ storage.

(the attacks can also be found in Schneier's Applied Cryptography)

Why is 3DES more secure than DES?
Because the keyspace is larger. 3DES has a keyspace with 112-bits in size whereas DES has only $2^{56}$ keys, which is brute-force-able.

$\endgroup$
  • 1
    $\begingroup$ He didn't specify, but 3DES with 3 independent keys (key space of 168 bits) can be attacked with MITM, thus his question. See crypto.stackexchange.com/questions/6345/… and crypto.stackexchange.com/questions/16073/… $\endgroup$ – Steve Peltz May 13 '15 at 19:52
  • $\begingroup$ @StevePeltz, thank you for pointing that out. I'll edit the answer. $\endgroup$ – SEJPM May 13 '15 at 19:53
  • $\begingroup$ @fgrieu thank you, I'll fix that in sunday AS I'm away until then. $\endgroup$ – SEJPM May 15 '15 at 8:43
  • $\begingroup$ (re-revised) In the section on attacking 2-key 3DES: odds of having made a valid guess at step 1, stated at step 4, are $p/{2^m}$. The storage requirement is OK (I had to get at the article to confirm that). $\;$ Minor TeXpo in the section on attacking 3-key 3DES: $2^56$ should be $2^{56}$ $\endgroup$ – fgrieu May 15 '15 at 9:10
2
$\begingroup$

3DES encryption with independent keys $(K_1,K_2,K_3)$ transforms a 64-bit plaintext block $P$ into ciphertext $C=E_{K_3}(D_{K_2}(E_{K_1}(P)))$, where $E$ and $D$ are DES encryption and decryption.

The basic Meet-in-the-Middle attack against this form of 3DES assumes 3 different known plaintext/ciphertext pairs $(P_i,C_i)$, and (theoretically) works as follows:

  1. For each $2^{56}$ values of $K_1$, compute $R=E_{K_1}(P_0)$ and from the results build in memory a data structure that allows quickly finding the value(s) of $K_1$ yielding a particular 64-bit result. This can be done with about $2^{62}$ bits of memory. That's $2^{25}$ Flash memory silicon dies each 128Gibit.
  2. For each $2^{112}$ values of $K_2,K_3$ compute $R=E_{K_2}(D_{K_3}(C_0))$ and try to find that $R$ in the table; if it is there (which will be the case about 1 time in 256)
    • get the corresponding $K_1$ (there's rarely several, and we can ignore that with low odds of failure); we know that $C_0=E_{K_3}(D_{K_2}(E_{K_1}(P_0)))$; check if $C_1=E_{K_3}(D_{K_2}(E_{K_1}(P_1)))$ and $C_2=E_{K_3}(D_{K_2}(E_{K_1}(P_2)))$, in which case we have the right key (with residual odds of the contrary about $2^{-24}).

Problem is, that's never going to work. We expect to perform each sub-step of 2 about $2^{111}$ times, performing one memory lookup (and like one DES, which is comparatively cheap) per loop. If we managed to operate each of our Flash memory silicon die at a rate of 100M lookups per second, we're talking 24 billion years (more than the estimated age of the known universe). Using more memory will speed up things, but not to the point of making that attack realistic.

Improved variants making less memory fetches exist, apparently culminating with section 5.3 on MitM in Paul C. van Oorschot and Michael J. Wiener: Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1). That remains impractical with full 3DES as considered above; but the same authors have an attack (only remotely related to MitM) worth consideration on 3DES with $K_3=K_1$ (known as TDEA Keying Option 2), see this question.

On the other hand, we can break DES with little memory and about $2^{55}$ DES, that was already practical in 1998 at relatively modest cost.

$\endgroup$
  • $\begingroup$ Is this EDE or EEE sample? EDE as used in 3DES would require the mentioned ED step 2 - so if I am not mistaken either the initial definition or the step 2 need to be adjusted. $\endgroup$ – eckes Apr 24 '17 at 7:44
  • 1
    $\begingroup$ @eckes: indeed; did I manage to fix it ? $\endgroup$ – fgrieu Apr 24 '17 at 11:02

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