User:Niklas Høj/MITM

Not to be confused with Man-in-the-Middle attack.

The Meet-in-the-Middle attack is a generic cryptographic attack, applicable to several cryptographic systems. The details of the internal structure of a specific system is therefore negligible to this attack.

When improving the security of a block cipher, a tempting idea is to do multiple successive encryptions using different keys. One might think this doubles or even n-tuples the security of the multiple-encryption scheme, but this is not the case.

The Meet-in-the-Middle attack splits the cipher into two sub-ciphers, and computes keys for each sub-cipher such that the forward mapping through the first sub-cipher is the same as the backward mapping (inverse image) through the last sub-cipher, whereby the sub-ciphers quite literally meet in the intermediate state between the two.

The Multidimensional MITM (MD-MITM) attack spilts the cipher into additional sub-ciphers, and uses a combination of several MITM-attacks like described above, where the meeting happens in guessed intermediate states between sub-ciphers.

Certainly, an exhaustive search on all possible combination of keys (simple bruteforce) would take 2^k·j attempts if j encryptions has been used with different keys in each encryption, where each key is k bits long. Using MITM or MD-MITM, this can reduced significantly. The MITM approach can also be combined with other kinds of attacks.

History

It was first developed as an attack on an attempted expansion of a block cipher by Diffie and Hellman in 1977 .

Diffie and Hellman, however, devised a time-memory tradeoff that could break the scheme in only double the time to break the single-encryption scheme.

In 2011, Bo Zhu and Guang Gong investigate the Multidimensional Meet-in-the-Middle attack and present new attacks on the KATAN32/48/64 block ciphers. In the same year Takanori Isobe presented an attack on the full GOST block cipher.

MITM (1D-MITM)

Consider a cipher that encrypts and decrypts a message P with key k to get a cipher text C:

 $C=ENC(k,P)$ 

 $P=DEC(k,C)$

Where ENC is the encryption function, DEC the decryption function defined as ENC_-1 (inverse mapping).

Now, suppose that the cipher can be split into two sub-ciphers f(k₁, x) and b(k₂, x) where k₁,k₂ are independent sub-keys of k, such that:

 $C=ENC_{f}(k_{2},ENC_{f}(k_{1},P))$ 

 $P=DEC_{b}(k_{1},DEC_{b}(k_{2},C))$

(Here f denotes forwards and b denotes backwards.)

The attacker can then compute and save ENC_f(k₁, P) for all possible keys k₁. Afterwards he can decrypt the ciphertext by computing DEC(k₂, C) for each k₂. For any matches between the two resulting sets, k₁,k₂ are candidates for the correct key.

To speed up the comparison, the ENC(k₁, P) set can be stored in an in-memory lookup table indexed by the result. Then each DEC(k₂, C) can be matched against the lookup table immediately to find the candidate keys.

This attack is one of the reasons why DES was replaced by Triple DES. Using a simple MITM attack, "Double DES" is broken in time 2⁵⁷ . However, Triple DES with a "triple length" (168-bit) key is vulnerable to a Meet-in-the-Middle attack in 2⁵⁶ space and 2¹¹².

An illustration of 1D-MITM attack

Once the matches are discovered, they can be verified with additional pairs of plaintexts and ciphertexts, until only one match remains.

Note that since all possible values of the block size are computed, the block size must be smaller than the key length for this attack to actually be an attack. Otherwise a simple brute force would be more efficient.

MITM algorithm

Compute the following:

• $SubCipher_{1}=ENC_{f_{1}}(k_{f_{1}},P)$ ∀ $k_{f_{1}}$ ∈ $K$:

and save each $SubCipher_{1}$ together with corresponding $k_{f_{1}}$ in a set A

• $SubCipher_{1}=DEC_{b_{1}}(k_{b_{1}},C)$ ∀ $k_{b_{1}}$ ∈ $K$:

and compare each new $SubCipher_{1}$ with the set A

When a match is found, keep k_f1,k_b1 as candidate key-pair in a table T. Test pairs in T on a new pair of (P,C) to confirm validity. If the key-pair does not work on this new pair, do MITM again on a new pair of (P,C).

MITM complexity

If the keysize is k, this simplest case attack uses only 2^k+1encryptions (or decryptions) (and O(2^k) memory in case a look-up table have been built for the set of forward computations) in contrast to the naive attack, which needs 2^2·k encryptions but O(1) space.

Two-dimensional-MITM (2D-MITM)

While 1D-MITM can be efficient, it can be expanded much further, starting with the Two-dimensional-MITM attack, abbreviated 2D-MITM. This method is preferable when the cipher can be split into 4 parts using different sub-keys of the master key. We assume these sub-keys to be independent for simplicity. We define a sub-cipher as a pair of such parts of the cipher, such that parts 1 and 2 will constitute the forwards and backwards computation of sub-cipher 1 etc.

Instead of meeting in the middle as described before, the 2D-MITM attack guesses an intermediate state between sub-ciphers 1 and 2, and does an MITM attack on each of the two sub-ciphers. See the illustrating figure on the right.

Note that, since ≥2D-MITM attacks guess all possible values of intermediate states, the attack will only actually be an attack if the size of the intermediate state is smaller than the master key length. If this is not the case, a simple brute force of the master key will be more efficient. The distinction between the size of intermediate states and the block size mentioned in the MITM section is valid because the two are not necessarily.

An illustration of 2D-MITM attack

2D-MITM algorithm

Compute the following:

• $SubCipher_{1}=ENC_{f_{1}}(k_{f_{1}},P)$ ∀ $k_{f_{1}}$ ∈ $K$

and save each $SubCipher_{1}$ together with corresponding $k_{f_{1}}$ in a set A

• $SubCipher_{2}=DEC_{b_{2}}(k_{b_{2}},C)$ ∀ $k_{b_{2}}$ ∈ $K$

and save each $SubCipher_{2}$ together with corresponding $k_{b_{2}}$ in a set B.

For each possible guess on an intermediate state s between $SubCipher_{1}$ and $SubCipher_{2}$ compute the following:

1 $SubCipher_{1}=DEC_{b_{1}}(k_{b_{1}},s)$ ∀ $k_{b_{1}}$ ∈ $K$

and for each match between this $SubCipher_{1}$ and the set A, save $k_{b_{1}}$ and $k_{f_{1}}$ in a new set T.

2 $SubCipher_{2}=ENC_{f_{2}}(k_{f_{2}},s)$ ∀ $k_{f_{2}}$ ∈ $K$

and for each match between this $SubCipher_{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 $(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 $2^{|k_{f_{1}}|}+2^{|k_{b_{2}}|}+2^{|s|}$⋅$(2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|})$ 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.

Multidimensional-MITM

The 2D-MITM attack can be naturally extended to a Multidimensional-MITM attack, abbreviated MD-MITM. As with 2D-MITM vs. MITM, this attack can be used when the attacked cipher can be split into three or more sub-ciphers, where each sub-cipher can be computed forwards and backwards with different keys to reach an intermediate state. Again, we assume the sub-keys of the sub-ciphers to be independente.

Extending the 2D-MITM approach, MD-MITM guesses intermediate states between all sub-ciphers and performs MITM attacks on each sub-cipher.

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

 $C=ENC_{f_{n}}(k_{n},ENC_{f_{n-1}}(k_{n-1},...ENC_{f_{1}}(k_{1},P))...)$ 

 $P=DEC_{b_{1}}(k_{1},DEC_{b_{2}}(k_{2},...DEC_{b_{n}}(k_{n},C))...)$

An illustration of MD-MITM attack

The MD-MITM has been used for cryptanalysis of (amongst others) the KATAN32/48/64 block cipher, where a 3D-MITM attack has significantly increased the number of attacked rounds.

MD-MITM algorithm

Compute the following:

• $SubCipher_{1}=ENC_{f_{1}}(k_{f_{1}},P)$ ∀ $k_{f_{1}}$ ∈ $K$:

and save each $SubCipher_{1}$ together with corresponding $k_{f_{1}}$ in a set $H_{1}$.

• $SubCipher_{n+1}=DEC_{b_{n+1}}(k_{b_{n+1}},C)$ ∀ $k_{b_{n+1}}$ ∈ $K$:

and save each $SubCipher_{n+1}$ together with corresponding $k_{b_{n+1}}$ in a set $H_{n+1}$.

For each possible guess on the intermediate state $s_{1}$ compute the following:

• $SubCipher_{1}=DEC_{b_{1}}(k_{b_{1}},s_{1})$ ∀ $k_{b_{1}}$ ∈ $K$:

and for each match between this $SubCipher_{1}$ and the set $H_{1}$, save $k_{b_{1}}$ and $k_{f_{1}}$ in a new set $T_{1}$.

• $SubCipher_{2}=ENC_{f_{2}}(k_{f_{2}},s_{1})$ ∀ $k_{f_{2}}$ ∈ $K$:

and save each $SubCipher_{2}$ together with corresponding $k_{f_{2}}$ in a set $H_{2}$.

For each possible guess on an intermediate state $s_{2}$ compute the following:

1 $SubCipher_{2}=DEC_{b_{2}}(k_{b_{2}},s_{2})$ ∀ $k_{b_{1}}$ ∈ $K$

and for each match between this $SubCipher_{2}$ and the set $H_{2}$, check also whether

it matches with $T_{1}$ and then save the combination of sub-keys together in a new set $T_{2}$.

2 ...

For each possible guess on an intermediate state $s_{n}$ compute the following:

a) $SubCipher_{n}=DEC_{b_{n}}(k_{b_{n}},s_{n})$ ∀ $k_{b_{n}}$ ∈ $K$

and for each match between this $SubCipher_{n}$ and the set $H_{n}$, check also whether

it matches with $T_{n-1}$, save $k_{b_{n}}$ and $k_{f_{n}}$ in a new set

$T_{n}$.

b) $SubCipher_{n+1}=ENC_{f_{n}+1}(k_{f_{n}+1},s_{n})$ ∀ $k_{f_{n+1}}$ ∈ $K$

and for each match between this $SubCipher_{n+1}$ and the set $H_{n+1}$, check also

whether it matches with $T_{n}$. If this is the case then:"

Use the found combination of sub-keys $(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 $2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|s_{1}|}$⋅$(2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}+2^{|s_{2}|}$⋅$(2^{|k_{b_{2}}|}+2^{|k_{f_{3}}|}+...))$

Regarding the memory complexity, it is easy to see that $T_{2},T_{3},...,T_{n}$ are much smaller than the first built table of candidate values: $T_{1}$ as i increases, the candidate values contained in $T_{i}$ must satisfy more conditions thereby fewer candidates will pass on to the end destination $T_{n}$.

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

$2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s_{n}|}...$

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 $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 $2^{|k|}/2^{|l|}$.

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

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

The part of brute force testing (testing the candidate key on new (P,C)-pairs, have time complexity $2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+2^{|k|-4b}$...

Clearly, for increasing multiples of b in the exponent, the number converges to zero. Thus the total time complexity is: $2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|s_{1}|}(2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}+2^{|s_{2}|}$⋅$(2^{|k_{b_{2}}|}+2^{|k_{f_{3}}|}+...))+2^{|k|-b}$

The conclusion on data complexity is by similar reasoning restricted by that around ⌈$|k|/n$⌉ (P,C)-pairs.

Below is a specific example of a simplest case 2D-MITM attack.

2D-MITM attack on 4DES

In order to demonstrate a simle 2D-MITM attack, consider DES applied 4 times successively with different keys, resulting in what we will call 4DES:

 $C=DES(k_{4},DES(k_{3},DES(k_{2},DES(k_{1},P))))$

DES has a block length of 64 bits and a key size of 56 bits.

We consider DES itself to be an atomic cipher which we cannot split into additional sub-ciphers. However, this is not necessary, as we can consider the first two applications of DES to be the forwards and backwards computations of sub-cipher 1, and the latter two applications of DES to be of sub-cipher 2.

With this, we can simply apply the attack described in the 2D-MITM section, and put in the numbers to calculate the complexities.

We get that the time complexity is:

 $2^{|k_{f_{1}}|}+2^{|k_{b_{2}}|}+2^{|s|}(2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|})+2^{|k|/b}$

 $=2^{56}+2^{56}+2^{64}(2^{56}+2^{56})+2^{224/64}$

 $=2^{57}+2^{64+57}+2^{3.5}$

 $\approx 2^{121}$

including the brute force filtering of false positives, and where b is the block size. This time complexity of 2¹²¹ is significantly more efficient than the brute force approach which has a time complexity of 2²²⁴.

Memory complexity is $\approx 2^{57}$, and data complexity is 4 plaintext/ciphertext pairs.

See also

• Birthday attack
• Triple DES
• Data Encryption Standard
• GOST (block cipher)
• Brute-force attack

References

Category:Cryptographic attacks