Криптографиялық шабуыл: Кеңістік-уақыт айырбасы және ортада кездесу әдісі

Generic space–time tradeoff cryptographic attack
the cryptanalysis optimisation process

The meet in the middle attack (MITM), a known plaintext attack, is a generic space–time tradeoff cryptographic attack against encryption schemes that rely on performing multiple encryption operations in sequence. The MITM attack is the primary reason why Double DES is not used and why a Triple DES key (168 bit) can be brute forced by an attacker with 256 space and 2112 operations. attack. The MITM attack attempts to find the keys by using both the range (ciphertext) and domain (plaintext) of the composition of several functions (or block ciphers) such that the forward mapping through the first functions is the same as the backward mapping (inverse image) through the last functions, quite literally meeting in the middle of the composed function. For example, although Double DES encrypts the data with two different 56 bit keys, Double DES can be broken with 257 encryption and decryption operations. The multidimensional MITM (MD MITM) uses a combination of several simultaneous MITM attacks like described above, where the meeting happens in multiple positions in the composed function.

Diffie and Hellman first proposed the meet in the middle attack on a hypothetical expansion of a block cipher in 1977. Their attack used a space–time tradeoff to break the double encryption scheme in only twice the time needed to break the single encryption scheme. In 2011, Bo Zhu and Guang Gong investigated the multidimensional meet in the middle attack and presented new attacks on the block ciphers GOST, KTANTAN and Hummingbird 2. Triple DES uses a "triple length" (168 bit) key and is also vulnerable to a meet in the middle attack in 256 space and 2112 operations, but is considered secure due to the size of its keyspace.

If the keysize is k, this attack uses only 2k+1 encryptions (and decryptions) and O(2k) memory to store the results of the forward computations in a lookup table, in contrast to the naive attack, which needs 22·k encryptions but O(1) space.

This is a general description of how 2D MITM is mounted on a block cipher encryption. In two dimensional MITM (2D MITM) the method is to reach 2 intermediate states inside the multiple encryption of the plaintext. See below figure: