Robert Heaton

Software Engineer /
One-track lover / Down a two-way lane

Off-The-Record Messaging part 3: how OTR works

15 Feb 2022

This is part 3 of a 4 part series about Off-The-Record Messaging (OTR), a cryptographic messaging protocol that protects its users’ communications even if they get hacked. In parts 1 and 2 we looked at problems with common encrypted messaging protocols, such as PGP. We considered four desirable properties for messaging protocols to have: confidentiality, authenticity, deniability, and forward secrecy. In this post (part 3) we’ll see how OTR works and how it provides each of these properties, and then in part 4 we’ll delve into some of OTR’s key insights.

Index

How does Off-The-Record Messaging work?

At a high level, an OTR exchange looks similar to that of many other encryption protocols.

In order to exchange an OTR message, the sender and recipient must:

  1. Agree on a secret encryption session key
  2. Verify each other's identities

Then the sender must:

  1. Encrypt the message
  2. Sign the message
  3. Send the message

And the recipient must:

  1. Decrypt the message and verify its signature

Then the sender must:

  1. Publish the previously-secret signing session key (yes, this is surprising)

Finally, the sender and recipient must both:

  1. Forget the encryption session key in order to preserve forward secrecy

This sounds straightforward enough, but OTR’s fanatical desire for deniability and forward secrecy means that there’s a lot of nuance in those little bullet points. There are also a few extra steps that I’ve left out for now because they won’t make much sense until we get there.

Let’s start at the top.

1. Agree on a secret encryption session key

Alice and Bob start by agreeing on a shared, symmetric, ephemeral session key. They will later use this key to encrypt a message using a symmetric cipher. In order to preserve forward secrecy, once they have finished exchanging a message, they forget the session key that they used to send it and re-agree on a new one. The exact cadence at which they agree on new session keys is discussed in detail in the original OTR paper, but for our purposes we can assume that session keys are rotated roughly every message.

Alice and Bob securely agree on each shared secret key without allowing Eve to discover them by using a Diffie-Hellman key exchange, as briefly mentioned above. The guts of Diffie-Hellman are complicated and not necessary in order to explain OTR, but a broad understanding is still instructive.

Diffie-Hellman key exchange

Roughly speaking, to begin a Diffie-Hellman key exchange Alice and Bob each separately choose a random secret number. They each send the other a specially-chosen intermediate number that is derived from, but isn’t, their own random secret number. Now each knows their own random secret number, as well as the intermediate number that the other sent them. Thanks to the careful construction of the Diffie-Hellman protocol, each can use their own secret number and the other person’s intermediate number to derive the same final, secret key, which they can use as their shared session key.

Even if Eve snoops on their communication and sees both of the intermediate numbers that they exchanged, this does not allow her to compute the final, secret key, because she doesn’t know either of their initial random secrets.

Wikipedia has a good analogy that uses paint instead of numbers, but if you don’t get it then don’t worry, the details aren’t important to us. What matters is that Diffie-Hellman allows Alice and Bob to agree on a shared symmetric key in a way that gives them forward secrecy and prevents Eve from discovering the key.

2 Verify identities

We’ve described how Alice and Bob agree on a shared secret session key that they can use for symmetric encryption. However, we haven’t yet considered how they can verify the identity of the person they’ve agreed that session key with. At the moment Eve could intercept and block all of Alice and/or Bob’s traffic, and then spoof a separate Diffie-Hellman key-exchange with each person herself! Alice and Bob would each have agreed to a shared secret, but with Eve instead of each other. Eve would be able to read their messages and spoof replies to them, and Alice and Bob would have no way of knowing what had happened. This is called a man-in-the-middle attack.

Even though OTR doesn’t use asymmetric cryptography to encrypt its messages, it does use it for identity verification. In their original paper (Borisov, Goldberg and Brewer 2004), the researchers who devised OTR recommended an elegant way in which Alice and Bob could use public/private keypairs to verify each other’s identities when performing a Diffie-Hellman key exchange.

However, a few years later another paper (Alexander and Goldberg 2007) was published that described a weakness in this approach. The second paper proposed a broadly similar but more complex alternative. Here we’ll discuss the original, if slightly flawed procedure, since it’s simpler and is still a good illustration of the general principle of authenticating a key-exchange.

In the original OTR formulation, in order to prove their identities to each other, Alice and Bob each signed the intermediate Diffie-Hellman values that they sent to the other person. Then, when they received a signed intermediate value, they verified the signature against the other person’s public key. If the signature didn’t check out, they aborted the conversation. If it did, they could be sure that the secret value corresponding to this intermediate value was known only to the person who signed the intermediate value. They could proceed to combine the intermediate value with their own secret value in order to produce the shared symmetric secret key. The intention of this process was to allow Alice and Bob to each be sure that they were agreeing a shared secret with the right person.

Eve could still intercept and try to tamper with Alice and Bob’s traffic. However, she would’t be able to get them to accept an intermediate Diffie-Hellman value derived from her own random secret, because she wouldn’t be able to produce a valid signature. She therefore would’t be able to trick them into negotiating an encrypted connection with her.

However, Alexander and Goldberg 2007 showed that Eve could still manipulate this type of key exchange in other ways. Eve could have Alice and Bob negotiate a connection with each other, but trick Bob into believing that he was talking to Eve when he was really talking to Alice. Eve wouldn’t be able to actually read any messages, but this was nonetheless an unacceptable level of shennanigans to allow in an otherwise robust protocol.

OTR therefore now uses the more intricate approach outlined in Alexander and Goldberg 2007, in which Alice and Bob use vanilla Diffie-Hellman to set up an encrypted but unauthenticated connection, and then authenticate each other’s identities inside that channel.

Astute readers may be surprised that OTR ever used signatures to verify participants’ identities. Haven’t we been saying that public/private key cryptographic signatures are the enemy of deniability? Have we forgetten John Podesta already?

However, Alice and Bob never sign their actual messages using their private keys. All they sign are their intermediate key exchange values, and all that these signatures prove is that Alice and Bob exchanged two random-looking numbers. They don’t prove anything about the contents of Alice and Bob’s messages, meaning that the substance of their conversations remain fully deniable.

This said, Alice and Bob do still somehow need to sign their messages in order to authenticate their contents and ensure that they aren’t tampered with. We’ll soon see how they manage to do this while preserving deniability.

For now, Alice and Bob have agreed on a shared, symmetric, ephemeral session key and verified each other’s identities. Next, Alice needs to encrypt her message.

3. Encrypt the message

At this point, Alice and Bob have agreed on a secret, symmetric session key. We now need to specify a symmetric encryption algorithm (or cipher) that they can pass their key into in order to encrypt and decrypt their messages. Many such encryption algorithms exist already, and OTR can use a pre-existing algorithm without inventing its own.

For counter-intuitive reasons that we will discuss shortly, OTR requires a malleable cipher. A malleable cipher is one for which it is possible for an attacker to manipulate a ciphertext so that it decrypts to an alternative plaintext chosen by the attacker. This is usually a lousy property. For example, the attacker can tweak an encrypted message that decrypts to “Release the prisoner” into one that decrypts to “Execute the prisoner”. This manipulated message will be decryptable using the symmetric key agreed by the sender and receiver, which means that the receiver will be inclined to believe that it is legitimate.

In order to exploit the cipher used by OTR, the attacker needs to be able to guess the plaintext that an original ciphertext decrypts to. The alternative plaintext that they want to produce must be the same length as the original. If they can make such a successful guess, the attacker can produce their new, seemingly-valid ciphertext without needing to know the keys that were used to encrypt or decrypt the original ciphertext.

Even though malleability is usually not a desirable property, we’ll see later why it is oddly useful for OTR. OTR uses a malleable cipher called a “stream cipher with AES in counter mode”, but the details of how this particular cipher works aren’t important to us here.

Alice and Bob have now agreed on a key, verified each other’s identities, and have an encryption cipher that they can use. They haven’t used their private keys to sign anything important, which means that there’s nothing cryptographically tying them back to their message in the event of a compromise. They are therefore ready to use their key and cipher to encrypt, exchange, and decrypt a message.

However, we haven’t yet given Alice and Bob a way to detect whether their encrypted messages are tampered with in transit. The fact that a stream cipher is malleable, and therefore particularly easy to manipulate, makes this check especially important for OTR. Let’s see how OTR authenticates the contents of its messages without jeopardizing Alice and Bob’s ability to deny that they sent them.

4. Sign the message

In order to authenticate the contents of a message, the sender needs to be able to sign it and the receiver needs to be able to validate this signature. However, Alice and Bob don’t want to sign their messages directly using their private signing keys (which is what PGP does), because this would make them un-deniable.

OTR therefore has to prove the integrity of its messages using a different type of cryptographic signature. We know already that OTR uses a symmetric encryption algorithm to encrypt its messages while preserving forward secrecy. Similarly, it also uses a symmetric signing algorithm to authenticate its messages while preserving deniability. Whereas an asymmetric signing algorithm (such as the one used by PGP) uses one key in a keypair to create a signature and the other key to verify it, a symmetric one uses the same key to both create and verify. We’ll see why this is important shortly.

OTR uses a symmetric signing algorithm called HMAC, which stands for Hash-Based Message Authentication Code. In order to generate an HMAC signature for a message, the signer passes both their message and their symmetric, shared, secret signing key into the HMAC algorithm (we don’t need to know any internal details about HMAC, but we’ll talk about where this new secret key comes from in a few paragraphs’ time). The algorithm returns an HMAC signature, and the signer sends the message and HMAC signature to the recipient.

In order to verify an HMAC signature, the recipient performs the same process. They pass the message and the same signing key (which they also know) into the HMAC algorithm, and get back an HMAC signature. If the signature that they calculate matches the signature that they received from the sender then - assuming that the secret signing key has not been exposed - the recipient can be confident that the message has not been tampered with. This shows how HMAC signatures provide authentication, although it doesn’t show how they preserve deniability. We’ll come back to that in a few sections’ time.

Agreeing on a symmetric signing key

In order to use HMAC signatures to authenticate their messages, the sender and recipient need to agree on a shared secret signing key that they can pass into the HMAC algorithm. In OTR they use the hash of their shared secret encryption key as their shared secret signing key.

As mentioned several sections ago, a hash function is a function that produces a random-seeming but consistent output (often called simply a “hash”) for each input. Given an input it is very easy to calculate the hash output. By contrast, given a hash output it is essentially impossible to calculate the input that produced it. In OTR Alice and Bob use a cryptographic hash function (a hash function with some specific security properties) to generate their shared signing key from their shared encryption key.

Using the hash of their encryption key as their signing key is convenient, since it removes the need for Alice and Bob to perform another key-exchange dance. It also provides a subtle contribution towards deniability that we will discuss later.

After a lot of preparation, Alice and Bob are finally ready to securely exchange a message.

5. Send the message

Alice encrypts her message using a stream cipher with AES in counter mode, plus the symmetric encryption key that she and Bob agreed using their Diffie-Hellman key exchange. She calculates the hash of the encryption key to give her their symmetric signing key. She hashes her encrypted message, and signs the hash using the HMAC algorithm plus the signing key. Lastly, she sends the message and signature to Bob.

6. Decrypting and verifying the message

Once Bob receives Alice’s message he performs the same process in reverse. He decrypts the message using the shared encryption key. Like Alice, he calculates the hash of the encryption key to give him their symmetric signing key. Also like Alice, he hashes the encrypted message and re-calculates the signature using the HMAC algorithm and the shared signing key. He verifies that the signature he calculates matches the one that Alice sent him, hopefully proving that the message has not been tampered with. Alice and Bob have now exchanged a secret, authenticated, forward-ly-secret, and deniable message.

But there’s more.

7. An unexpected twist: publishing the signing key

Penultimately and oddly, Alice publishes her and Bob’s shared signing key to the world, for example by uploading it to a webpage that she controls. This is safe to do, because now that Bob has verified Alice’s message, it doesn’t matter if Eve has access to the signing key that he used to do this. This is the same principle by which it would be safe for Google to publish their private DKIM signing keys when they rotate them.

By contrast, it would be highly unsafe for Alice to publish their shared encryption key, because if Eve had stored their encrypted traffic then she would be able to use the encryption key to decrypt it. Happily, since the signing key that Alice publishes is only a cryptographic hash of the encryption key, it cannot be used to reconstruct the encryption key itself. All of this shows that publishing the signing key is a safe thing to do, but it doesn’t say anything about why it’s useful. We’ll talk about this shortly.

8. Forgetting the encryption key

Finally, once Bob has received, decrypted, and verified a message, and Alice has published the private signing key, the participants forget and delete their session encryption key. As we’ve discussed, this step is necessary in order to preserve forward secrecy and to make it impossible for an attacker to ever penetrate their encrypted traffic, even if they compromise their computers. Alice and Bob then start the process again, negotiating a new shared session encryption key for each message.

Let’s summarize these steps again:

  1. Sender and recipient agree on a secret encryption session key using Diffie-Hellman key exchange.
  2. They prove their identities to each other by signing the intermediate values in the Diffie-Hellman exchange
  3. Sender uses the encryption key from step 1 to encrypt their message and signature
  4. Sender signs their encrypted message using HMAC. They use a signing key equal to the cryptographic hash of the encryption key from step 1
  5. Sender sends the encrypted ciphertext and signature to the recipient
  6. Recipient decrypts the cipherext and verifies the accompanying signature
  7. Sender publishes the HMAC key
  8. Sender and recipient forget their session keys

That’s how you send an OTR message, but it doesn’t say much about why this fiddly foxtrot is useful. How exactly does it preserve deniability? Why does OTR use HMAC signatures? Why does it use a malleable cipher? And why on earth do participants publish their private signing keys once they’re done with them?

We’ll find out in part 4.

Index

Subscribe to my new work on programming, security, and a few other topics. Published a few times a month.

NEW: Also subscribe to my new series, Programming Feedback for Advanced Beginners.