International Association
for Cryptologic Research

This talk will propose a new approach for building the next generation of AEAD. In the last few years, researchers and practitioners have discovered that widely deployed AEAD schemes, designed almost two decades ago, have many limitations. These range from uncomfortably small security margins to outright security vulnerabilities. We will discuss foundational theory and concrete designs for the next generation of AEAD schemes. Our designs better support real-world workloads while retaining performance.

A line of recent work has highlighted the importance of context commitment security, which asks that authenticated encryption with associated data (AEAD) schemes will not decrypt the same adversarially-chosen ciphertext under two different, adversarially-chosen contexts (secret key, associated data, and nonce). Despite a spate of recent attacks, many open questions remain around context commitment; most obviously nothing is known about the commitment security of important schemes such as CCM, EAX, and SIV. We resolve these open questions, and more. Our approach is to, first, introduce a new framework that helps us more granularly define context commitment security in terms of what portions of a context are adversarially controlled. We go on to formulate a new security notion, called context discoverability, which can be viewed as analogous to preimage resistance from the hashing literature. We show that unrestricted context commitment security (the adversary controls all of the two contexts) implies context discoverability security for a class of schemes encompassing most schemes used in practice. Then, we show new context discovery attacks against a wide set of AEAD schemes, including CCM, EAX, SIV, GCM, and OCB3, and, by our general result, this gives new unrestricted context commitment attacks against them. Finally, we explore the case of restricted context commitment security for the original SIV mode, for which no prior attack techniques work (including our context discovery based ones). We are nevertheless able to give a novel $\bigO(2^{n/3})$ attack using Wagner's k-tree algorithm for the generalized birthday problem.

The recently passed EU Digital Markets Act (DMA) will require large “gatekeeper” companies like Meta and Apple who run widely used end-to-end encrypted (E2EE) messaging apps to allow interoperability with other smaller E2EE apps, on request. Users will be able to communicate with each other across providers: for example, a user on Signal would be able to chat with a user on WhatsApp. The law itself is light on details or concrete requirements, leading to both its supporters and detractors arguing based more on speculation rather than hard evidence. One thing these opposing sides agree on is that the DMA’s interoperability mandate will require fundamental changes to the design of existing E2EE messaging. But what changes will the law require, exactly? How will these requirements be translated into new designs? Will these new designs have new security challenges? These and other critical technical questions lack clear answers today; since legal interoperability requirements under the DMA could take effect as soon as March 2024, and similar legislation has been proposed in the US, it is imperative that the community starts trying to answer these questions now. The purpose of this talk is to introduce E2EE messaging interoperability to the broader cryptography community. Our first task will be to interpret -- guided by existing legal analyses, where available -- the text of the DMA’s interoperability mandate for the community, highlighting requirements and identifying key pieces we believe will have the biggest impact on new designs. Next, we will break down the specific challenges of interoperability in three key areas: identity, protocols, and abuse prevention. For each area, we will briefly survey the landscape of possible designs, critically evaluate proposed solutions, identify novel cryptography-focused questions where more research is needed, and elaborate a minimal list of properties we believe any solution should satisfy. We also identify a set of overarching principles that should guide new designs, e.g. limiting cross-platform metadata leakage. Our goal is to bring the cryptography community into the ongoing dialogue between regulators, policy scholars, industry practitioners, and users about what interoperable E2EE messaging will look like.

This talk will make the case, on behalf of a group of authors of many of the recent results on commitment in AEAD, that the community should prioritize and standardize AEAD designs that achieve commitment to the key, associated data, and nonce. We call this context commitment. The main benefit of such schemes is that they preclude practitioners from having to make choices about what parts of the context should be committing. While context commitment has not yet seen the same kind of attacks in practice as key commitment, we expect them to be discovered and, to get ahead of attackers, standardization efforts should therefore target context commitment. We will start our presentation by defining context commitment [BH22], highlighting in particular how it is not formally implied by key commitment. We next discuss new attacks that exploit this gap, including showing context-commitment attacks on recently proposed key commitment-secure schemes [Kra19, §3.1.1], [ADG+22, §5.3], and [D+22]. These hint at a rich landscape of possible attacks, and we briefly discuss frameworks that explore this landscape [BH22,CR22,MLGR22]. Finally, we provide an overview of recent proposals for new AEAD schemes that achieve context commitment, and discuss avenues for future work.

Authenticated encryption with associated data (AEAD) forms the core of much of symmetric cryptography, yet the standard techniques for modeling AEAD assume recipients have no ambiguity about what secret key to use for decryption. This is divorced from what occurs in practice, such as in key management services, where a message recipient can store numerous keys and must identify the correct key before decrypting. Ad hoc solutions for identifying the intended key are deployed in practice, but these techniques can be inefficient and, in some cases, have even led to practical attacks. Notably, to date there has been no formal investigation of their security properties or efficacy. We fill this gap by providing the first formalization of nonce-based AEAD that supports key identification (AEAD-KI). Decryption now takes in a vector of secret keys and a ciphertext and must both identify the correct secret key and decrypt the ciphertext. We provide new formal security definitions, including new key robustness definitions and indistinguishability security notions. Finally, we show several different approaches for AEAD-KI and prove their security.

In this talk we introduce partitioning oracles, a new class of decryption error oracles which, conceptually, take a ciphertext as input, and output whether the decryption key belongs to some known subset of keys. These can arise when encryption schemes are not committing with respect to their keys, and lead to vulnerabilities when keys are lower entropy, such as human-chosen passwords. We detail adaptive chosen ciphertext attacks that exploit partitioning oracles to efficiently recover passwords. The attacks utilize efficient key multi-collision algorithms --- a cryptanalytic goal that we define --- against the widely used authenticated encryption with associated data (AEAD) schemes, including AES-GCM, XSalsa20/Poly1305, and ChaCha20/Poly1305. Finally, we discuss why these findings point to the need to develop and standardize efficient committing AEAD schemes for widespread deployment.

Zoom’s platform provides video conferencing services for hundreds of millions of daily meeting participants. They use Zoom to conduct business, learn among classmates scattered by recent events, connect with friends and family, collaborate with colleagues, and in some cases, discuss critical matters of state. Zoom is working hard to improve meeting security for its users. In May 2020, Zoom published an incrementally deployable proposal\footnote{\url{https://github.com/zoom/zoom-e2e-whitepaper}}, describing not only a design for its improved end-to-end encryption (E2EE), but also a plan to build an auditable and persistent notion of identity for all Zoom users, which will provide additional security even against active attacks from a compromised Zoom server. In this talk, I will first describe our improved end-to-end design, report on our progress deploying it, and comment on some lessons we learned along the way. Then, I will look to the future and present our vision for user identity protocols. I will argue why it matters, discuss the issues which make this problem hard, and how we plan to address them.

Content moderation is crucial for stopping abusive and harassing messages in online platforms. Existing moderation mechanisms, such as message franking, require platform providers to be able to associate user identifiers to encrypted messages. These mechanisms fail in metadata-private messaging systems, such as Signal, where users can hide their identities from platform providers. The key technical challenge preventing moderation is achieving cryptographic accountability while preserving deniability.In this work, we resolve this tension with a new cryptographic primitive: asymmetric message franking (AMF) schemes. We define strong security notions for AMF schemes, including the first formal treatment of deniability in moderation settings. We then construct, analyze, and implement an AMF scheme that is fast enough to use for content moderation of metadata-private messaging.