Today, the Messaging Layer Security (MLS) protocol has been published as RFC 9420, a standards track document by the Internet Engineering Task Force (IETF). MLS is the first standardized and fully specified end-to-end encryption protocol. The specification is freely accessible, and its security has been analyzed in a series of academic publications.

Our team has been involved in the design and development of the MLS protocol since the very beginning. Over the course of five years, along with others from the MLS IETF working group, we have iterated to combine modern academic proposals with real-life requirements from the industry. The protocol has already proven its aptitude in large-scale deployments with major companies like Cisco and RingCentral having already integrated an early version of MLS into their products, serving millions of users.

This blog post gives a high-level overview of MLS, its practical applications, and why it matters.

The early days and the standardization process

Prior to MLS, a comprehensive specification of a protocol for end-to-end encryption informed by industry-wide input did not exist.

Protocols like the Off-the-Record protocol, the Wickr protocol, and the Signal protocol paved the way with modern security properties and asynchronous messaging capabilities.

The Signal protocol introduced the asynchronous mode of operation the Off-the-Record protocol was lacking and has made end-to-end encryption available to mobile messaging. It has since become the reference for practical and high-quality end-to-end encryption. However, a few derivatives emerged due to the lack of both a full specification and permissively licensed implementations. These derivatives have seen different levels of analysis and every provider has had to maintain their own libraries.

Generally, existing protocols were typically focused on end-to-end encryption between two peers. Using them to protect group chats with many peers proved difficult and either meant compromising on security properties or accepting high computational and bandwidth costs.

Various stakeholders from the industry and academia identified these gaps and started initial talks for an open standard for asynchronous group messaging with modern security properties solving an entire range of issues. In March 2018, these “Birds of a Feather” finally flocked together and the MLS working group was subsequently established.

During the protocol design process, the working group followed an iterative approach that involved multiple rounds of review, feedback, and refinement. Regular members of the working group, as well as other interested individuals, carefully reviewed the Internet-Drafts, providing feedback, suggesting changes, and engaging in technical discussions. Numerous cryptographic experts from academia and industry analyzed MLS and the different security guarantees it aims to provide, sharing their findings in several academic publications. This was particularly beneficial to mitigate security issues before deploying it in production environments.

How is MLS different from existing protocols?

Compared to existing protocols such as the Off-the-Record and the Signal protocol, MLS offers improvements in multiple ways.

Efficiency: Do more with less

Secure messaging protocols in use today were designed as one-to-one protocols, with group messaging functionality built directly from one-to-one channels between all group members. This leaves the sender of a message to encrypt and upload a message for each other group member individually, leading to a complexity of O(n), where n is the number of members in a group. In contrast, MLS typically has costs of O(log n) for the same scenario, making it well-suited even for large groups.

Constructions such as Sender Keys improve the efficiency of the approach of one-to-one protocols, however, their security guarantees do not reach those of the base protocol. In particular, achieving good Post-Compromise Security guarantees is prohibitively expensive with Sender Keys. In other words, removing users from a group chat or ensuring a compromised device has no long-term negative impact incurs high bandwidth and computation costs for all members of the group. To recover from a compromise of a single member of the group, all other members have to broadcast an update of their key material. This leads to an overall cost of computation and bandwidth of O(n^2) for a group size of n and requires all group members to come online at least once. In contrast, MLS has an update operation with complexity of O(log n)  that requires only the compromised member to be online for the group to recover from the compromise.

MLS achieves its low complexity through the use of a binary tree. This means that the number of required operations and the payload size do not increase linearly with the group size but rather only logarithmically after a short warm-up period. Example: In a group with 1000 members, the number of required operations to calculate new group keys would only be 10 as opposed to 1000 with existing protocols. With an assumed base payload size of 100 B per key negotiation, the total payload size would only be 1 KB instead of 100 KB.

A new security notion: Group Integrity

As existing protocols don’t have a notion of groups, messaging apps either manage group membership on the server side in plain text or combine the end-to-end encryption protocol with an additional group management protocol such as Signal’s Private Group System.

In MLS, all group members cryptographically agree on the current state of the group, including who is a part of it. As a consequence, a group member can only decrypt messages from other group members if the sender and the receiver generally agree on the group state and specifically on who is in the group. In other words, it becomes impossible for a third party to add a member to a group without all existing members of the group being aware of it.

Synchronizing data in a distributed system: A hard problem becomes easier

Distributing and synchronizing data across multiple clients can be a daunting task. Aside from confidentiality, MLS also addresses the issue of synchronizing data between members of a group. The corresponding mechanism is directly derived from the group integrity property. Instead of only agreeing on a member list, members of a group can agree on arbitrary data. MLS relies on a component called Delivery Service that ensures an in-order delivery of MLS messages. This ordering then dictates how clients move incrementally from one group state to the next.

With that, an MLS group can become a distribution channel for whatever data needs to be synchronized between different entities by guaranteeing cryptographical agreement on previous extension messages. In other words, this simply means that members of a group can be sure all other members saw the same messages previously.

Extensible: Tune it for your needs

MLS is also extensible, which means that the protocol can be modified, or additional data can be added to the state of a group. The latter can be used, for example, to attach data such as a group name or an image to the group state.

The protocol has a negotiation mechanism that ensures that extensions are only used if they are supported by all members of a group. Group members also agree on which extensions are mandatory in a group.

Since MLS is fundamentally also a group key negotiation protocol, additional cryptographic key material can be exported by all members of a group. This mechanism – called Exporter – can be used to derive encryption keys. For example, participants of audio/video calls or conferences can use MLS to generate encryption keys for end-to-end encryption of the media streams.

Future-proof: Version and cipher suite agility

In contrast to many existing end-to-end encryption protocols, MLS allows members to signal which versions of MLS and which MLS cipher suites they support. In the future, this lets applications safely transition to a newer version of MLS or gradually roll out support for new cipher suites without confusion between individual clients. An example of such a transition could be that a secure messaging application rolls out MLS and later wants to transition to a post-quantum secure cipher suite.

The next steps

Now that the standard is established, we focus more on making end-to-end encryption ubiquitous. We believe that accessibility to the technology is paramount, and we want to complement the specification with a general-purpose implementation published under a permissive license: OpenMLS. Along with our partners at Cryspen, we have evolved OpenMLS over the years into a software library that can be used in various projects. OpenMLS is licensed under the MIT license to minimize friction and make it broadly accessible.

Additional resources

• See the full specification: RFC 9420
• Don’t want to read anymore? Listen to the Security Cryptography Whatever Podcast episode about MLS
• Tired of listening? Watch the Black Hat talk on MLS: Towards a New Era of Secure Group Messaging

Our team has been active in the secure messaging field for over a decade and co-authored the MLS protocol specification. If you are interested in using MLS in general or our MLS implementation (OpenMLS) in particular in your application, do not hesitate to contact us and let us know how we can help. We offer consulting services around MLS and messaging architecture as well as development services related to OpenMLS.

This blog first appeared here.