Key establishment from secret answer to a question using Socialist Millionaire Protocol I have read this as telling that two parties sharing a low-entropy secret (such as a secret answer to a question) can use it to establish a high-entropy shared secret key across a classical insecure channel, with help of the Socialist Millionaire Protocol.

How is that achieved? Quantitatively, what's the probability for a MitM attack to succeed at least once in $n$ attempt?



Or asked differently, but equivalently: How to build a password-authenticated key exchange (PAKE) from a Socialist Millionaire Protocol (SMP)?
I have read this as telling that two parties sharing a low-entropy
  secret (such as a secret answer to a question) can use it to establish
  a high-entropy shared secret key across a classical insecure channel,
  with help of the Socialist Millionaire Protocol.


First, I think this isn't usually done, because SMP protocols tend to be not faster than key exchanges and because you can build an SMP protocol out of a password-authenticated key exchange (PAKE) by simply afterwards comparing whether the resulting keys are equal (eg by using them for a symmetric transport layer and sending a pre-agreed value both directions).


  Quantitatively, what's the probability for a MitM attack to succeed at
  least once in $n$ attempt?


I would suppose any such protocol enjoys similar security properties to your standard PAKE protocol, that is, if you break into one of the parties it's game over, but you don't learn anything about the password from the transcript and you can only test one guess for the password per connection attempt. So if the process of picking the password has entropy $E$, your chance of getting it right (per online connection attempt) should be $2^{-E}$.


  How is that achieved?


One protocol, I just came up with goes as follows:


Run un-authenticated Diffie-Hellman between the two parties $A$ and $B$ to get the shared secrets $m_A,m_B$. Note that if there is an active MitM attacker $m_A\neq m_B$.
Let $p$ be the password the two parties share. Formulate $\langle p,m_A\rangle$ and $\langle p,m_B\rangle$, e.g. as $\langle x,y\rangle=\operatorname{HMAC-SHA256}_y(x)$, i.e. pair them up somehow, so that the result of $\langle\cdot,\cdot\rangle$ may only be learned by somebody knowing both inputs.
Run a SMP protocol between $A$ and $B$ and have them compare $\langle p,m_B\rangle$ and $\langle p,m_A\rangle$ for equality. If the result is 1, output $m_A=m_B=m$ as the shared secret, if the result is $0$, output $\perp$, that is an error.


The idea is that attacks on DH result in both parties seeing different shared secrets which the SMP protocol should unveil while at the same time ensuring that if the parties actually arrive at the same DH secret, they also both know the same password and are thus authenticated by knowledge of the password.

Of course the above does not constitute a formal security analysis and thus this (inefficient) protocol should not be used without prior formal protocol analysis in production!