How is OTR messaging with Socialist Millionaire Protocol (SMP) protected from Man In The Middle?

Question

So imagine the next situation:

Alice wants to initiate OTR instant messaging session with Bob but Joe is Man In The Middle.

Alice negotiates a shared secret 'X' with Joe (thinking he is Bob) using Diffie-Hellman.

Joe negotiates another shared secret 'Y' with Bob (who thinks Joe is Alice) using Diffie-Hellman.

Now Alice and Bob both know that they have established the so called "unverified OTR session", meaning that they are encrypted but none of them have verified their identities (none of them know about the existence of Joe).

So from what I understand, the Socialist Millionaire Protocol is supposed to be the solution of this problem. Alice has to match her shared secret 'X' with Bob's 'Y' and if they don't match - they will know that they have someone (Joe) in the middle, haven't they?

Anyway… Obviously X != Y because Joe is in the middle.

Now, I think I understand the steps in the Socialist Millionaire Protocol but still… I can't see what is stopping Joe from pretending in front of Alice that he is indeed Bob and use SMP to match with her their shared secret 'X' (which they both know)?

Am I missing something? What is the thing that makes OTR with SMP protected from MitM?

Answer 1

The problem, as laid out in George P's linked paper, is that "vanilla" Diffie-Hellman does not provide authentication as we generally define the term (the ability for each party to prove they are the real person or other entity they say they are, and for the other party to verify that proof). D-H at its core simply provides a secure means of key negotiation over an insecure network; an observer (someone tapping the line and sniffing packets read-only) could not decipher the derived key. However, someone controlling a node between the two parties, a true man in the middle, can pretend to be each of the parties in communication with the other, and eavesdrop on the conversation through the decryption and re-encryption.

To solve this problem using SMP, Alice and Bob must each know something Joe does not (a shared secret). They then use the SMP algorithm to verify that the other party knows the same shared secret. If the values produced during the proof match, then each party now knows that the other party knows the same secret, so they know (given the secret hasn't been compromised) they've been talking to the right person all along, and therefore they know that either or both of the two keys negotiated via D-H for the SMP proof are safe for use as a symmetric key for the conversation, because these keys are inherent in the transmission of the secret and could not have been spoofed without affecting the result of the SMP proof.

This isn't the only way to add authentication to D-H exchange protocols. The STS protocol, built on top of Diffie-Hellman, uses public key certificates that can be independently verified as genuine, and adds a couple of steps to the negotiation process. As soon as each party knows the shared key K, and thus knows or can calculate g^x mod p and g^y mod p (where x and y are the random secrets of each party generated for D-H), these two values are concatenated in a bitstream, hashed, encrypted asymmetrically using the sender's private key, then symmetrically using the shared key, before being sent to the other party who can (in theory) decrypt and verify the signature and thus the sender. Both sides must do this as part of the negotiation process, so this scheme incorporates two-way authentication into the system.

Answer 2

As far as I understand, SMP does not protect against MitM per se. The paper's authors clearly state,

Suppose that Alice and Bob are chatting online using OTR and decide to run the SMP, but have not previously selected a secret and possess no channel more secure than their current conversation. They can still select an appropriate secret in this case, but they will be more vulnerable to attack.

The SMP protocol is used to compare that shared secret without needing to send it in the clear, but the shared secret must already exist.

Otherwise, to Alice's eyes, there would be no difference between Bob and Joe. For the same reason, Alice and Joe would be identical to Bob's eyes. Which would lead to a perfect man-in-the-middle scenario.