Crypto-IT

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.

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.

The scheme of meet-in-the-middle attack

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.

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(k_a) log(2^len(k_a)) + 2^len(k_b) log(2^len(k_a))

• 2^len(k_a) - creating the table with all possible values of E_a(k_a,P),
• log(2^len(k_a)) - sorting the table with all possible values of E_a(k_a,P),
• 2^len(k_b) - calculating all possible values of D_b(k_b,C),
• log(2^len(k_a)) - 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.

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₁(k₁, E₂(k₂, P))
    P = D₂(k₂, D₁(k₁, C))
Where values E₂(k₂,P) can be find in the set which contains all possible values of the intermediate state S.

Both encryption algorithms E₁ and E₂ 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:

1. 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).
2. 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).
3. For all possible values of the intermediate state S:
   1. 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).
   2. 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).
   3. 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.

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.

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:

1. 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).
2. 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).
3. For all possible values of the intermediate state S₁:
   1. 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₁).
   2. 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₁).
   3. For all possible values of the intermediate state S₂:
      1. Calculate all possible values of D_b2(k_b2,S₂) (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...
      3. For all possible values of the intermediate state S_n:
         1. 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).
         2. 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).
         3. 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.

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.