Title: Social Millionaire's Protocol in OTR
Date: 2015-01-08 09:00

A friend of mine asked me how [OTR]( https://en.wikipedia.org/wiki/Off-the-Record_Messaging ) can guarantee that we're not
[MITM]( https://en.wikipedia.org/wiki/Man-in-the-middle_attack )'ed,
and I thought that maybe she was not the only one wondering about this crypto-powered black-magic,
so I wrote this small blogpost.

Since not everyone is well versed into mathematics or computer science,
every explanation will have two parts: an "[explain me like I'm five]( https://xkcd.com/1364/ )" one,
and a more mathematical one. As usual in cryptography, our protagonists will be Alice and Bob
who're trying to communicate together, while Eve will try to eavesdrop on them.

To perform mutual-authentication, OTR uses something called the Social Millionaire's Protocol (SMP).
It's based on [Yao's Millionaires' Problem]( https://en.wikipedia.org/wiki/Yao%27s_Millionaires%27_Problem ),
which was proposed by *Andrew C. Yao*, in 1982.

> Two millionaires wish to know who is richer; however,
they do not want to find out inadvertently any additional
information about each other’s wealth. How can they
carry out such a conversation?

# Diffie-hellman

The solution to this problem used by OTR is using the
[Diffie-Hellman key exchange]( https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange ) (DH) as a primitive.
As you may have guessed, this scheme was invented by Whitfield *Diffie* and Martin *Hellman*,
in 1976. It allows two parties that have no prior knowledge
of each other to establish a shared secret, over an insecure communication channel. This primitive
is not authenticated, meaning that it's vulnerable to MITM.

Wikipedia has an awesome picture to explain this process with paint:

![Wikipedia's picture of Diffie-Hellman]({static}/images/DH.jpg)

And now some mathematics:

Let *p* be a prime number (A prime number is greater than *1*, and can only be divided by itself or by *1*),
and *g* a primitive root modulo p. 

Primitive root modulo *p* means that every number coprime (Coprimes numbers have no common divisors except 1.)
to *p* is congruent to a power of *g* modulo *n*. This can be summarized as: *g primitive root modulo p ⇔ ∀n, n⊥p, ∃k, g<sup>k</sup> ≡ n (mod p)*

In OTR, both p and g are fixed: the first one to a 1536-bit prime, and the later is equal to 2. This is how it works:

1. Alice is choosing a random number *a*, and she sends over an insecure channel *A = g<sup>a</sup> mod p* to Bob.
2. Bob is choosing a random number *b*, and he sends over an insecure channel *B = g<sup>b</sup> mod p* to Alice.
3. Alice computes *s = B<sup>a</sup> mod p*.
4. Bob computes *s = A<sup>b</sup> mod p*.

Now Alice and Bob are sharing the same secret *s*.

When numbers are big enough, given *g*, *p*, *g<sup>b</sup> mod p* and *g<sup>a</sup> mod p*,
it's **really super hard** to find *a* or *b*, even for super-computers.
This is knows as the [discrete logarithm problem]( https://en.wikipedia.org/wiki/Discrete_logarithm ).

Ok, now we have a way to create a shared secret, but we're still vulnerable to MITM.

# Socialist millionaire protocol
You may wonder how we could use the SMP to establish authentication without being vulnerable to MITM.
Think of the wealth amount as a shared secret : You can check if both of you are knowing it,
without disclosing it. If someone is trying to MITM you, she'll have to guess this amount.

Someone else already came up with a [great]( http://twistedoakstudios.com/blog/Post3724_explain-it-like-im-five-the-socialist-millionaire-problem-and-secure-multi-party-computation) explanation of the SMP, and I didn't managed
to find something better.

So let's jump to the mathematical side, straight from OTR 3.4 [specification]( https://otr.cypherpunks.ca/Protocol-v3-4.0.0.html):

* Alice
	- Picks random exponents *a<sub>2</sub> and a<sub>3</sub>*
	- Sends Bob *g<sub>2a</sub> = g<sub>1</sub><sup>a<sub>2</sub></sup> and g<sub>3a</sub> = g<sub>1</sub><sup>a<sub>3</sub></sup>*
* Bob
	- Picks random exponents *b<sub>2</sub> and b<sub>3</sub>*
	- Computes *g<sub>2b</sub> = g<sub>1</sub><sup>b<sub>2</sub></sup> and g<sub>3b</sub> = g<sub>1</sub><sup>b<sub>3</sub></sup>*
	- Computes *g<sub>2</sub> = g<sub>2a</sub><sup>b<sub>2</sub></sup> and g<sub>3</sub> = g<sub>3a</sub><sup>b<sub>3</sub></sup>*
	- Picks random exponent *r*
	- Computes *P<sub>b</sub> = g<sub>3</sub><sup>r</sup> and Q<sub>b</sub> = g<sub>1</sub><sup>r</sup> g<sub>2</sub><sup>y</sup>*
	- Sends Alice *g<sub>2b</sub>, g<sub>3b</sub>, P<sub>b</sub> and Q<sub>b</sub>*
* Alice
	- Computes *g<sub>2</sub> = g<sub>2b</sub><sup>a<sub>2</sub></sup> and g<sub>3</sub> = g<sub>3b</sub><sup>a<sub>3</sub></sup>*
	- Picks random exponent *s*
	- Computes *P<sub>a</sub> = g<sub>3</sub><sup>s</sup> and Q<sub>a</sub> = g<sub>1</sub><sup>s</sup> g<sub>2</sub><sup>x</sup>*
	- Computes *R<sub>a</sub> = (Q<sub>a</sub> / Q<sub>b</sub>) <sup>a<sub>3</sub></sup>*
	- Sends Bob *P<sub>a</sub>, Q<sub>a</sub> and R<sub>a</sub>*
* Bob
	- Computes *R<sub>b</sub> = (Q<sub>a</sub> / Q<sub>b</sub>) <sup>b<sub>3</sub></sup>*
	- Computes *R<sub>ab</sub> = R<sub>a</sub><sup>b<sub>3</sub></sup>*
	- Checks whether *R<sub>ab</sub> == (P<sub>a</sub> / P<sub>b</sub>)*
	- Sends Alice *R<sub>b</sub>*
* Alice
	- Computes *R<sub>ab</sub> = R<sub>b</sub><sup>a<sub>3</sub></sup>*
	- Checks whether *R<sub>ab</sub> == (P<sub>a</sub> / P<sub>b</sub>)*

## Proof

*R<sub>ab</sub>
= R<sub>a</sub><sup>b<sub>3</sub></sup>
= (Q<sub>a</sub> / Q<sub>b</sub>) <sup>a<sub>3</sub>·b<sub>3</sub></sup>
= (g<sub>1</sub><sup>s - r</sup> · g<sub>2</sub><sup>x - y</sup>) <sup>a<sub>3</sub></sup>·<sup>b<sub>3</sub></sup>
= g<sub>1</sub><sup>a<sub>3</sub>·b<sub>3</sub>·(s - r)</sup> · g<sub>2</sub><sup>(x - y)·a<sub>3</sub>·b<sub>3</sub></sup>*

*P<sub>a</sub> / P<sub>b</sub>
= g<sub>3</sub><sup>s</sup> / g<sub>3</sub><sup>r</sup> 
= g<sub>3</sub><sup>s - r</sup>
= g<sub>3a</sub><sup>b<sub>3</sub>·(s - r)</sup>
= g<sub>1</sub><sup>a<sub>3</sub>·b<sub>3</sub>·(s - r)</sup>*

This means that

*g<sub>2</sub><sup>a<sub>3</sub></sup>·<sup>b<sub>3</sub>·(x - y)</sup> = 1*

Since *g<sub>2</sub><sup>a<sub>3</sub></sup>·<sup>b<sub>3</sub></sup>* is a random number different from 1,
the only solution is that *x - y = 0*, meaning that *x = y*.

Thanks to the discrete logarithm problem, 
an attacker eavesdropping on the connection wouldn't be able to guess the secret.
If she was trying to MITM with the wrong secret, the final check will fail.

## The common secret

When Alice and Bob are initiating an OTR communication,
they are first creating a shared secret with Diffie-Hellman,
then are doing a mutual authentication. This process is named
Authenticated Key Exchange (AKE), and produces the shared secret *s*.

Don't be fooled by the term *mutual authentication*, here, we're speaking of *keys*,
not persons: the communication is secure between those two keys, but at this point,
Alice and Bob can't be sure (Unless they know each other fingerprints.) that they
are not MITM'ed.

For OTR, the secret *x* (or *y* if you're Bob) is composed of:
*[SHA256]( https://en.wikipedia.org/wiki/SHA-2 )(0x01|initiator_fingerprint|responder_fingerprint|session_id|secret)*,
with *sessions_id* equals to *SHA256(0x00|s)*.

Why is the secret *x* (or *y*) so complicated? Because this ensures that you're doing the authentication
with the *right* fingerprints, in the *right* session.

If you have used a decent OTR client, you'll noticed that you can either use a *shared secret*,
or ask a question. When you're choosing the later, the answer to the question is used
as the shared secret, while the question is transmitted along with the first message.
You can also of course manually verify the fingerprint, but this is less convenient.

# Conclusion
If hope that now you understand how the magic authentication of OTR is working,
and that you're eager to know more about this wonderful protocol by reading its
[specification]( https://otr.cypherpunks.ca/Protocol-v3-4.0.0.html ),
or at least, to [use it]( https://freedom.press/encryption-works#otr) for your IM communications.

By the way, if you know some C, feel free to help us improving [libotr]( https://bugs.otr.im/projects/libotr ),
the reference implementation of OTR ;)