###### Books / Crypto 101 / Chapter 13

# Off-The-Record Messaging (OTR)

## OTR messaging

**OTR messaging** is a protocol for
securing instant messaging communication between people. It intends to be the
online equivalent of a private, real-life conversation. It encrypts
messages, preventing eavesdroppers from reading them. It also
authenticates peers to each other, so they know who they’re talking to.
Despite authenticating peers, it is designed to be deniable:
participants can later deny to third parties anything they said to each
other. It is also designed to have perfect forward secrecy: even a
compromise of a long-term public key pair doesn’t compromise any
previous conversations.

The deniability and perfect forward secrecy properties are very
different from those of other systems such as OpenPGP. OpenPGP
intentionally guarantees non-repudiability. It’s a great property if
you’re signing software packages, talking on mailing lists or signing
business invoices, but the authors of *OTR* argue that those aren’t desirable properties for the
online equivalent of one-on-one conversations. Furthermore, OpenPGP’s
static model of communication makes the constant key renegotiation to
facilitate *OTR*’s perfect forward
secrecy impossible.

*OTR* is typically configured
opportunistically, which means that it will attempt to secure any
communication between two peers, if both understand the protocol,
without interfering with communication where the other peer does not.
The protocol is supported in many different instant messaging clients
either directly, or with a plugin. Because it works over instant
messages, it can be used across many different instant messaging
protocols.

A peer can signal that they would like to speak *OTR* with an explicit message, called the
*OTR* Query message. If the peer is just
willing to speak *OTR* but doesn’t
require it, they can optionally invisibly add that information to a
plaintext message. That happens with a clever system of whitespace tags:
a bunch of whitespace such as spaces and tab characters are used to
encode that information. An *OTR*-capable
client can interpret that tag and start an *OTR* conversation; an client that isn’t *OTR*-capable just displays some extra whitespace.

*OTR* uses many of the primitives we’ve
seen so far:

- Symmetric key encryption (AES in CTR mode)
- Message authentication codes (HMAC with SHA-1)
- Diffie-Hellman key exchange

*OTR* also utilizes another mechanism,
called the SMP, to check if peers arrived at the same shared secret.

## Key exchange

In *OTR*, AKE relies heavily on
Diffie-Hellman key exchange, extended with a significant number of
extra, interlocking checks. The Diffie-Hellman exchange itself uses a
fixed 1536-bit prime with a fixed generator \(g\).

We suppose that two participants, named Alice and Bob want to communicate and are willing to exchange sensitive data with each other. Alice and Bob have a long-term DSA authentication key pair each, which we’ll call (\(p_A, s_A)\) and \((p_B, s_B)\) respectively.

The protocol also relies on a number of other primitives:

- A 128-bit block cipher. In
*OTR*, this is always AES. In this section, we’ll call block cipher encryption and decryption \(E\) and \(D\), respectively. - A hash function, \(H\). In
*OTR*, this is SHA1. - A Message authentication code, \(M\).
In
*OTR*, this is HMAC-SHA1. - A signing function, \(S\).

### Commit message

Initially Alice and Bob are in a protocol state where they wait for the
peer to initiate an *OTR* connection, and
advertise their own capability of speaking *OTR*.

Let’s suppose that Bob chooses to initiate an *OTR* conversation with Alice. His client sends an
*OTR* Commit Message, and then
transitions to a state where he waits for a reply from from Alice’s
client.

To send a commit message, a client picks a random 128-bit value \(r\) and a random 320-bit (or larger) Diffie-Hellman secret \(x\). It then sends \(E(r, g^x)\) and \(H(g^x)\) to the peer.

### Key message

Alice’s client has received Bob’s client’s advertisement to start an
*OTR* session. Her client replies with a
key message, which involves creating a new Diffie-Hellman key pair. She
picks a 320-bit (or larger) Diffie-Hellman secret \(y\) and sends \(g^y\) to
Bob.

### Reveal Signature Message

Now that Alice has sent her public Diffie-Hellman key, Bob can complete his part of the Diffie-Hellman protocol. Alice can’t continue yet, because she hasn’t seen Bob’s public key.

When we discussed Diffie-Hellman, we noted that it does not
*authenticate* the peer. Bob can compute a secret, but doesn’t know
he’s talking to Alice. As with TLS and other systems using
Diffie-Hellman, this problem is solved by authenticating the key
exchange.

After verifying that Alice’s public key is a valid value, Bob computes the shared secret \(s = (g^y)^x\). Using a key derivation function, he derives several keys from \(s\): two AES keys \(c, c^\prime\), and four MAC keys \(m_1, m_1^\prime, m_2, m_2^\prime\).

He chooses an identification number \(i_B\) for his current Diffie-Hellman
key pair \((x, g^x)\). This will be important once Alice and Bob generate
new key pairs, which they will do later on in the
*OTR* protocol.

Bob computes:

\[M_B = M_{m_1}(g^x, g^y, p_B, i_B)\] \[X_B = (p_B, i_B, S(p_B, M_B))\]He sends Alice \(r, E_c(X_B), M_{m_2}(E_c(X_B))\).

### Signature Message

Alice can now confirm she’s talking to Bob directly, because Bob signed the authenticator for the exchange \(M_B\) with his long-term DSA key.

Alice can now also compute the shared secret: Bob has sent her \(r\), which was previously used to encrypt Bob’s Diffie-Hellman public key. She then computes \(H(g^x)\) herself, to compare it against what Bob sent. By completing her side of the Diffie-Hellman exchange (\(s = (g^x)^y\)), she derives the same keys: \(c, c^\prime, m_1, m_1^\prime, m_2, m_2^\prime\). Using \(m_2\), she can verify \(M_{m_2}(E_c(X_B))\). Once that message is verified, she can safely decrypt it using her computed \(c\).

She can then also compute \(M_B = M_{m_1}(g^x, g^y, p_B, i_B)\), and verifies that it is the same as Bob sent. By verifying the signed portion \(S(p_B, M_B)\) against Bob’s public key, she has now unambiguously tied the current interaction to Bob’s long-term authentication key.

She then computes the same values Bob computed to tie his long-term key to the short-term handshake, so that Bob can also authenticate her. She chooses an identification number \(i_A\) for her current DH keypair \((y, g^y)\), computes \(M_A = M_{m_1^\prime}(g^y, g^x, p_A, i_A)\) and \(X_A = p_A, i_A, S(p_A, M_A)\). Finally, she sends Bob \(E_{c^\prime}(X_A), M_{m_2^\prime}(E_c(X_B))\).

### Authenticating Alice

Now Bob can also authenticate Alice, again by mirroring steps. First, he verifies \(M_{m_2^\prime}(E_c(X_B))\). This allows him to check that Alice saw the same \(X_B\) he sent.

Once he decrypts \(E_{c^\prime}(X_A)\), he has access to \(X_A\), which is Alice’s long-term public key information. He can then compute \(M_A = M_{m_1^\prime}(g^y, g^x, p_A, i_A)\) to compare it with the version Alice sent. Finally, he verifies \(S(p_A, M_A)\) with Alice’s public key.

### What have we accomplished?

If all checks succeed then Alice and Bob have completed an authenticated Diffie-Hellman exchange and have a shared secret that only the two of them know.

Now that you’ve seen both sides of the authenticated handshake, you can see why so many different keys are derived from the Diffie-Hellman secret. Keys marked with a prime (\(\prime\)) are for messages originating from the second peer (the one responding to the advertisement, in our case, Alice); keys without a prime are for the initiating peer (in our case, Bob).

## Data exchange

See https://otr.cypherpunks.ca/Protocol-v3-4.0.0.html