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

Question

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?

Answer 1

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).

If this is a possibility, it's generally a good approach to use a Password Authenticated Key Exchange; this is a protocol that solves the socialist millionaire problem, and also generates a secret value which is the same on both sides if both sides have the same password. This secret value is useful because it can be used to derive keying data; then can be used to prevent MITM attacks after the PAKE protocol has completed.

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$).