How does the Socialist Millionaire Protocol differ from a simple Challenge-Response like CHAP?

Question

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"?

Answer 1

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.

Answer 2

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.