7
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ It's a completely different attack in a completely different scenario. There's not really anything to compare, IMO. $\endgroup$ – otus Jan 13 '16 at 8:46
17
$\begingroup$

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)
$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – CodesInChaos Jan 13 '16 at 8:59
  • 2
    $\begingroup$ "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). $\endgroup$ – CodesInChaos Jan 13 '16 at 9:00
  • $\begingroup$ Thx, I will refine the answer. $\endgroup$ – cygnusv Jan 13 '16 at 9:02
  • $\begingroup$ Thx @cygnusv, that made things very clear $\endgroup$ – James Jan 13 '16 at 9:09
  • 1
    $\begingroup$ I think the name of meet-ITM just comes from solving the problem from both ends and, well, meeting in the middle. $\endgroup$ – otus Jan 13 '16 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.