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.
Description When trying to improve the security of a block cipher, a tempting idea is to encrypt the data several times using multiple keys. One might think this doubles or even n-tuples the security of the multiple-encryption scheme, depending on the number of times the data is encrypted, because an exhaustive search on all possible combinations of keys (simple brute force) would take 2n·k attempts if the data is encrypted with k-bit keys n times. The MITM attack is a generic attack which weakens the security benefits of using multiple encryptions by storing intermediate values from the encryptions or decryptions and using those to improve the time required to brute force the decryption keys. This makes a Meet-in-the-Middle attack (MITM) a generic space–time tradeoff cryptographic 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.
History 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.
Meet-in-the-middle (1D-MITM) Assume someone wants to attack an encryption scheme with the following characteristics for a given plaintext P and ciphertext C:
C = E N C k 2 ( E N C k 1 ( P ) ) P = D E C k 1 ( D E C k 2 ( C ) ) {\displaystyle {\begin{aligned}C&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(P))\\P&={\mathit {DEC}}_{k_{1}}({\mathit {DEC}}_{k_{2}}(C))\\\end{aligned}}}
where ENC is the encryption function, DEC the decryption function defined as ENC−1 (inverse mapping) and k1 and k2 are two keys. The naive approach at brute-forcing this encryption scheme is to decrypt the ciphertext with every possible k2, and decrypt each of the intermediate outputs with every possible k1, for a total of 2|k1| × 2|k2| (or 2|k1|+|k2|) operations. The meet-in-the-middle attack uses a more efficient approach. By decrypting C with k2, one obtains the following equivalence:
… excerpt ends here. Continue reading the full article.
