I've come up with an algorithm to solve the socialist millionaire problem, but I'm not sure if the algorithm is secure. I wasn't able to find any flaw in it, but it seems too simple to be secure, so I'm posting it here. Here's how it would work together with Diffie Hellman to prevent man in the middle attacks:

  1. Alice and Bob have a pair of numbers, the generator g and the modulus P, these numbers are similar to those used in Diffie-Hellman
  2. They also have a secret number X - Alice has X1, Bob has X2, this number could be derived from a pre-shared password using a hash or PBKDF2
  3. Bob generates his private exponent Eb and sends Alice Yb=g^Eb mod P
  4. Bob calculates Zb=Yb^X2 mod P and sends it to Alice
  5. Alice calculates Z=Yb^X1 mod P and check if Z equals Zb, which means that X1 equals X2 and that she got keys from Bob (and not Eve)
  6. Alice generates her private exponent Ea, and calculates Ya=g^Ea mod P
  7. Alice calculates Za = Ya^X1 mod P
  8. Alice calculates a symmetric key S=Yb^Ea mod P and uses that key to encrypt a message for Bob
  9. Alice sends Ya, Za and the encrypted message to Bob
  10. Bob calculates Z = Ya^X2 mod P and checks if Z equals Za which means that the message came from Alice (not Eve). If this check fails, the message came from Eve, and Bob can ignore it
  11. Bob calculates S = Ya^Eb and uses that as a symmetric key to decrypt the message he got from Alice

If Eve tries to do a man-in-the-middle attack, she would try to give her Y key to Alice and Bob, but she wouldn't be able to create valid Z, because she doesn't know X, so her keys would get rejected.

I haven't been able to find a flaw in this algorithm, so I'm asking you to tell me if it's good? Assume that everything is done properly - P, E and X are big enough, Y!=1 and Z!=1 and g is a primitive root modulo P.

It looks too simple and I haven't found anyone else using something similar to this, so I want to ask if anyone can find a security flaw in this.

Can a malicious third party generate valid Y and Z without knowing X? Can this be used together with Diffie-Hellman to prevent man-in-the-middle attacks?

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – mikeazo Jun 1 '15 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.