Workshop on Secure Messaging

Secure messaging, MLS and Wire

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.

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.

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

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.

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)

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