# What is the advantage of using the socialist millionaire protocol to authenticate vs HMACing some random number?

Say Alice and Bob have a shared secret $s$.

Alice and Bob establish an encrypted channel and verify that it hasn't been MitM'ed by exchanging $r_1$ and $r_2$, where $r_1$ and $r_2$ are randomly generated by Bob and Alice respectively and sent over the channel. Alice computes $\operatorname{HMAC}(C \mathbin\| r_1, s)$ and Bob computes $\operatorname{HMAC}(C\mathbin\|r_2, s)$ where $C = \operatorname{HASH}(\text{Communication-channel})$ and they exchange values:

1. A & B: $C = \operatorname{HASH}(\text{Communication-channel})$

2. A → B: $r_1$, $\operatorname{HMAC}(C \mathbin\| r_1, s)$,
B → A: $r_2$, $\operatorname{HMAC}(C \mathbin\| r_2, s)$

3. A & B recalculate $\operatorname{HMAC}(C \mathbin\| r_2, s)$ and $\operatorname{HMAC}(C \mathbin\| r_1, s)$ and verify that they match the received values.

At this point Alice should trust that Bob knows $s$ and has the same value of $C$, and vice versa. If Eve had carried out a MITM attack on the channel, the HMACs would fail, because $C$ would be different for Alice and Bob.

What differences would there be if the socialist millionaire protocol was used to establish that $s$ is shared?

• What is your 3-argument version of HMAC? $\:$ The differences are that $s$ could instead just be a shared password and they wouldn't need $HASH$. $\;\;\;\;$ – user991 Mar 3 '15 at 2:40
• Sorry I meant to use concatenation there, instead of using multiple arguments. So the main advantage of SMP is that you do not need to rely on a collision resistant hash function? What about prevention of MITM attacks? – placeybordeaux Mar 3 '15 at 16:55
• For that, either $C$ would need to be fixed-length or both $r_1$ and $r_2$ would need to be fixed-length. $\hspace{.53 in}$ – user991 Mar 4 '15 at 2:19

The problem with the HMAC-based solution you drew up is if the shared secret $s$ has low entropy; for example, it's actually a password that could conceivably be in a dictionary.
In this case, someone could listen to the exchange $r_1, \operatorname{HMAC}(C \mathbin\| r_1, s)$, and go through his dictionary of possible values of $s$, and see if any one of them makes the HMAC be the expected value; if so, he can MITM (or just pretend to be either Alice or Bob).
Now, one thing that a PAKE protocol can't prevent is someone making a guess at the shared secret $s$, and attempting to log in using that value -- if his authentication attempt is successful, he knows that he guessed correctly. What PAKE can do is prevent any more efficent approaches; to test 1000 possible passwords, the attacker would need to attempt 1000 authentication requests.
On the other hand, if you have a strong $s$ which is immune to a dictionary attack (for example, it's a 128 bit random number), and you don't care about Perfect Forward Secrecy (which a PAKE will also provide), then a PAKE is overkill -- your simpler approach using HMAC may be preferable (and, don't forget, you would need to bind the rest of the conversation with the authentication exchange, such as generating a shared key based on $s$).