Cryptography
diffie-hellman man-in-the-middle meet-in-the-middle-attack
Updated Fri, 15 Jul 2022 16:46:55 GMT

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


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?

Solution

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)

Comments (5)

  • +5 – I don't think that meet-in-the-middle necessarily involves a space-time trade-off. For example collision finding or computing ECDLP require little memory yet are a meet-in-the-middle attack. — Jan 13, 2016 at 08:59  
  • +3 – "halving the effort" is misleading as well. Typically it reduces the effort to the square-root of the original effort, halving the strength of the encryption in bits (which scaled like the logarithm of the effort). — Jan 13, 2016 at 09:00  
  • +1 – Thx, I will refine the answer. — Jan 13, 2016 at 09:02  
  • +1 – Thx @cygnusv, that made things very clear — Jan 13, 2016 at 09:09  
  • +3 – I think the name of meet-ITM just comes from solving the problem from both ends and, well, meeting in the middle. — Jan 13, 2016 at 09:18  

External Links

External links referenced by this document:

References