The method of meeting in the middle in cryptanalysis

In a cryptanalysis by the method of meeting in the middle or by a meet-in-the-middle attack, a class of attacks on cryptographic algorithms is called, which asymptotically reduce the exhaustive search time due to the principle of divide and conquer, as well as an increase in the amount of required memory. This method was first proposed by Whitfield Diffie and Martin Hellman in 1977.  

Initial conditions

Given the open (unencrypted) and encrypted texts. The cryptosystem consists of h encryption cycles. Cycle keys are independent and have no common bits. The key K of the system is a combination of h-cyclic keys k1, k2 ... kh. The task is to find the key K.

Simple case solution

A simple example is dual sequential encryption with a block algorithm with two different keys {\ displaystyle K_ {1}} and . The encryption process looks like this:

,

Where Is a plaintext - ciphertext, and - single key encryption operation . Accordingly, the inverse operation - decryption - looks like this:

At first glance, it seems that the use of double encryption repeatedly increases the strength of the entire scheme, since now you need to sort through two keys, and not one. In the case of the DES algorithm, the resistance increases from 2 ⁵⁶ to 2 ¹¹² . However, it is not. The attacker can make two tables:

1. All values for all possible values ,
2. All values for all possible values .

Then it is enough for him to only find coincidences in these tables, i.e. such values and , what . Each match corresponds to a set of keys. that satisfies the condition.

For this attack, it took 2 ⁵⁷ encryption-decryption operations (only two times more than going through one key) and 2 ⁵⁷ memory. Additional optimizations — using hash tables, calculating only half of the keys (for DES, exhaustive search, in fact, requires only 2 ⁵⁵ operations) —can reduce these requirements. The main result of the attack is that sequential encryption with two keys increases the search time only twice.

Decision in general

Denote the transformation of the algorithm as Ek (a) = b, where a is the plaintext and b is ciphertext. It can be represented as a composition Ek1Ek2..Ekh (a) = b, where Eki is a cycle transformation on the key ki. Each key ki is a binary vector of length n, and the common key of the system is a vector of length n * h.

1. Filling the memory.

All values ​​of k '= (k1, k2..kr) are enumerated, that is, the first r cyclic keys. On each such key, k ', we encrypt the plaintext a - Ek' (a) = Ek1Ek2..Ekr (a) = S (i.e., pass r encryption cycles instead of h). We will consider S as a certain memory address and at this address we will write the value of k '. It is necessary to go through all the k 'values.

2. Key definition.

All possible k "= (kr + 1, kr + 2 ... kh) are enumerated. The ciphertext is decrypted on the received keys b - E-1k" (b) = E-1kh..E-1kr + 1 (b) = S '. If at address S 'is not empty, then we get out the key k' from there and we get the key candidate (k ', k ") = k.

However, it should be noted that the first received candidate k is not necessarily the true key. Yes, for data a and b, Ek (a) = b is performed, but on other plain text values ​​a 'ciphertext b', obtained from a 'on the true key, the equality may be violated. It all depends on the specific characteristics of the cryptosystem. But sometimes it is enough to get such a "pseudoequivalent" key. Otherwise, after the completion of the procedures, a certain set of keys {k ', k "...} will be received, among which there is a true key.

If we consider a specific application, the ciphertext and plaintext can be large (for example, graphic files) and represent a sufficiently large number of blocks for a block cipher. In this case, to speed up the process, you can encrypt and decrypt not all the text, but only its first block (which is much faster) and then, having received many candidates, look for the true key in it, checking it on the other blocks.

Notes.

If the set of keys of the cryptoalgorithm is closed relative to the composition, that is, for any keys zi and zj there is a key zk such that the result of encrypting any text in series on zi and zj is equal to the cipher code of the same number on zk, that is, F (zj, F (zi, x )) = F (zk, x), then you can use this property. Suppose we need to find the key zk. Then to find the key zk, you need to find an equivalent pair of keys zi, zj. This method of cryptanalysis is based on the “birthday paradox”. It is known that if we assume that birthdays are evenly distributed, then in a group of 24 people with a probability of 0.5 for two people, birthdays will coincide. In a general way, this paradox is formulated as follows: if a выбира n items are selected with a return from a certain aggregate size n, then the probability that two of them match is equal to 1-exp (-a2 / 2)

Let the plaintext x and its cipher code y be known. For the text x, we build a database containing a random set of keys z | and the corresponding ciprograms w = F (z |, x), and we arrange it according to the ciprograms w. The database size is O (n # {z}). Then we randomly select the keys z | | to decrypt texts y and the result of decryption v = F (z | |, y) is compared with the database. If the text v turns out to be equal to one of the ciprograms w, then the key z | z | | is equivalent to the desired key z. The time complexity of the method is O (C # {z} log # {z}). The log # {z} multiplier takes into account the complexity of sorting. The required memory is equal to O (C # {z} log # {z}) bits or OC blocks ({z}) blocks (it is assumed that the block length and key length differ by a limited constant).

The same method is applicable if the set of keys contains a sufficiently large subset that is a semigroup.

Another application of this method to a set that is not a semigroup can be demonstrated on hash functions. For example, to fake a signature, you need to find two texts that have the same hash image. After that, you can replace the signed message with another one that has the same hash image. The search for two such messages can be performed using the "meeting in the middle" method. The complexity of the search is O (n # {h}), where # {h} is the number of all possible hash images