What is difference between meet in the middle attack and man in the middle attack?

Question

From my understanding man-in-the middle attack works as follow: Alice and Bob agreed to use Diffie-Hellman using $a$ and $q$. Alice sends $Y_A$. Before it reaches Bob,
Charlie intercepts it and sends $Y_{C1}$ instead. Bob believes to have agreed on a key $K_B$ with Alice, but the key is actually only shared by Bob and Charlie since $K_B = a^{X_{C1}X_B} \mod q$.

Bob sends back $Y_B$, and it is again intercepted by Charlie. Charlie sends $Y_{C2}$ instead, and Alice sees that Bob has replied. Alice believes to have agreed on a key $K_A$ with bob, but they key is actually only shared by Alice and Charlie since $K_A = a^{X_{C1}X_A} \mod q$.

So how does meet-in-the middle attack compare to this example?

Answer 1

These are completely different things:

• Man-in-the-middle is an active attack to a cryptographic protocol, where the attacker is, effectively, in between the communications of two users, and is capable of intercepting, relying, and (possibly) altering messages. In this case, the meaning of "in the middle" is direct: the attacker is in the middle of two communicating users.
• Meet-in-the-middle is a type of cryptanalytic attack that uses some sort of time-space trade-off to drastically reduce the effort to perform a brute-force attack (e.g., transforming an attack that requires $2^{128}$ time into one that takes $2^{64}$ time and $2^{64}$ space). In this case, the name of the attack comes from the expression "let's meet in the middle", which means "to make a compromise". It may also refer to a type of attack over certain block ciphers, where the attacker decompose the problem in two halves and proceeds on each part separately.

The biggest difference between these attacks is that the first one is interactive (i.e., the attacker must participate in the communication), while the second one isn't.

The confusion may come from the fact that certain protocols could receive both type of attacks. For example, in your question you are talking about the Diffie-Hellman key exchange:

• A Man-in-the-middle attack to this protocol is exactly the one you describe
• A Meet-in-the-middle attack focus on extracting a private key by finding the discrete logarithm using some time-space trade-off (e.g., baby-step giant-step algorithm)