Socialist millionaire

From Wikipedia, the free encyclopedia

This cryptography-related article is a stub. You can help Wikipedia by expanding it.

The Socialist Millionaire Protocol is a cryptographic protocol that allows two parties to verify the identity of the remote party and avoid 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. Brute force attacks are avoided by demanding user input on both sides prior to the check itself. It is a part of Off-the-Record Messaging.

[edit] Example

While data messages are being exchanged, either Alice or Bob may run Socialist Milllionaire Protocol (SMP) to detect impersonation or man-in-the-middle attacks. All exponentiations are done modulo a particular 1536-bit prime, and g₁ is a generator of that group. All sent values include zero-knowledge proofs that they were generated according to this protocol, as indicated in the detailed description below.

Suppose Alice and Bob have secret information x and y respectively, and they wish to know whether x = y. The Socialist Millionaires' Protocol allows them to compare x and y without revealing any other information than the value of (x == y). For OTR, the secrets contain information about both parties' long-term authentication public keys, as well as information entered by the users themselves. If x = y, this means that Alice and Bob entered the same secret information, and so must be the same entities who established that secret to begin with.

Assuming that Alice begins the exchange:

* Alice: 
         1. Picks random exponents a₂ and a₃
         2. Sends Bob g_{2_a} = g₁^a₂ and g_{3_a} = g₁^a₃
* Bob:
         1. Picks random exponents b₂ and b₃
         2. Computes g_2b = g₁^b₂ and g_3b = g₁^b₃
         3. Computes g₂ = g_2a^b₂ and g₃ = g_3a^b₃
         4. Picks random exponent r
         5. Computes P_b = g_3r and Q_b = g₁^r g₂^y
         6. Sends Alice g_2b, g_3b, P_b and Q_b
* Alice:
         1. Computes g₂ = g_2b^a₂ and g³ = g_3b^a₃
         2. Picks random exponent s
         3. Computes P_a = g₃^s and Q_a = g₁^s g₂^x
         4. Computes R_a = (Q_a / Q_b)^a₃
         5. Sends Bob P_a, Q_a and R_a
* Bob:
         1. Computes R_b = (Q_a / Q_b)^b₃
         2. Computes R_ab = R_a^b₃
         3. Checks whether R_ab == (P_a / P_b)
         4. Sends Alice R_b
* Alice:
         1. Computes R_ab = R_b^a₃
         2. Checks whether R_ab == (P_a / P_b)

If everything is done correctly, then R_ab should hold the value of (P_a / P_b) times (g₂^a₃b₃)^{(x - y)}, which means that the test at the end of the protocol will only succeed if x == y. Further, since g₂^a₃b₃ is a random number not known to any party, if x is not equal to y, no other information is revealed.