3

this is a clueluess question, but what does the Socialist Millionaire Protocol, which is typically used in conjunction with OTR-Messaging, that "conventional" Challenge-Response Mechanisms like CHAP can't do?

http://en.wikipedia.org/wiki/Socialist_millionaire

http://en.wikipedia.org/wiki/Challenge-handshake_authentication_protocol

PS: Can someone consider adding the tag "OTR"?

skaffman
  • 398,947
  • 96
  • 818
  • 769
Fabian Zeindl
  • 5,860
  • 8
  • 54
  • 78

2 Answers2

7

A standard challenge response system works like this:

  • Bob, the server, sends Alice a random challenge number.

  • Alice performs a cryptographic operation on the challenge using her secret.

  • Alice sends the result to Bob.

  • Bob performs the same operation on the challenge with his secret.

  • If the result of this calculation matches the response Alice sent him, then Alice must have used the same secret.

The problem with this scheme is that an eavesdropper who gets the challenge and the response can use their supercomputer to bruteforce the secret. They can perform the cryptographic operation repeatedly with many secrets and if they find a secret that produces the observed response they know that that is the shared secret between Alice and Bob.

If the secret is a 128 bit key or a very strong passphrase then bruteforcing the secret will take a very long time and will be impractical but for small secrets like numeric pins or normal passwords bruteforcing is a very real threat.

The socialist millionaire's protocol serves the same purpose but it doesen't reveal any information about the secret. An eavesdropper can't use the messages sent back and forth to learn anything about the secret even if they had an infinitely powerful computer. Even if the attacker pretends to be Bob and can send any messages he wants back to Alice, they still can't get any information about the secret other than whether the guess they made was correct.

Paŭlo Ebermann
  • 73,284
  • 20
  • 146
  • 210
Richard
  • 71
  • 1
  • 3
2

In the CHAP protocol the client just proves his identity through showing that he has knowledge of the key. This could also be done with asymmetric cipher. The client just has to encrypt randomly generated challenge and the serve has be able to verify the content.

The Socialist millionaire protocol tells both entities that they have either used to same value or a different value. This could also be used as a login protocol. It will then offer mutual authentication.

mrks
  • 1,421
  • 2
  • 12
  • 20
  • I still don't get it completely. The CHAP protocol also "tells" both entities that they have the same value, no? Or do you mean with SM you can somehow generate a key on both sides and ensure that it's the same then instead of having to have the key ready on both sides somehow? – Fabian Zeindl May 14 '11 at 12:52
  • 3
    1) No, chap only tells the server that the user has the correct key, but a malicious server could send a random challenge but then accept what ever the user returns. 2) SM just proves that two entities share a secret. In case the secrets are not the same, the entities will find out without gaining any knowledge about the secret of the other entity. – mrks May 16 '11 at 07:32