ου γαρ εστιν κρυπτον ο ου φανερον γενησεται ουδε αποκρυφον ο ου γνωσθησεται και εις φανερον ελθη
Wersja PL ENG Version

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.

A cipher, which is to be broken using meet-in-the-middle attack, can be defined as two algorithms, one for encryption and one for decryption. Each of them contains two simpler algorithms:
    C = Eb(kb, Ea(ka, P))
    P = Da(ka, Db(kb, C))
where:
  • C is a ciphertext,
  • P is a plaintext,
  • E is an algorithm for encryption,
  • D is an algorithm for decryption,
  • ka and kb are two secret keys

A following equation can be written for the cipher defined above:
    Db(kb, C) = Ea(ka, 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 Ea(ka,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 Ea(ka,P), in order to simplify its further searching.

The second step of the attack is to calculate values of Db(kb,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 ka and kb, for which the value Ea(ka,P) found in the table and the just calculated value Db(kb,C) are the same.

The scheme of meet-in-the-middle attack
scheme of meet-in-the-middle

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 ka and kb. They may be presented as a sum of two products:

    2len(ka) log(2len(ka)) + 2len(kb) log(2len(ka))

Where:
  • 2len(ka) - creating the table with all possible values of Ea(ka,P),
  • log(2len(ka)) - sorting the table with all possible values of Ea(ka,P),
  • 2len(kb) - calculating all possible values of Db(kb,C),
  • log(2len(ka)) - searching the sorted table with values of Ea(ka,P)

If lengths of both keys ka and kb are the same and equal to Lk, then time complexity of the meet-in-the-middle attack can be presented as O(2Lk+1). Memory usage can be approximated as O(2Lk). Time complexity of the brute force attack is much greater and equals to approximately O(2Lk+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 = E1(k1, E2(k2, P))
    P = D2(k2, D1(k1, C))
Where values E2(k2,P) can be find in the set which contains all possible values of the intermediate state S.

Both encryption algorithms E1 and E2 can be broken using a two-dimentional meet-in-the-middle attack. A scheme of the two-dimentional attack is presented below:

A scheme of the two-dimentional meet-in-the-middle attack

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 Ea1(ka1,P) (for known P and all possible values of the key ka1), then insert them to a table together with values of corresponding keys ka1. The table should be sorted by calculated values of Ea1(ka1,P).
  2. Calculate all possible values of Db2(kb2,C) (for known C corresponding to P and all possible values of the key kb2), then insert them to a table together with values of corresponding keys kb2. The table should be sorted by calculated values of Db2(kb2,C).
  3. For all possible values of the intermediate state S:
    1. Calculate all possible values of Db1(kb1,S) (for all possible values of the key kb1), then insert them to a table together with values of corresponding keys kb1. The table should be sorted by calculated values of Db1(kb1,S).
    2. Calculate all possible values of Ea2(ka2,S) (for all possible values of the key ka2), then insert them to a table together with values of corresponding keys ka2. The table should be sorted by calculated values of Ea2(ka2,S).
    3. Compare values in four created tables, searching for equality Ea1(ka1,P) = Db1(kb1,S) (one should receive a pair of keys (ka1,kb1)) and Ea2(ka2,S) = Db2(kb2,C) (a pair of keys (ka2,kb2)). 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 ka1, kb1, ka2 and kb2 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:

A scheme of the multidimensional meet-in-the-middle attack

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 Ea1(ka1,P) (for known P and all possible values of the key ka1), then insert them to a table together with values of corresponding keys ka1. The table should be sorted by calculated values of Ea1(ka1,P).
  2. Calculate all possible values of Dbn+1(kbn+1,C) (dla znanego C opowiadającego P and all possible values of the key kbn+1), then insert them to a table together with values of corresponding keys kbn+1. The table should be sorted by calculated values of Dbn+1(kbn+1,C).
  3. For all possible values of the intermediate state S1:
    1. Calculate all possible values of Db1(kb1,S1) (for all possible values of the key kb1), then insert them to a table together with values of corresponding keys kb1. The table should be sorted by calculated values of Db1(kb1,S1).
    2. Calculate all possible values of Ea2(ka2,S1) (for all possible values of the key ka2), then insert them to a table together with values of corresponding keys ka2. The table should be sorted by calculated values of Ea2(ka2,S1).
    3. For all possible values of the intermediate state S2:
      1. Calculate all possible values of Db2(kb2,S2) (for all possible values of the key kb2), then insert them to a table together with values of corresponding keys kb2. The table should be sorted by calculated values of Db2(kb2,S2).
      2. ...powtarzać analogiczne operacje aż do przejściowego stanu Sn...
      3. For all possible values of the intermediate state Sn:
        1. Calculate all possible values of Dbn(kbn,Sn) (for all possible values of the key kbn), then insert them to a table together with values of corresponding keys kbn. The table should be sorted by calculated values of Dbn(kbn,Sn).
        2. Calculate all possible values of Ean+1(kan+1,Sn) (for all possible values of the key kan+1), then insert them to a table together with values of corresponding keys kan+1. The table should be sorted by calculated values of Ean+1(kan+1,Sn).
        3. Analyze numbers in all created tables, comparing corresponding values of Eai with Dbi. One should receive a few combinations of corresponding pairs of keys (kai,kbi). 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.