We started talking about Messaging Layer Security (MLS) last December and we would now like to give an overview of what was discussed during the second MLS interim meeting that was held on 14th and 15th of January 2019 in Mountain View, CA. Wire is a founding member of the Messaging Layer Security (MLS) IETF working group and continues to contribute with ideas and code. A lot of small and big topics were discussed at the interim meeting. Some of the topics had been discussed before and were continued, others were new. This is a summary of the most important themes that have come up in discussion.
This topic might be the most fundamental one. Federation means that members of group conversations can be users of different server instances, avoiding a centralised service. While MLS never prohibited federation, it was at best federation agnostic. During this interim the proposal was made to include federation more strongly in the design considerations and the proposal was adopted as a future goal for MLS. Wire’s goal has always been to achieve federation between different compatible backends and this brings us one step closer to that goal!
Re-balancing trees for more efficiency
This topic is very technical and deals with the internal representation of client-side data. With the TreeKEM construction, MLS internally uses binary trees for all cryptographic operations between members of a group. This topic is about re-balancing trees to make them more efficient. When members are removed from a group, their leaf node and direct path are blanked (the values of the nodes are deleted), punching holes in the tree. When other members later update their leaf node, the holes in the tree will be overwritten. Ideally, this will “heal” the inner nodes of the tree over time. However, the leaf node of the removed member will never be overwritten by this mechanism, leaving the tree unbalanced. An unbalanced tree does not decrease the security guarantees, only the efficiency. A discussion took place about how previously blanked leaf nodes can be re-used by new members and how existing members can be moved into them.
Lazy handshake messages
Handshake messages are currently designed in a way that the sender of the message does most of the work. For example, new node secrets are encrypted to their members via KEM construction with an effort of between O(log n) and O(n), depending how how many inner nodes of the tree are populated. Recipients can then decrypt new values with an effort of O(1). This work load asymmetry can be particularly penalising in situations where changes have to be made to many groups at once. This is for example the case in a multi-device scenario, where devices have to be added and removed to all groups at once. A proposal was discussed on how this particular problem could be alleviated by introducing so-called “lazy” handshake message. With such messages, the sender would not calculate new values and encrypt them to the rest of the group, but rather just publish the intention. Any other member of the group (including the sender) can finish the operation at a later point in time, when it is more convenient and/or efficient. The advantage is that bottlenecks can be avoided that way, and the postponed cost might even decrease over time, while the security guarantees are not affected as such.
Exploring techniques for server assistance
Server assistance has been discussed before, in particular at the IETF 103 meeting in Bangkok last year. The underlying assumption is that it might be impractical for members to synchronise their group state from one device to another, or between members’ devices. The concept of server assistance revolves around caching some or all of the group state data on the server and make it selectively available when it is needed by devices, eliminating the need for other devices to bulk upload it in its entirety. This sort of assistance brings up the question how the privacy and confidentiality of group members can be best preserved, if the server is to cache data potentially long-term. During this meeting, the idea of using proxy re-encryption (PRE) was explored, under the assumption that it might be a suitable mechanism to shield data from the server while still making it available efficiently to devices.
The MLS working group is lucky to have a comparatively high number of participants from academia. The goal for the MLS protocol is to be formally verified, similar to how it was done with TLS 1.3. Formal verification has become an increasingly present element in modern security protocols and ensures that the security promises are actually security guarantees. In addition to that, a more long-term goal is to generate a formally verified implementation, which is similar to the approach taken with F* code into NSS, but here the protocol is new and has data structures of unbounded size, which poses some technical challenges. Roughly, the implementation is written in a high-level functional language similar to ML, where security properties are proven, and then C code (or even optimised assembly) is extracted from the high-level implementation.
During the meeting the status quo of the current analysis work was discussed and a temptative timeline for future steps was laid out.
In addition to the topics mentioned above, many others were discussed during the two days of the meeting. A more detailed overview can be found in the interim minutes.
Raphael Robert, Head of Security