Meet-in-the-middle attack

History

Diffie and Hellman first proposed the meet-in-the-middle attack on a hypothetical expansion of a block cipher in 1977. Their attack used a space–time tradeoff to break the double-encryption scheme in only twice the time needed to break the single-encryption scheme.

In 2011, Bo Zhu and Guang Gong investigated the multidimensional meet-in-the-middle attack and presented new attacks on the block ciphers GOST, KTANTAN and Hummingbird-2.

Meet-in-the-middle (1D-MITM)

Assume someone wants to attack an encryption scheme with the following characteristics for a given plaintext P and ciphertext C:

${\displaystyle \begin{array}{cc}C& ={\mathit{E}\mathit{N}\mathit{C}}_{k_2}({\mathit{E}\mathit{N}\mathit{C}}_{k_1}(P))\\ P& ={\mathit{D}\mathit{E}\mathit{C}}_{k_1}({\mathit{D}\mathit{E}\mathit{C}}_{k_2}(C))\end{array}}$

where ENC is the encryption function, DEC the decryption function defined as ENC⁻¹ (inverse mapping) and k₁ and k₂ are two keys.

The naive approach at brute-forcing this encryption scheme is to decrypt the ciphertext with every possible k₂, and decrypt each of the intermediate outputs with every possible k₁, for a total of 2^|k₁| × 2^|k₂| (or 2^{|k₁|+|k₂|}) operations.

The meet-in-the-middle attack uses a more efficient approach. By decrypting C with k₂, one obtains the following equivalence:

${\displaystyle \begin{array}{cc}C& ={\mathit{E}\mathit{N}\mathit{C}}_{k_2}({\mathit{E}\mathit{N}\mathit{C}}_{k_1}(P))\\ {\mathit{D}\mathit{E}\mathit{C}}_{k_2}(C)& ={\mathit{D}\mathit{E}\mathit{C}}_{k_2}({\mathit{E}\mathit{N}\mathit{C}}_{k_2}[{\mathit{E}\mathit{N}\mathit{C}}_{k_1}(P)])\\ {\mathit{D}\mathit{E}\mathit{C}}_{k_2}(C)& ={\mathit{E}\mathit{N}\mathit{C}}_{k_1}(P)\end{array}}$

The attacker can compute ENC_k1(P) for all values of k₁ and DEC_k2(C) for all possible values of k₂, for a total of 2^|k₁| + 2^|k₂| (or 2^|k₁|+1, if k₁ and k₂ have the same size) operations. If the result from any of the ENC_k1(P) operations matches a result from the DEC_k2(C) operations, the pair of k₁ and k₂ is possibly the correct key. This potentially-correct key is called a candidate key. The attacker can determine which candidate key is correct by testing it with a second test-set of plaintext and ciphertext.

The MITM attack is one of the reasons why Data Encryption Standard (DES) was replaced with Triple DES and not Double DES. An attacker can use a MITM attack to bruteforce Double DES with 2⁵⁷ operations and 2⁵⁶ space, making it only a small improvement over DES. Triple DES uses a "triple length" (168-bit) key and is also vulnerable to a meet-in-the-middle attack in 2⁵⁶ space and 2¹¹² operations, but is considered secure due to the size of its keyspace.

MITM algorithm

Compute the following:

• ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1={\mathit{E}\mathit{N}\mathit{C}}_{f_1}(k_{f_1},P),\mathrm{\forall }{k}_{f_1}\in K}$:

  and save each ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1}$ together with corresponding ${\displaystyle k_{f_1}}$ in a set A

• ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1={\mathit{D}\mathit{E}\mathit{C}}_{b_1}(k_{b_1},C),\mathrm{\forall }{k}_{b_1}\in K}$:

  and compare each new ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1}$ with the set A

When a match is found, keep ${\displaystyle k_{f_1},k_{b_1}}$ as candidate key-pair in a table T. Test pairs in T on a new pair of ⁠${\displaystyle (P,C)}$⁠ to confirm validity. If the key-pair does not work on this new pair, do MITM again on a new pair of ⁠${\displaystyle (P,C)}$⁠.

MITM complexity

If the keysize is k, this attack uses only 2^k+1 encryptions (and decryptions) and O(2^k) memory to store the results of the forward computations in a lookup table, in contrast to the naive attack, which needs 2^2·k encryptions but O(1) space.

Multidimensional MITM (MD-MITM)

While 1D-MITM can be efficient, a more sophisticated attack has been developed: multidimensional meet-in-the-middle attack, also abbreviated MD-MITM. This is preferred when the data has been encrypted using more than 2 encryptions with different keys. Instead of meeting in the middle (one place in the sequence), the MD-MITM attack attempts to reach several specific intermediate states using the forward and backward computations at several positions in the cipher.

Assume that the attack has to be mounted on a block cipher, where the encryption and decryption is defined as before:

${\displaystyle C={\mathit{E}\mathit{N}\mathit{C}}_{k_n}({\mathit{E}\mathit{N}\mathit{C}}_{k_{n-1}}(...({\mathit{E}\mathit{N}\mathit{C}}_{k_1}(P))...))}$

${\displaystyle P={\mathit{D}\mathit{E}\mathit{C}}_{k_1}({\mathit{D}\mathit{E}\mathit{C}}_{k_2}(...({\mathit{D}\mathit{E}\mathit{C}}_{k_n}(C))...))}$

that is a plaintext P is encrypted multiple times using a repetition of the same block cipher

The MD-MITM has been used for cryptanalysis of, among many, the GOST block cipher, where it has been shown that a 3D-MITM has significantly reduced the time complexity for an attack on it.

MD-MITM algorithm

Compute the following:

${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1={\mathit{E}\mathit{N}\mathit{C}}_{f_1}(k_{f_1},P)\mathrm{\forall }{k}_{f_1}\in K}$

and save each ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1}$ together with corresponding ${\displaystyle k_{f_1}}$ in a set ${\displaystyle H_1}$.

${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_{n+1}={\mathit{D}\mathit{E}\mathit{C}}_{b_{n+1}}(k_{b_{n+1}},C)\mathrm{\forall }{k}_{b_{n+1}}\in K}$

and save each ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_{n+1}}$ together with corresponding ${\displaystyle k_{b_{n+1}}}$ in a set ${\displaystyle H_{n+1}}$.

For each possible guess on the intermediate state ${\displaystyle s_1}$ compute the following:

${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1={\mathit{D}\mathit{E}\mathit{C}}_{b_1}(k_{b_1},s_1)\mathrm{\forall }{k}_{b_1}\in K}$

and for each match between this ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1}$ and the set ${\displaystyle H_1}$, save ${\displaystyle k_{b_1}}$ and ${\displaystyle k_{f_1}}$ in a new set ${\displaystyle T_1}$.

${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_2={\mathit{E}\mathit{N}\mathit{C}}_{f_2}(k_{f_2},s_1)\mathrm{\forall }{k}_{f_2}\in K}$

and save each ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_2}$ together with corresponding ${\displaystyle k_{f_2}}$ in a set ${\displaystyle H_2}$.

For each possible guess on an intermediate state ${\displaystyle s_2}$ compute the following:

• ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_2={\mathit{D}\mathit{E}\mathit{C}}_{b_2}(k_{b_2},s_2)\mathrm{\forall }{k}_{b_2}\in K}$

  and for each match between this ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_2}$ and the set ${\displaystyle H_2}$, check also whether

  it matches with ${\displaystyle T_1}$ and then save the combination of sub-keys together in a new set ${\displaystyle T_2}$.

• For each possible guess on an intermediate state ${\displaystyle s_n}$ compute the following:

1. ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_n={\mathit{D}\mathit{E}\mathit{C}}_{b_n}(k_{b_n},s_n)\mathrm{\forall }{k}_{b_n}\in K}$ and for each match between this ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_n}$ and the set ${\displaystyle H_n}$, check also whether it matches with ${\displaystyle T_{n-1}}$, save ${\displaystyle k_{b_n}}$ and ${\displaystyle k_{f_n}}$ in a new set ${\displaystyle T_n}$.
2. ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_{n+1}={\mathit{E}\mathit{N}\mathit{C}}_{f_n+1}(k_{f_n+1},s_n)\mathrm{\forall }{k}_{f_{n+1}}\in K}$ and for each match between this ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_{n+1}}$ and the set ${\displaystyle H_{n+1}}$, check also whether it matches with ${\displaystyle T_n}$. If this is the case then:"

Use the found combination of sub-keys ${\displaystyle (k_{f_1},k_{b_1},k_{f_2},k_{b_2},...,k_{f_{n+1}},k_{b_{n+1}})}$ on another pair of plaintext/ciphertext to verify the correctness of the key.

Note the nested element in the algorithm. The guess on every possible value on s_j is done for each guess on the previous s_j-1. This make up an element of exponential complexity to overall time complexity of this MD-MITM attack.

MD-MITM complexity

Time complexity of this attack without brute force, is ${\displaystyle 2^{|k_{f_1}|}+2^{|k_{b_{n+1}}|}+2^{|s_1|}}$⋅${\displaystyle (2^{|k_{b_1}|}+2^{|k_{f_2}|}+2^{|s_2|}}$⋅${\displaystyle (2^{|k_{b_2}|}+2^{|k_{f_3}|}+\cdots ))}$

Regarding the memory complexity, it is easy to see that ${\displaystyle T_2,T_3,...,T_n}$ are much smaller than the first built table of candidate values: ${\displaystyle T_1}$ as i increases, the candidate values contained in ${\displaystyle T_i}$ must satisfy more conditions thereby fewer candidates will pass on to the end destination ${\displaystyle T_n}$.

An upper bound of the memory complexity of MD-MITM is then

${\displaystyle 2^{|k_{f_1}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s_n|}\cdots }$

where k denotes the length of the whole key (combined).

The data complexity depends on the probability that a wrong key may pass (obtain a false positive), which is ${\displaystyle 1/2^{|l|}}$, where l is the intermediate state in the first MITM phase. The size of the intermediate state and the block size is often the same! Considering also how many keys that are left for testing after the first MITM-phase, it is ${\displaystyle 2^{|k|}/2^{|l|}}$.

Therefore, after the first MITM phase, there are ${\displaystyle 2^{|k|-b}\cdot 2^{-b}=2^{|k|-2b}}$, where ${\displaystyle |b|}$ is the block size.

For each time the final candidate value of the keys are tested on a new plaintext/ciphertext-pair, the number of keys that will pass will be multiplied by the probability that a key may pass which is ${\displaystyle 1/2^{|b|}}$.

The part of brute force testing (testing the candidate key on new ⁠${\displaystyle (P,C)}$⁠-pairs, have time complexity ${\displaystyle 2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+2^{|k|-4b}\cdots }$ , clearly for increasing multiples of b in the exponent, number tends to zero.

The conclusion on data complexity is by similar reasoning restricted by that around ${\displaystyle \lceil |k|/n\rceil }$ ⁠${\displaystyle (P,C)}$⁠-pairs.

Below is a specific example of how a 2D-MITM is mounted:

A general example of 2D-MITM

This is a general description of how 2D-MITM is mounted on a block cipher encryption.

In two-dimensional MITM (2D-MITM) the method is to reach 2 intermediate states inside the multiple encryption of the plaintext. See below figure:

2D-MITM algorithm

Compute the following:

${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1={\mathit{E}\mathit{N}\mathit{C}}_{f_1}(k_{f_1},P)\mathrm{\forall }{k}_{f_1}\in K}$

and save each ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1}$ together with corresponding ${\displaystyle k_{f_1}}$ in a set A

${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_2={\mathit{D}\mathit{E}\mathit{C}}_{b_2}(k_{b_2},C)\mathrm{\forall }{k}_{b_2}\in K}$

and save each ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_2}$ together with corresponding ${\displaystyle k_{b_2}}$ in a set B.

For each possible guess on an intermediate state s between ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1}$ and ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_2}$ compute the following:

• ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1={\mathit{D}\mathit{E}\mathit{C}}_{b_1}(k_{b_1},s)\mathrm{\forall }{k}_{b_1}\in K}$

  and for each match between this ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_1}$ and the set A, save ${\displaystyle k_{b_1}}$ and ${\displaystyle k_{f_1}}$ in a new set T.

• ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_2={\mathit{E}\mathit{N}\mathit{C}}_{f_2}(k_{f_2},s)\mathrm{\forall }{k}_{f_2}\in K}$

  and for each match between this ${\displaystyle {\mathit{S}\mathit{u}\mathit{b}\mathit{C}\mathit{i}\mathit{p}\mathit{h}\mathit{e}\mathit{r}}_2}$ and the set B, check also whether it matches with T for

  if this is the case then:

Use the found combination of sub-keys ${\displaystyle (k_{f_1},k_{b_1},k_{f_2},k_{b_2})}$ on another pair of plaintext/ciphertext to verify the correctness of the key.

2D-MITM complexity

Time complexity of this attack without brute force, is

${\displaystyle 2^{|k_{f_1}|}+2^{|k_{b_2}|}+2^{|s|}\cdot \left(2^{|k_{b_1}|}+2^{|k_{f_2}|}\right)}$

where |⋅| denotes the length.

Main memory consumption is restricted by the construction of the sets A and B where T is much smaller than the others.

For data complexity see subsection on complexity for MD-MITM.