Message Franking: Invisible Salamanders, Encryptment, and AMFs

Paul Grubbs


A challenge in deploying end-to-end encrypted (E2EE) messaging is that it prevents the service provider from performing moderation: 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 that would have allowed a sender to send un-reportable abusive messages. We disclosed this vulnerability to Facebook and were awarded a bug bounty for it. The flaw stems from the fact that for fast authenticated encryption (AE) schemes, ciphertexts can be decrypted to different plaintexts under different keys (formally, they are not binding commitments). Next, to address this we will define and analyze compactly committing AE (ccAE) and encryptment, two new symmetric-key primitives. We show a lower bound on the efficiency of these primitives and construct a ccAE scheme called HFC that meets our lower bound.

Finally, we will turn to metadata-private messaging systems, where the service provider cannot see communication metadata. One such system is Signal, where senders can hide their identities from the server. Because prior message franking schemes are insecure without metadata and digital signatures break deniability, moderation for metadata-private messaging is currently impossible. To close this gap 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.

Time and Place

Friday, May 24, 4:15pm
Gates 358