Secure Messaging Protocols Part 1: A Brief History

In this series of blog posts, I’m going to talk about secure messaging protocols. The first post will discuss some important milestones in their history that led us to where we are today. The next post will go over some exciting cutting-edge developments currently taking place both in the industry and in the cryptographic research community around the topic of secure messaging protocols. Finally, I’ll talk about some important future directions I think secure messaging will move towards in the future.

Be it to defend against criminals, overzealous data collection, espionage, mass surveillance, or other threats, secure messaging protocols are a central tool with which we defend ourselves. Although some version of such protocols has been around since (at least) the early 80’s, recently there have been growing efforts from several quarters to develop new, more powerful, and yet also more secure versions.

To provide some context, I’ll first recall a few historical highlights in the industry, explaining what I think makes them interesting and how they have influenced our current state of the art. However, the bulk of the post will be about the recent push to create better protocols in several new and exciting directions. My goal here is to describe things in a way that’s accessible both to interested users as well as security researchers interested in learning about how things are evolving for what I believe to be one of the most widely and regularly used types of security tool.

What is a “Secure Messaging Protocol”?

A secure messaging protocol (SMP) allows remote users to send messages (and more) to each other securely over an untrusted (and possibly adversarial) network such as the Internet. In general, to use an SMP, participants first have to go through some type of trusted setup, often called “contact discovery”. The type of security that is provided differs between SMPs and must be balanced against other costs such as the resources required to run the protocol, the flexibility of the protocol, and its implementation cost. Given all of these considerations, it is probably not surprising that we find ourselves with a large and growing collection of candidate SMPs out there.

One thing to keep in mind as you read on: the messaging protocol is only one aspect of a wider secure messaging platform like Wickr. In fact, many other features besides the protocol must be carefully considered and executed if the platform is to be secure in any practical sense.

Nevertheless, the protocol used by a platform is truly a fundamental building block. If the underlying SMP is not secure, then no amount of other security features, thorough engineering, and well-designed UX can make the wider platform truly secure in any sort of meaningful sense. Yet, like almost all modern cryptography, SMPs have evolved into finely tuned, delicate constructions that have progressed steadily over decades and through many iterations.

PGP: A First Step

As long as there has been writing, there has been some form of “secret” writing used to secure the exchange of messages, so choosing a starting point for this story is a bit arbitrary. Nevertheless, I think the Pretty Good Privacy protocol (PGP) is probably a good place to begin. First introduced in 1991 by Phil Zimmerman, it allows users to encrypt and digitally sign emails which are then delivered via the standard email protocol (i.e. SMTP). What makes PGP interesting for this post is that it was one of the very first SMPs to be (at least somewhat) widely implemented, deployed, and used. In fact, PGP and a similar protocol called S/MIME developed a decade later are still used in some communities to this day. As such, PGP has had a huge influence on future SMPs, not least of which by setting the initial bar against which we measure newer protocols. I’d like to highlight the following features of PGP (and S/MIME).

  • Asynchronous Communication: One of the most useful aspects of using PGP with email is that this allows users to communicate with each other even if they are not online at the same time. Indeed, if Bob is not online when Alice sends him a PGP protected email, then Bob’s email server will store the messages until Bob comes online again and retrieves it from his inbox. This is known as asynchronous communication, and nowadays it has become an essential part of what we expect from our (even non-secure) messaging protocols.
  • End-to-End Security: From a security standpoint, PGP is built around an E2E security model. Essentially, this means that users can communicate securely, even via an adversarially controlled network and server infrastructure. The worst the network/infrastructure can do is deny service to a user. Crucially though, this means that all intermediary devices tasked with transferring a message from Alice to Bob are incapable of reading the message or modifying it. That is, PGP provides both E2E privacy and E2E authenticity. So, for example, as long as Alice keeps her PGP keys safe, no one other than Alice can create a PGP message that would be accepted by Bob as having been sent by Alice. This stands in contrast to other contemporary (and even quite modern) messaging systems such as SMS, normal emails, and even Facebook Messenger or Google Hangouts. PGP showed us that this level of exposure to malicious infrastructure is not necessarily incompatible with messaging services (even asynchronous ones).

OTR: Security++

Another major milestone in the story of SMPs took place with the introduction of the Off-the-Record protocol (OTR) in 2004 by Nikita Borisov, Ian Avrum Goldberg, and Eric A. Brewer. With the goals of deniability and long-term security in mind, the protocol introduced two new security features to the world of SMPs.

  • Forward Secrecy: Roughly speaking, an SMP provides forward secrecy (FS) if messages are encrypted with temporary (a.k.a. ephemeral) key material which is deleted again by the sender/receiver as soon as the message has been sent/received. Once delivered, the protocol ensures that, regardless of all future compromises, no one (including the legitimate sender and receiver) will ever again be able to decrypt that message. This even holds if the long-term key material of all participants is leaked to an adversary. Intuitively, this provides a type of long-term security, because even if an adversary records an encrypted message during transmission, once the message has been delivered there is no means left for the adversary to ever go back and decrypt that message, regardless of who gets compromised in the future.
  • Deniable Authentication: As mentioned above, an SMP provides authentication if it is impossible to forge the origin of a message; that is, no one but Alice can create messages that Bob will accept as having been sent by Alice. Deniable authentication goes a step further by also guaranteeing that once an encrypted and authenticated message is delivered, anyone is capable of producing a “fake” encrypted message that looks like it came from Alice. In other words, during a conversation between Alice and Bob, only Alice can produce messages that Bob will accept. Yet, once the conversation is complete, anyone (not just Bob) can produce a fake encrypted message (with arbitrary content) that looks like it came from Alice in that conversation. In effect, this means that a transcript of OTR encrypted messages does not provide any (at least cryptographic) evidence that the conversation took place, let alone what was actually said and by whom, since it’s easy to fake such transcripts. It is in this sense that OTR provides a type of deniability.

Wickr: The Best of Both Worlds.

Both PGP and OTR provided E2E security. However, neither quite fulfills all the requirements we have come to expect from today’s secure messaging protocols. On the one hand, PGP allows for asynchronous communication but lacks forward secrecy, while OTR provides forward secrecy but doesn’t support asynchronousity. Thus, a new milestone was reached in 2013 with the public release of the new Wickr SMP, which combined all 3 of these properties into a single protocol. To the best of my knowledge, this makes Wickr the first publicly available SMP meeting today’s basic standard of security, now commonly expected of any SMPs.

The Double Ratchet: A Trade-Off

In 2014, Open Whisper Systems released the Signal SMP, whose main component is the novel key agreement (sub)protocol later dubbed the Double Ratchet. In fact, the Double Ratchet remains a central piece in many of today’s modern SMPs (e.g. Viber, Wire, WhatsApp, Signal, and more). Like Wickr’s SMP, the ones based on the Double Ratchet are designed to achieve both E2E security and FS while still allowing for asynchronous messaging. However, in other ways, these two types of SMPs are simply incomparable.

Multiple Receivers: While the Double Ratchet seems to be an inherently 2-party protocol (i.e. with 1 sender and 1 receiver), the Wickr SMP lends itself quite naturally to sending messages to multiple receivers. On the one hand, this makes supporting multiple devices on an account much easier (at least at the protocol level). On the other hand, this also means that group chats require almost no further effort to be supported on the protocol level. Both are important features of a messaging platform.

Due to its 2-party nature, supporting groups and multiple devices per account using the Double Ratchet require a fair bit of non-trivial cryptographic design and engineering. Various solutions have been built so far, each exhibiting different trade-offs. For example, Signal’s SMP essentially re-encrypts and re-sends messages to each receiver. On the other hand, WhatsApp’s SMP (also based on the Double Ratchet) requires a mobile device in order to make use of the service on a PC. Generally, it’s fair to say that Wickr has one of the most powerful and flexible features of any platform out there when it comes to supporting multiple devices on an account, and that is in no small part because of the flexibility of its SMP.

Deniability: On the other hand, Double Ratchet based SMPs can, under some conditions, provide a slightly stronger deniability guarantee. Essentially, Wickr’s SMP authenticates messages using digital signatures with long term keys, while Double Ratchet SMPs normally use Message Authentication Codes (MACs) with ephemeral keys.

Now, one might think it is easier to link the signatures to a message than the MACs (at least once ephemeral key material has been deleted). However, it’s not quite that straightforward as senders actually sign the *encrypted* message, not the plaintext. What’s more, that encryption uses ephemeral keys. This means that, once a Wickr SMP packet is delivered to a recipient, the relevant decryption keys are deleted and there is no longer any way to show that the cipher text in the packet actually encrypts a particular plaintext, even if we know that to be the case. In other words, the actual message (if not the ciphertext) becomes deniable again.

Moreover, the signatures themselves are also encrypted using keys derived from the identities of the sender and receivers. So if any of these identities are unknown, the signatures cannot even be recovered from the packet, making even the ciphertext deniable.

Channel Healing: Another way in which the security of the two SMPs is incomparable concerns which types of attacks they can recover with which type of security. This type of “healing” property is what is referred to as Post Compromise Security (PCS), and it has become an important topic of ongoing research and development for new SMPs.

Post Compromise Security: Roughly speaking, a security protocol (e.g. an SMP) is said to have Post Compromise Security if, after a compromise of one or more of the participants and once the attacker loses access to the compromised devices, the participants eventually return to a fully secure state (e.g. their messages are both private and authenticated). Crucially, this should result from normal usage of the protocol and participants remain oblivious to the compromise. In a sense, PCS requires the protocol to constantly be “healing” itself.

Frankly speaking, a full coverage of the PCS of the two SMPs and how they compare could fill an entire blog post on its own. So, to keep things within reason, I’ll just give a couple of highlights.

Suppose all the data on Alice’s device was leaked to Michael, including all of her secret keys she was using for a Double Ratchet based SMP. Once this happens, Michael is able to decrypt any traffic she sends or receives. Moreover, Michael also gains the ability to forge new messages on Alice’s behalf to all of her contacts. In fact, Michael can also forge messages to Alice impersonating any of her contacts. Michael can even kick Alice’s contacts out of their shared conversation for good, so that no future message the contact sends to Alice will ever be accepted by Alice again. In practice, such messages will most likely simply be silently dropped by her app without even informing her. However, if Michael remains passive, doing nothing more than eavesdropping after he learned Alice’s state, then eventually Alice can refresh all of her secrets in a way that “heals” her security; both privacy and authenticity. That is, eventually Michael loses all capabilities he gained from learning her state earlier on.

For Wickr’s SMP, the situation is somewhat different with some advantages and other disadvantages. As before, immediately after the state compromise, Michael can read messages sent to Alice. However, this time around, the outgoing messages sent by Alice remain indecipherable. Moreover, Michael does not have the ability to permanently kick other parties off the channel. Similarly, while the adversary can again forge messages from Alice to her contacts, this is no longer true for messages sent to Alice. Finally, if Michael remains passive after the compromise (i.e. he, at most, eavesdrops on Alice), then eventually Alice can heal to the extent that even her incoming messages become indecipherable to Michael again. However, he will not lose the capability to forge messages on Alice’s behalf.

Stay Tuned

As our digital infrastructure becomes ever more complicated (while often also staying in use for years at a time), being “secure” is more and more a process rather than some kind of fixed state. A big part of that process is how we respond to and recover from breaches. It is within this context that forward secrecy and Post Compromise Security have become such interesting security goals for modern SMPs. While forward secrecy is, by now, a well understood security property, cryptographers and security engineers are now pushing the boundaries of what we can achieve in terms of PCS and other types of security for SMPs. To read more about the bleeding edge of research and development on SMPs, both in industry and in academia, stay tuned for the next part in this series.