Socialist millionaire

The Socialist Millionaire Problem is one in which two millionaires want to determine if their wealth is equal, without disclosing any information about their riches to each other. It is a variant of the Millionaire's Problem whereby two millionaires wish to compare their riches to determine who has the most wealth, without disclosing any information about their riches to each other.

It is often used as a cryptographic protocol that allows two parties to verify the identity of the remote party through the use of a shared secret, avoiding a man-in-the-middle attack without the inconvenience of manually comparing public key fingerprints through an outside channel. In effect a relatively weak password/passphrase in natural language can be used.

Motivation

Alice and Bob have secret values x, and y respectively. Alice and Bob wish to learn if x = y without allowing either party to learn anything else about the other's secret value. A passive attacker, simply spying on the messages Alice and Bob exchange learns nothing about x and y, nor even if x = y. Even if one of the parties is dishonest, and deviates from the protocol, he or she cannot learn anything more than if x = y. An active attacker, capable of arbitrarily interfering with Alice and Bob's communication (a man-in-the-middle) cannot learn more than a passive attacker, and cannot affect the outcome of the protocol other than to make it fail. Therefore, the protocol can be used to authenticate whether two parties have the same secret information. Popular instant message cryptography package Off-the-Record Messaging uses the Socialist Millionaire protocol for authentication, in which the secrets x and y contain information about both parties' long-term authentication public keys, as well as information entered by the users themselves.

Procedure

All operations are performed modulo a prime p, or in other words, in the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$. Let g₁ be a generator of the group (any element other than 1, noting that 0 is not an element of multiplicative groups). The values p and g₁ are agreed on before the protocol, and in practice are generally fixed in a given implementation. For example, in Off-the-Record Messaging p is a specific fixed 1536-bit prime. All sent values include zero-knowledge proofs that they were generated according to this protocol, as indicated in the detailed description below.

Assuming that Alice begins the exchange:

• Alice:
  1. Picks random exponents a₂ and a₃
  2. Sends Bob $g_{2a} = {g_1}^{a_2}$ and $g_{3a} = {g_1}^{a_3}$
• Bob:
  1. Picks random exponents b₂ and b₃
  2. Computes $g_{2b} = {g_{1}}^{b_{2}}$ and $g_{3b} = {g_{1}}^{b_{3}}$
  3. Computes $g_{2} = {g_{2a}}^{b_{2}}$ and $g_{3} = {g_{3a}}^{b_{3}}$
  4. Picks a random exponent r
  5. Computes $P_{b} = {g_{3}}^{r}$ and $Q_{b} = {g_{1}}^{r} \, {g_{2}}^{y}$
  6. Sends Alice g_2b, g_3b, P_b and Q_b
• Alice:
  1. Computes $g_{2} = {g_{2b}}^{a_{2}}$ and $g_{3} = {g_{3b}}^{a_{3}}$

     (g₂ and g₃ have effectively been negotiated via the Diffie-Hellman key exchange.)

  2. Picks a random exponent s
  3. Computes $P_{a} = {g_{3}}^{s}$ and $Q_{a} = {g_{1}}^{s} \, {g_{2}}^{x}$
  4. Computes $R_{a} = {Q_{a}}^{a_{3}} \, {Q_{b}}^{-a_{3}}$
  5. Sends Bob P_a, Q_a and R_a
• Bob:
  1. Computes $R_{b} = {Q_{a}}^{b_{3}} \, {Q_{b}}^{-b_{3}}$
  2. Computes $R_{ab} = {R_{a}}^{b_{3}}$
  3. Checks whether $R_{ab} = P_{a} \, {P_{b}}^{-1}$
  4. Sends Alice R_b
• Alice:
  1. Computes $R_{ab} = {R_{b}}^{a_{3}}$
  2. Checks whether $R_{ab} = P_{a} \, {P_{b}}^{-1}$

The correctness of this algorithm (but not its security) can be shown by simply representing all values in terms of the inputs x, y, and g₁, and the randomly generated values a₂, a₃, b₂, b₃, r, and s:

$\begin{alignat}{3} R_a &= {Q_{a}}^{a_{3}} \, {Q_{b}}^{-a_{3}} \\ & = ({g_{1}}^{s} \, {g_{2}}^{x})^{a_{3}} \, ({g_{1}}^{r} \, {g_{2}}^{y})^{-a_{3}} \\ & = {g_{1}}^{(s - r) \, a_{3}} \, {g_{2}}^{(x - y) \, a_{3}} \end{alignat}$

Assuming x = y, then ${g_{2}}^{(x - y) \, a_{3}} = 1$, and therefore $R_a = {g_{1}}^{(s - r) \, a_{3}}$. The same logic holds to show $R_b = {g_{1}}^{(s - r) \, b_{3}}$. Therefore,

$\begin{alignat}{3} R_{ab} &= {R_a}^{b_3} \\ &= ({g_{1}}^{(s - r) \, a_{3}} \, {g_{2}}^{(x - y) \, a_{3}})^{b_3} \\ &= {g_{1}}^{(s - r) \, a_{3} \, b_{3}} \, {g_{2}}^{(x - y) \, a_{3} \, b_{3}} \end{alignat}$

Similarly expanding ${R_b}^{a_3}$ reveals that the values of R_ab that Alice and Bob generate are identical. Finally, examining the equation being tested by Alice and Bob shows that the algorithm works:

$\begin{alignat}{5} R_{ab} &= P_{a} \, {P_{b}}^{-1} \\ {g_{1}}^{(s - r) \, a_{3} \, b_{3}} \, {g_{2}}^{(x - y) \, a_{3} \, b_{3}} &= {g_{3}}^{s - r} \\ &= ({g_{1}}^{a_{3} \, b_{3}})^{s - r} \\ &= g_{1}^{(s - r) \, a_{3} \, b_{3}} \\ {g_{2}}^{(x - y) \, a_{3} \, b_{3}} &= 1 \end{alignat}$

As the last equation given above holds only if x = y, and as it is equivalent to the first equation, the tests Alice and Bob perform of $R_{ab} = P_{a} \, {P_{b}}^{-1}$ are therefore equivalent to testing x = y, completing a proof of correctness.

However, as written above the protocol is vulnerable to poisoning whereby either Alice or Bob chooses (a₂, a₃) or (b₂, b₃) to be zero to be able to predict the result [1]. To solve this problem, check that the pairs (g_2a, g_3a) and (g_2b, g_3b) are not equal to one.

See also

• Zero-knowledge proof
• Off-the-Record Messaging

External links

• Description of the OTR-Messaging Protocol version 2