# Meet-in-the-middle attack

The meet-in-the-middle attack is one of the types of known plaintext attacks. The intruder has to know some parts of plaintext and their ciphertexts. Using meet-in-the-middle attacks it is possible to break ciphers, which have two or more secret keys for multiple encryption using the same algorithm. For example, the 3DES cipher works in this way. Meet-in-the-middle attack was first presented by Diffie and Hellman for cryptanalysis of DES algorithm.

C = E

_{b}(k

_{b}, E

_{a}(k

_{a}, P))

P = D

_{a}(k

_{a}, D

_{b}(k

_{b}, C))

- C is a ciphertext,
- P is a plaintext,
- E is an algorithm for encryption,
- D is an algorithm for decryption,
- k
_{a}and k_{b}are two secret keys

A following equation can be written for the cipher defined above:

D_{b}(k_{b}, C) = E_{a}(k_{a}, P)

Where C is the ciphertext, known to the intruder, which corresponds to the message P, also known to the intruder.

The first step of the attack is to create a table with all possible values for one side of the equation. One should calculate all possible ciphertexts of the known plaintext P created using the first secret key, so E_{a}(k_{a},P). A number of rows in the table is equal to a number of possible secret keys. It is good idea to sort the received table based on received ciphertexts E_{a}(k_{a},P), in order to simplify its further searching.

The second step of the attack is to calculate values of D_{b}(k_{b},C) for the second side of the equation. One should compare them with the values of the first side of the equation, computed earlier and stored in the table. The intruder searches a pair of secret keys k_{a} and k_{b}, for which the value E_{a}(k_{a},P) found in the table and the just calculated value D_{b}(k_{b},C) are the same.

It is possible to attack encryption systems, where two encrypting algorithms E are different (and used keys which have not necessarily the same lengths). In that case, in the first step the table is created for weaker of two algorithms.

## Meet-in-the-middle complexity

The meet-in-the-middle attack allows much quicker breaking of the cipher than using the ordinary brute force attack. Both time complexity and computational complexity depend on lengths of two encrypting keys k_{a} and k_{b}. They may be presented as a sum of two products:

2^{len(ka)} log(2^{len(ka)}) + 2^{len(kb)} log(2^{len(ka)})

- 2
^{len(ka)}- creating the table with all possible values of E_{a}(k_{a},P), - log(2
^{len(ka)}) - sorting the table with all possible values of E_{a}(k_{a},P), - 2
^{len(kb)}- calculating all possible values of D_{b}(k_{b},C), - log(2
^{len(ka)}) - searching the sorted table with values of E_{a}(k_{a},P)

If lengths of both keys k_{a} and k_{b} are the same and equal to Lk, then time complexity of the meet-in-the-middle attack can be presented as O(2^{Lk+1}). Memory usage can be approximated as O(2^{Lk}). Time complexity of the brute force attack is much greater and equals to approximately O(2^{Lk+Lk}). However, the brute force attack uses only O(1) memory.

## Meet-in-the-middle 2D

If an analyzed algorihtm can be divided into two simpler algorithms with one intermediate state and if the state is smaller than a secret key, then is is possible to perform the two-dimentional meet-in-the-middle attack. In modern block ciphers, algorithms often operate on small data blocks using the quite long secret key.

If it is possible to find the intermediate state S, then the analyzed cipher may can be presented as:

C = E_{1}(k_{1}, E_{2}(k_{2}, P))

P = D_{2}(k_{2}, D_{1}(k_{1}, C))

Where values E_{2}(k_{2},P) can be find in the set which contains all possible values of the intermediate state S.

Both encryption algorithms E_{1} and E_{2} can be broken using a two-dimentional meet-in-the-middle attack. A scheme of the two-dimentional attack is presented below:

In order to break a cipher using the two-dimensional meet-in-the-middle attack, one should take the following steps:

- Calculate all possible values of E
_{a1}(k_{a1},P) (for known P and all possible values of the key k_{a1}), then insert them to a table together with values of corresponding keys k_{a1}. The table should be sorted by calculated values of E_{a1}(k_{a1},P). - Calculate all possible values of D
_{b2}(k_{b2},C) (for known C corresponding to P and all possible values of the key k_{b2}), then insert them to a table together with values of corresponding keys k_{b2}. The table should be sorted by calculated values of D_{b2}(k_{b2},C). - For all possible values of the intermediate state S:
- Calculate all possible values of D
_{b1}(k_{b1},S) (for all possible values of the key k_{b1}), then insert them to a table together with values of corresponding keys k_{b1}. The table should be sorted by calculated values of D_{b1}(k_{b1},S). - Calculate all possible values of E
_{a2}(k_{a2},S) (for all possible values of the key k_{a2}), then insert them to a table together with values of corresponding keys k_{a2}. The table should be sorted by calculated values of E_{a2}(k_{a2},S). - Compare values in four created tables, searching for equality E
_{a1}(k_{a1},P) = D_{b1}(k_{b1},S) (one should receive a pair of keys (k_{a1},k_{b1})) and E_{a2}(k_{a2},S) = D_{b2}(k_{b2},C) (a pair of keys (k_{a2},k_{b2})). All combinations of the two pairs are the potential secret key for the whole cipher. One should check all received combinations with other known plaintext and ciphertexts blocks.

- Calculate all possible values of D

Usually four extracted keys k_{a1}, k_{b1}, k_{a2} and k_{b2} share some bits. One should
assign an independent variable to each bit in the keys and treat them separately.

## Meet-in-the-middle nD

It is possible that the attacked cipher can be divided into more than two simpler ciphers. In the general case one could find n intermediate states and n+1 encryption algorithms which can be break using the meet-in-the-middle method. A scheme of the multidimensional meet-in-the-middle attack is presented below:

In order to break a cipher using the multidimensional meet-in-the-middle attack, one should take the following steps:

- Calculate all possible values of E
_{a1}(k_{a1},P) (for known P and all possible values of the key k_{a1}), then insert them to a table together with values of corresponding keys k_{a1}. The table should be sorted by calculated values of E_{a1}(k_{a1},P). - Calculate all possible values of D
_{bn+1}(k_{bn+1},C) (dla znanego C opowiadającego P and all possible values of the key k_{bn+1}), then insert them to a table together with values of corresponding keys k_{bn+1}. The table should be sorted by calculated values of D_{bn+1}(k_{bn+1},C). - For all possible values of the intermediate state S
_{1}:- Calculate all possible values of D
_{b1}(k_{b1},S_{1}) (for all possible values of the key k_{b1}), then insert them to a table together with values of corresponding keys k_{b1}. The table should be sorted by calculated values of D_{b1}(k_{b1},S_{1}). - Calculate all possible values of E
_{a2}(k_{a2},S_{1}) (for all possible values of the key k_{a2}), then insert them to a table together with values of corresponding keys k_{a2}. The table should be sorted by calculated values of E_{a2}(k_{a2},S_{1}). - For all possible values of the intermediate state S
_{2}:- Calculate all possible values of D
_{b2}(k_{b2},S_{2}) (for all possible values of the key k_{b2}), then insert them to a table together with values of corresponding keys k_{b2}. The table should be sorted by calculated values of D_{b2}(k_{b2},S_{2}). - ...powtarzać analogiczne operacje aż do przejściowego stanu S
_{n}... - For all possible values of the intermediate state S
_{n}:- Calculate all possible values of D
_{bn}(k_{bn},S_{n}) (for all possible values of the key k_{bn}), then insert them to a table together with values of corresponding keys k_{bn}. The table should be sorted by calculated values of D_{bn}(k_{bn},S_{n}). - Calculate all possible values of E
_{an+1}(k_{an+1},S_{n}) (for all possible values of the key k_{an+1}), then insert them to a table together with values of corresponding keys k_{an+1}. The table should be sorted by calculated values of E_{an+1}(k_{an+1},S_{n}). - Analyze numbers in all created tables, comparing corresponding values of E
_{ai}with D_{bi}. One should receive a few combinations of corresponding pairs of keys (k_{ai},k_{bi}). The pairs should be checked for other known parts of plaintext and ciphertext and one combination of pairs should work encrypt and decrypt properly all data.

- Calculate all possible values of D

- Calculate all possible values of D

- Calculate all possible values of D

One can choose an arbitrary order of analyzed intermediate states. The states are smaller than encryption keys, so tables created in the multidimensional meet-in-the-middle attack have approximately the same size as tables created during the regular meet-in-the-middle attack.