The last few years have seen a global uptake in secure messaging. It is only very recent that billions of users have gained access to some form of secure messaging, through WhatsApp, Facebook Secure Conversations, Signal, and many others. Recently, a new IETF Working Group (MLS) was started to develop an open strongly secure messaging standard in the future. These strongly secure messaging tools build on novel cryptographic constructions, and several theoretical challenges remain for secure messaging, for example in the group setting. Thus, secure messaging is highly interesting for academic research but offers also a unique opportunity to contribute to upcoming new standards.

The Workshop on Secure Messaging will include talks from a range of experts in the field. The workshop aims to inform its attendees about the state-of-the-art in secure messaging, and help guide the future theoretical developments. By bringing together both practitioners and theoreticians, the practitioners can inform the cryptographers of real-world constraints and concerns, and vice versa, the cryptographers can offer insights in (im)possibilities.

The workshop is co-located with EuroCrypt in Darmstadt in Germany, and held on Saturday May 18. The workshop includes a range of invited speakers, and attendance is open for anyone who is registered.


The schedule is:

08:30-09:00 Registration opens
09:00-09:45 Raphael Robert (Wire)
09:45-10:30 Paul Roesler (RUB) slides and implementation
10:30-11:00 Coffee break
11:00-11:45 Ania Piotrowska (UCL)
11:45-12:30 Richard Barnes (Cisco) slides, mlspp code, and general MLS implementations
12:30-14:00 Lunch
14:00-14:45 Yevgeniy Dodis (NYU)
14:45-15:30 Paul Grubbs (Cornell) slides (pptx)
15:30-16:00 Coffee break
16:00-16:45 Serge Vaudenay (EPFL) slides and implementations
16:45-17:30 Discussion and wrap up

We hope to see you all there!

Karthik Bhargavan & Cas Cremers

Full program

08:30-09:00 Registration opens
09:00-09:45 Raphael Robert (Wire)

Secure messaging, MLS and Wire

09:45-10:30 Paul Roesler (RUB)

Definitional Foundations of Ratcheting and their Impact on Practice

Paul will talk about the challenges and the importance of defining ratcheting (and especially its security) as it depicts the cryptographic core of modern messaging protocols. Motivated by weaknesses in group messaging protocols (presumably also caused by the lack of well defined security), he will explain how security is defined "naturally": 1) Define a puristic syntax, 2) Model a practical adversary, 3) Require security whenever possible. After examining each of these three steps, he will focus on the impact of defining "natural" and "optimal" security for ratcheting. While it results in a comprehensible definition it may require strong constructions. In this context, strong means good security but potentially also inefficient implementations. He will end his talk by shortly sketching how far such implications provably hold.

slides and implementation

10:30-11:00 Coffee break
11:00-11:45 Ania Piotrowska (UCL)

Encryption is not enough - using mix-networks for anonymous messaging

Over the past years, the increasing concerns about the privacy of our daily communication persuaded many users to turn to messaging applications, like Signal, Telegram or WhatsApp, which offer end-to-end encryption in order to protect the confidentiality of our messages. However, hiding the content of the messages is not sufficient to protect the users' privacy. Studies have shown that the metadata associated with our communication carries a great deal of privacy-sensitive information, which allows adversaries to infer users' communication patterns and their relationships.

This talk provides an overview of mix-networks, which hide the communication metadata and offer strong privacy guarantees. Moreover, it presents the recent design of the Loopix system, a low-latency anonymous communication channel, that provides bi-directional third-party sender and receiver unlinkability. Loopix can be used both for Email and Instant Messaging and competes with the established onion router architectures, embodied in Tor.

11:45-12:30 Richard Barnes (Cisco)

Messaging Layer Security: Past, Present, and Future

Messaging Layer Security (MLS) is an effort to standardize a protocol for asynchronous group authenticate key agreement, with the goal of achieving for group communications what TLS has done for 1-1 communications. The MLS working group has been at work for a little over a year, and the protocol is starting to stabilize. This talk will provide some background about how MLS came to be and a brief overview of how MLS works in its current form. We will also highlight some potential challenges that the protocol may still have to overcome, and some new areas where there might be applications for the lessons learned from MLS.

slides, mlspp code, and general MLS implementations

12:30-14:00 Lunch
14:00-14:45 Yevgeniy Dodis (NYU)

On the Security and Insecurity of TreeKEM

TreeKEM is a novel secure group messaging protocol which is proposed as part of the MLS standard. We give the first formal definitions of secure group messaging and continuous group key agreement, and provide the first security analysis of TreeKEM under our definitions. In particular, we show it has much weaker forward security than what was previously believed, even if no insertions and deletions are allowed (only corruptions and key exposures). We give a give a semi-practical solution achieving dramatically higher security, but leave open the question of what is the best compromise between security and efficiency acceptable for MLS, and whether MLS should pause the adoption of TreeKEM in light of its weak security.

14:45-15:30 Paul Grubbs (Cornell)

Message Franking: Invisible Salamanders, Encryptment, and AMFs

A challenge in deploying end-to-end encrypted (E2EE) messaging is that it prevents the service provider from identifying abusive or threatening messages and taking punitive action against parties that send them. In this talk we study message franking, recently proposed by Facebook as a way to overcome this challenge. Message franking enables verifiable reporting of abusive messages sent in E2EE chats while preserving deniability.

First we will give a high-level overview of the architecture and security goals of message franking, using Facebook's implementation as an example. Next, we will describe a vulnerability in Facebook's message franking implementation: by exploiting the use of Galois/Counter mode for encrypting attachments, a sender can craft an abusive message that the receiver cannot report as abusive. We disclosed this vulnerability to Facebook and were awarded a bug bounty for it.

The flaw in Facebook's scheme stems from the fact that for fast authenticated encryption (AE) schemes like GCM, ciphertexts generally are not binding commitments to the plaintext. Motivated by this, we next turn to building fast AE schemes with committing ciphertexts. We define compactly committing AE (ccAE), a new primitive which is sufficient for message franking when the provider can see communication metadata, and a simplified variant called encryptment. Our first result here is a negative one: existing lower bounds on blockcipher-based hashing imply neither ccAE nor encryptment can be as fast as GCM. Using this connection to hashing we build HFC, a ccAE scheme that uses a single pass of a cryptographic compression function. Our lower bound implies HFC's efficiency is essentially optimal.

Finally, we turn to metadata-private messaging systems, where the service provider cannot see communication metadata. Such systems are becoming increasingly widespread; for example, Signal's new sealed sender feature hides the sender's identity from the server. Message franking schemes like Facebook's cannot be used in metadata-private messaging systems. Other seeming solutions for abuse reporting (such as digital signatures) cannot be used because they break deniability. To enable abuse reporting for metadata-private messaging we introduce asymmetric message franking (AMF) schemes. We describe security goals for AMFs as well as an instantiation based on proofs of knowledge.

Joint work with Jiahui Lu, Thomas Ristenpart, Yevgeniy Dodis, Joanne Woodage, Nirvan Tyagi, Ian Miers, and Julia Len.

slides (pptx)

15:30-16:00 Coffee break
16:00-16:45 Serge Vaudenay (EPFL)

A Proper Security Level for Postcompromise Secure Messaging

Following up mass surveillance and privacy issues, modern secure communication protocols now seek more security such as forward secrecy and post-compromise security. CRYPTO 2018 includes two protocols with optimal security, but requiring huge complexity. Another protocol in EUROCRYPT 2019 has "near-optimal" security and lower (but still high) complexity. In those protocols, exchanging n messages has complexity O(n^2). In this work we relax security a bit more and present a protocol BARK (for bidirectional asynchronous ratcheted key agreement). We provide a simple security model and we reach linear complexity.

slides and implementations

16:00-17:30 Discussion and wrap up