A look at the OMEMO protocol

For humans, by humans

Every article on LWN.net is written for humans, by humans. If you've enjoyed this article and want to see more like it, your subscription goes a long way to keeping the slop at bay. We are offering a free one-month trial subscription (no credit card required) to get you started.

For several years, the Off-the-Record (OTR) protocol has been the go-to option for application developers and users needing to secure instant-messaging (IM) conversations. OTR provides a number of features useful for IM, such as mutual authentication and forward secrecy, without requiring a public infrastructure like PGP's web of trust. But OTR has its limitations as well, such as the lack of a way to synchronize a user's messages between multiple clients and an inability to send messages to a user who is offline. In recent months, however, a new alternative has gained popularity. OMEMO, the "OMEMO Multi-End Message and Object Encryption" protocol, fills several of the gaps left open in OTR, while promising ease-of-use to end users. OMEMO also dispenses with one of the oft-criticized requirements of Signal, doing away with the need for a centralized server.

OMEMO is implemented as an extension to the XMPP IM protocol. At present, the specification has not been officially accepted by the XMPP Standards Foundation, so OMEMO does not have an XMPP Extension Protocol (XEP) designation. The first draft was published in October of 2015, based on work by Andreas Straub.

The initial implementation was written by Straub as a Google Summer of Code project for the Conversations IM client for Android. Subsequently, The Guardian Project announced that it would rebase its ChatSecure app on Conversations—although, as we will see, that work became mired in license-compatibility issues that have only recently moved toward a positive resolution. There is also an OMEMO plugin for the Gajim desktop IM client and support has been added to the Cryptocat desktop IM application.

Ratchets

OMEMO's design borrows from the Double Ratchet algorithm (formerly known as the Axolotl Ratchet) developed for the TextSecure and Signal apps. The Double Ratchet algorithm, interestingly, is itself derived from the OTR key-exchange protocol. In this context, the "ratchet" is the function used to derive the new ephemeral key pair that a client uses to encrypt its next outgoing message.

OTR required each client to send every new public key to the other party, then wait for an acknowledgment message to return before using the new key pair. This has the drawback of forcing the client to keep using the same key for several messages if the other party is slow to reply (and it has the side effect of requiring the entire conversation to be a "live" session; one cannot send an OTR message to a user who is offline).

In a Double-Ratchet session, the "key" used to encrypt a message is actually a compound object made up of two parts: a "root" key and a "chain" key. Thus, the client can generate a new ephemeral key pair using either of two mechanisms or ratchets. Whenever the participants successfully exchange messages, they can also update the root keys they use, just as in OTR. But, in between receiving messages from the other party, each client uses a second key-derivation function to update the chain key. The second key-derivation function generates a new chain key by hashing the previous chain key. Because this second ratchet derives its new keys solely from old keys, with no Diffie-Hellman exchange required, the client can generate new keys as often as its needs to. Furthermore, the remote client is able to "catch up" whenever it needs to, and it can even recover messages that arrive out-of-order.

Both OTR and Double Ratchet are limited to one-to-one conversations. OTR's limitation comes from the key-exchange protocol itself; the Signal app provides the additional feature of allowing a user to keep conversation history in sync between multiple clients, but it does this by routing the (encrypted) messages through the central Signal servers.

In addition, Double Ratchet (as implemented in Signal) relies on a central server to secure the initial key exchange step between any new pair of clients. Upon registering with the service the first time, each Signal client generates a set of one-time-use "prekeys" that are stored on the server. Whenever a new remote contact initiates a conversation with the client, the server provides that contact with one of the prekeys, thus enabling the client-to-client session setup.

Many-to-many encryption

OMEMO enables multi-client chats by establishing a separate Double Ratchet channel to every participating client in the conversation—including the remote chat partners and every additional client that has been configured by the user. So Alice's desktop chat program sets up a channel not only to Bob, but one to Alice's mobile phone app as well.

Every message sent by the OMEMO application includes a single payload plus a separate header for each client. The payload is the message body, encrypted with an ephemeral key. Each of the headers contains a copy of the message-body's key, encrypted with a different, per-device session key. Thus, the message body is only sent once, but each remote client is only able to decrypt its own header. The ephemeral keys are periodically updated using Double Ratchet, thus providing forward secrecy.

Being built on XMPP, the protocol is largely server-independent and can be federated. However, the XMPP servers employed by the users do need to support Message Carbons (XEP-0280), which relays multiple copies of each message to all of the intended recipients, and Message Archive Management (XEP-0313), which enables a client to retrieve any messages sent while the client was offline. Both of these XEPs are still working their way through the formal approval process.

OMEMO also decentralizes the initial set-up scheme. Whereas Signal requires the central server to store prekeys for every registered client, OMEMO instead uses the Personal Eventing Protocol (PEP), an existing XMPP extension also known as XEP-0163. With PEP, each client randomly generates the equivalent of a prekey each time it starts up and advertises it to the XMPP server. When a chat session is initiated, the users' XMPP servers contact each other to set up the connection, and they relay the current prekeys between the clients. After set-up, the prekeys can be permanently discarded.

Further developments

OMEMO also supports some features not covered by OTR, such as encrypted client-to-client file transfer. This is done by first sending an XMPP message that contains only a decryption key. Subsequently, the sending client can encrypt the file and send it to the recipient using an existing XMPP file-transfer method (of which there are several options, like XEP-0096, XEP-0234 and XEP-0047). Conversations supports the XEP-0234 method, which is built on top of the Jingle protocol.

OMEMO is still rather new, at least in comparison to OTR, but it has been gaining exposure and several free-software application projects have been exploring it of late. For several months, though, the migration of ChatSecure from its own code base to Conversations was held up by a licensing issue. The crux of the matter was that the ChatSecure developers wanted to reuse the Double Ratchet code released by Signal, known as SignalProtocolKit.

But, unlike Conversations, ChatSecure publishes its app for iOS as well as Android, and SignalProtocolKit is under the GPL—preventing it from inclusion in apps distributed through the iOS App Store (at least in the eyes of many license-compliance experts). On June 13, however, Open Whisper Systems updated the license to include an "additional permissions" clause permitting distribution on the iOS App Store. After the announcement, ChatSecure's Chris Ballinger indicated that the porting effort would resume.

Having multiple implementations available is a vital stress-test for any protocol, of course. Signal quickly garnered endorsements from security researchers like Matthew Green, which encouraged other developers to consider utilizing the Double Ratchet algorithm. By adopting it, OMEMO enables chat clients to move beyond OTR's limitations. The next test will be to see whether OMEMO's extensibility not only gives it an edge over OTR, but over Signal as well. Many free-software advocates find Signal's dependence on a centralized server to be a non-starter; OMEMO may allow them to route around the issue entirely.