[OTR-users] OTR - AKE v2

[Ian Goldberg]

On Sun, Mar 19, 2006 at 04:56:36AM -0800, testbnam jhgujgef wrote:
> Hello,
> 
> I was about to review OTR, and my first question would be:
> 
> 1. Picks a random value r (128 bits)
> 2. Sends Alice AESr(gx), HASH(gx)
> 
> Bob encrypts the DH public key fom Alice with AES (key = r) and send it
> to Alice.
> 
> 7. Sends Alice r, AESc(XB), MACm2(AESc(XB)) 
> 
> Now Bob sends r (the AES key used to encrypt Bob's public key) in
> plain-text to Alice. To make it short: the procedure of encrypting the
> DH public key appears pointless to me. The attacker gains access to the
> AES key "r" later anyway.
> 
> I would like to know the background behind this. Is there actually a
> good reason for encrypting the DH public key? Did I overlook something
> maybe?
> 
> A good friend is always saying: Either you add security to your
> algorithm, or you leave it as it is. You can't make it "a little more
> secure" with "tricks".

That's correct.  This actually adds security to the algorithm: without
it, a man-in-the-middle could try to carefully pick his DH exponents so
that Alice and Bob's secure session ids would match.  This way, the
parties have to commit to their choices before seeing the other parties'
choices.  [Note that it's not the encryption per se, but rather the
hash, that forms the commitment.  The encryption is just to enable us to
rearrange some messages.]

Nikita wrote a good FAQ entry about this, which I realize I've neglected
to post, so I've included it below.

   - Ian

Nikita writes:

Q. Looking at the new key exchange protocol, it looks an awful lot like
SIGMA.  However, there's this extra key that is used to encrypt g^x in
the first message and is sent in the third one.  Can you explain what
that's about?

A. Glad you asked!  There are actually two things happening here, one
to support secure session identifiers and another to make the key
exchange messages smaller.  OTR clients have the ability to show a
"secure session ID," which is the hash of the two Diffie-Hellman
exponents.  The idea is that if two people can verify out-of-band (e.g.
over the phone) that they are using the same secure session ID, they
know that there is no man-in-the-middle attack, even if they can't
verify each other's public keys, or worse, one of the private keys has
been compromised.

However, if the secure session ID is too short, a man in the middle can
try to find a hash collision and still get away with his attack.  Here
is a protocol execution with Mallory:

  Alice -> Mallory[Bob]:          g^x
           Mallory[Alice] <- Bob: g^y

  (In this case, Alice and Bob both initiate a connection with each
  other, and their messages are intercepted by Mallory)

  Mallory: find z, z' such that H(g^x g^z) = H(g^z' g^y).  If H() has
  k bits, it requires about 2^{k/2} exponentiations to find such
  numbers.

  Alice <- Mallory[Bob]:          g^z
           Mallory[Alice] -> Bob: g^z'

  Now the secure session ID for Alice's session with Mallory and for Bob's
  session with Mallory are the same.

This is why, in clients using v1 of the protocol, secure session IDs
were 128 bits long: 2^64 exponentiations are almost certainly too much
work for an active attack.  However, we can modify the protocol to get
away with smaller session IDs:

  Alice -> Bob:                   H(g^x)
  Bob -> Alice:                   g^y
  Alice -> Bob:                   g^x

In the first step, Alice commits to her value of g^x but doesn't reveal
it.  So neither party knows the other's DH value until they reveal it to
the other party.  Now, Mallory could still run the following attack:

  Alice -> Mallory[Bob]:          H(g^x)
  Alice <- Mallory[Bob]:          g^z
  Alice -> Mallory[Bob]:          g^x

           Mallory[Alice] <- Bob: H(g^y)
           Mallory[Alice] -> Bob: g^z'
           Mallory[Alice] <- Bob: g^y

However, in this case, Mallory has to commit to g^z before he sees
Alice's g^x, and similarly, to g^z' before he sees g^y.  So he has to
hope that H(g^x g^z) = H(g^z' g^y).  Of course, he could start 2^k
sessions to find such a collision; however, even for k=32, it is
unlikely that Mallory will be able to start 2^32 sessions before getting
detected.  Therefore, we can use much shorter session IDs, imposing a
smaller burden on the users.

Getting back to the OTR key exchange protocol, our modification to Sigma
are like follows:

  1: A -> B: H(g^x)
  2: B -> A: g^y
  3: A -> B: g^x, "A", Sign_A(g^y,g^x)...
  4: B -> A: "B", Sign_B(g^x,g^y)...

Instead of sending g^x in the first message, we send a commitment to it,
and reveal it in the third message.  Well, almost -- there is another
twist.  Message 3 of the protocol is the largest one, and some IM
protocols (*cough* IRC *cough*) have very strict limits on the sizes of
messages.  So we make the following change:

  1: A -> B: H(g^x), E(r, g^x), where r is a random symmetric key
  2: B -> A: g^y
  3: A -> B: r, "A", Sign...
  4: ...

Alice sends the value of g^x in the first message, but encrypts it with a
random key.  She then reveals the key in message 3, which is equivalent
to revealing the value of g^x.  The 128-bit r is much smaller than the
1500+ bit Diffie-Hellman exponent g^x, and this way message 3 *just*
squeaks by under the message size limits.  Welcome to real-world
security protocol engineering!