Artificial truth

The more you see, the less you believe.

[archives] [latest] | [homepage] | [atom/rss]

Social Millionaire's Protocol in OTR
Thu 08 January 2015 — download

A friend of mine asked me how OTR can guarantee that we're not MITM'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" 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, 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 (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

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, gk ≡ 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 = ga mod p to Bob.
  2. Bob is choosing a random number b, and he sends over an insecure channel B = gb mod p to Alice.
  3. Alice computes s = Ba mod p.
  4. Bob computes s = Ab mod p.

Now Alice and Bob are sharing the same secret s.

When numbers are big enough, given g, p, gb mod p and ga mod p, it's really super hard to find a or b, even for super-computers. This is knows as the discrete logarithm problem.

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 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:

  • Alice
    • Picks random exponents a2 and a3
    • Sends Bob g2a = g1a2 and g3a = g1a3
  • Bob
    • Picks random exponents b2 and b3
    • Computes g2b = g1b2 and g3b = g1b3
    • Computes g2 = g2ab2 and g3 = g3ab3
    • Picks random exponent r
    • Computes Pb = g3r and Qb = g1r g2y
    • Sends Alice g2b, g3b, Pb and Qb
  • Alice
    • Computes g2 = g2ba2 and g3 = g3ba3
    • Picks random exponent s
    • Computes Pa = g3s and Qa = g1s g2x
    • Computes Ra = (Qa / Qb) a3
    • Sends Bob Pa, Qa and Ra
  • Bob
    • Computes Rb = (Qa / Qb) b3
    • Computes Rab = Rab3
    • Checks whether Rab == (Pa / Pb)
    • Sends Alice Rb
  • Alice
    • Computes Rab = Rba3
    • Checks whether Rab == (Pa / Pb)

Proof

Rab = Rab3 = (Qa / Qb) a3·b3 = (g1s - r · g2x - y) a3·b3 = g1a3·b3·(s - r) · g2(x - y)·a3·b3

Pa / Pb = g3s / g3r = g3s - r = g3ab3·(s - r) = g1a3·b3·(s - r)

This means that

g2a3·b3·(x - y) = 1

Since g2a3·b3 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(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, or at least, to use it for your IM communications.

By the way, if you know some C, feel free to help us improving libotr, the reference implementation of OTR ;)