meet-in-the-middle attack

What is a meet-in-the-middle attack?

Meet-in-the-middle is a known plaintext attack that can greatly reduce the number of brute-force permutations required to decrypt text that has been encrypted by more than one key. Such an attack makes it much easier for an intruder to gain access to data.

A meet-in-the-middle attack targets block cipher cryptographic functions. The intruder applies brute-force techniques to both the plaintext, which is ordinary text before it is encrypted, and the ciphertext, or encrypted text that has been transformed from plaintext, of a block cipher.

The intruder then attempts to encrypt the plaintext according to various keys to achieve an intermediate ciphertext, or text that has only been encrypted by one key. Simultaneously, the intruder attempts to decrypt the ciphertext according to various keys, seeking a block of intermediate ciphertext that is the same as the one created by encrypting the plaintext. If there is a match of intermediate ciphertext, it is highly probable that the key used to encrypt the plaintext and the key used to decrypt the ciphertext are the two encryption keys used for the block cipher.

The name for this exploit comes from the method: Because the intruder tries to break the two-part encryption method from both sides simultaneously, a successful effort enables the intruder to "meet in the middle" of the block cipher.

How does a meet-in-the-middle attack work?

A meet-in-the-middle attack uses two known assets -- a plaintext block and an associated ciphertext block -- to decipher the keys originally used to facilitate the encryption. The attack involves working from either end of the encryption chain toward the middle, as opposed to trying brute-force permutations from one end of the encryption process to the other. Essentially, meet-in-the-middle attacks involve breaking the encryption process into simpler, separate steps instead of one long, complex chain.

Meet-in-the-middle attacks are often executed to decode multiple data encryption standard (DES) techniques. A double DES, for example, uses two encryption keys to transform its plaintext inputs into ciphertext outputs. This method of encryption uses its two unique keys to perform two encryption stages. The goal of a meet-in-the-middle attack, in this case, is to use the intermediate values -- the values between the encryption stages -- to solve for all used encryption keys; which for a double DES, is two.

When DES was first created, experts believed that longer key lengths would increase the difficulty of brute-force attacks because the entropy -- or the degree to which randomness has been applied during encryption -- required to decipher the encryption process would be exponentially larger. A single DES, for example, has an entropy of 2⁵⁶. When two DES are used in combination to form a double DES encryption, the entropy is 2¹¹². This does not mean that a double DES is twice as strong, but rather that a double DES is 2⁵⁶ times as strong. This figure refers to the number of possible encryption keys a hacker must attempt in order to produce the same ciphertext as the original double DES.

Despite initial assumptions, however, multiple instances of DES, such as double DES, proved to be vulnerable to meet-in-the-middle attacks. This method of attack enables hackers to bypass the longer keys by significantly reducing the entropy of permutations.

The implications of meet-in-the-middle attacks

Although a meet-in-the-middle exploit can make the attacker's job easier, it cannot be conducted without a piece of plaintext and corresponding ciphertext. That means the attacker must have the capacity to store all possible intermediate ciphertext values from both the brute-force encryption of the plaintext and decryption of the ciphertext. While cumbersome, it is not impossible or unrealistic. In fact, the efficacy of meet-in-the-middle attacks has resulted in DES techniques becoming less popular. While double DES is not used very often, triple DES is still incorporated in some instances. However, triple DES, like double DES, can be brute forced by an attacker using meet-in-the-middle attacks.

Meet-in-the-middle is a passive attack, which means that although the intruder can access messages, in most situations, they cannot alter them or send their own. Passive attacks like this can be conducted over extended periods of time, depending on the encryption method the hackers are trying to decipher. Similarly, the attack is not practical for the average hacker, and is more likely to be used in corporate or international espionage or similar settings that can accommodate the storage required to carry it out.

Meet-in-the-middle vs. man-in-the-middle

While the names are similar, a meet-in-the-middle attack is very different from a man-in-the-middle attack. A man-in-the-middle attack involves a malicious user eavesdropping or altering the conversation between two or more individuals in order to carry out an attack. The attacker, in this case, takes a position in the middle of an exchange while hiding or disguising their activity so they can intercept and possibly alter the data flowing back and forth. This type of attack is typically more interactive than a meet-in-the-middle attack and does not normally involve brute-force encryption key tests.

Learn how man-in-the-middle attacks occur and what steps you can take to prevent them from affecting your organization.