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?

  • $\begingroup$ 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$. $\;\;\;\;$ $\endgroup$
    – user991
    Mar 3, 2015 at 2:40
  • $\begingroup$ 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? $\endgroup$ Mar 3, 2015 at 16:55
  • $\begingroup$ 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}$ $\endgroup$
    – user991
    Mar 4, 2015 at 2:19

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


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.