International Association
for Cryptologic Research

In 2020, the Federal Communications Commission (FCC) began mandating the adoption of the STIR/SHAKEN protocol by all telephone service providers operating in the United States. This protocol aims to reduce the number of fraudulent robocalls by creating a reputation system for providers, disincentivizing providers from permitting fraudulent calls to originate from their network. This talk will discuss our ongoing study of the privacy implications of STIR/SHAKEN. Our study has uncovered severe privacy issues stemming from the design and implementation of the cryptography in STIR/SHAKEN. Notably, STIR/SHAKEN requires, for every call, highly sensitive call metadata (e.g., caller and callee numbers) to be signed in a cryptographically non-repudiable way and transmitted unencrypted between providers; this gives anyone the ability to cryptographically assert a call took place. Further, because third-party signing-as-a-service is widespread, this highly sensitive metadata is often revealed to off-path third parties. The talk will give the relevant background on telephony and STIR/SHAKEN, describe these privacy issues in detail, and discuss our ongoing research on solutions. We will also highlight unusual real-world cryptography challenges that arise, such as blind verification for signatures.

Over the past decade, proof systems, and especially zero-knowledge proofs, have seen an explosion of interest from academic researchers and practitioners. The resulting modern proof systems are being widely deployed in blockchain and cryptocurrency settings. Though built using novel technical ideas, many modern proof systems share a key ingredient with classic schemes: the Fiat-Shamir (F-S) transform. F-S is a generic way to compile an interactive proof system with a public-coin verifier to a non-interactive one by hashing the prover’s messages to generate verifier’s challenges. Prior work has shown that it is surprisingly easy to implement F-S incorrectly, and that incorrect F-S breaks classic proof systems like Schnorr. However, little is known about the risk of incorrectly implementing F-S for the modern proof systems being used in practice today; since more proof systems that use F-S are being deployed than ever before, it is crucial to understand whether vulnerable code exists and how it could be exploited. In this talk, we will present a broad survey of the state of the Fiat-Shamir transform in implementations of modern proof systems. Our talk’s contributions are fourfold. First, we will describe an extensive survey we conducted on implementations of the F-S transform in modern proof systems which identified dozens of incorrect implementations. For one such implementation, Incognito Chain’s Bulletproofs, the incorrect implementation could have led to untraceable theft of millions of dollars of funds. Second, we introduce novel attacks on incorrect F-S for four modern proof systems of interest: Bulletproofs, Plonk, Wesolowski’s VDF, and Spartan. We demonstrate attacks on adaptive knowledge soundness for all four protocols: for example, using the F-S transform described in the Wesolowski’s VDF paper, an attacker could claim to have performed orders of magnitude more squarings than it actually did. Third, we look at the applications in which these proof systems are used and try to understand whether these attacks are exploitable in relevant application contexts. Here the picture is more mixed: we show that the vulnerabilities are clearly exploitable in some applications, such as transactions using Plonk or Bulletproofs, but in other cases external constraints seem to prevent “lifting” soundness attacks to overlying protocols. Finally, we develop a set of clear recommendations to academic researchers and practitioners to try to ensure future implementations of proof systems use F-S correctly. This talk is based on a paper that was published at IEEE S&P ‘23, where it received a Distinguished Paper Award.

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.

Increasing deployment of advanced zero-knowledge proof systems, especially zkSNARKs, has raised critical questions about their security against real-world attacks. Two classes of attacks of concern in practice are adaptive soundness attacks, where an attacker can prove false statements by choosing its public input after generating a proof, and malleability attacks, where an attacker can use a valid proof to create another valid proof it could not have created itself. Prior work has shown that simulation-extractability (SIM-EXT), a strong notion of security for proof systems, rules out these attacks. In this paper, we prove that two transparent, discrete-log-based zkSNARKs, Spartan and Bulletproofs, are simulation-extractable (SIM-EXT) in the random oracle model if the discrete logarithm assumption holds in the underlying group. Since these assumptions are required to prove standard security properties for Spartan and Bulletproofs, our results show that SIM-EXT is, surprisingly, ``for free'' with these schemes. Our result is the first SIM-EXT proof for Spartan and encompasses both linear- and sublinear-verifier variants. Our result for Bulletproofs encompasses both the aggregate range proof and arithmetic circuit variants, and is the first to not rely on the algebraic group model (AGM), resolving an open question posed by Ganesh et al. (EUROCRYPT'22). As part of our analysis, we develop a generalization of the tree-builder extraction theorem of Attema et al. (TCC'22), which may be of independent interest.

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.

A core goal of the NIST PQC competition is to produce PKE schemes which, even if attacked with a large-scale quantum computer, maintain the security guarantees needed by applications. The main security focus in the NIST PQC context has been IND-CCA security, but other applications demand that PKE schemes provide 'anonymity' (Bellare et al., ASIACRYPT 2001), and 'robustness' (Abdalla et al., TCC 2010). Examples of such applications include anonymous cryptocurrencies, searchable encryption, and auction protocols. However, almost nothing is known about how to build post-quantum PKE schemes offering these security properties. In particular, the status of the NIST PQC candidates with respect to anonymity and robustness is unknown. This paper initiates a systematic study of anonymity and robustness for post-quantum PKE schemes. Firstly, we identify implicit rejection as a crucial design choice shared by most post-quantum KEMs, show that implicit rejection renders prior results on anonymity and robustness for KEM-DEM PKEs inapplicable, and transfer prior results to the implicit-rejection setting where possible. Secondly, since they are widely used to build post-quantum PKEs, we examine how the Fujisaki-Okamoto (FO) transforms (Fujisaki and Okamoto, Journal of Cryptology 2013) confer robustness and enhance weak anonymity of a base PKE. We then leverage our theoretical results to study the anonymity and robustness of three NIST KEM finalists---Saber, Kyber, and Classic McEliece---and one alternate, FrodoKEM. Overall, our findings for robustness are definitive: we provide positive robustness results for Saber, Kyber, and FrodoKEM, and a negative result for Classic McEliece. Our negative result stems from a striking property of KEM-DEM PKE schemes built with the Classic McEliece KEM: for any message 'm', we can construct a single hybrid ciphertext 'c' which decrypts to the chosen 'm' under any Classic McEliece private key. Our findings for anonymity are more mixed: we identify barriers to proving anonymity for Saber, Kyber, and Classic McEliece. We also found that in the case of Saber and Kyber, these barriers lead to issues with their IND-CCA security claims. We have worked with the Saber and Kyber teams to fix these issues, but they remain unresolved. On the positive side, we were able to prove anonymity for FrodoKEM and a variant of Saber introduced by D'Anvers et al. (AFRICACRYPT 2018). Our analyses of these two schemes also identified technical gaps in their IND-CCA security claims, but we were able to fix them.

Oblivious RAM (ORAM) is a powerful technique to prevent harmful data breaches. Despite tremendous progress in improving the concrete performance of ORAM, it remains too slow for use in many practical settings; recent breakthroughs in lower bounds indicate this inefficiency is inherent for ORAM and even some natural relaxations. This work introduces snapshot-oblivious RAMs, a new secure memory access primitive. Snapshot-oblivious RAMs bypass lower bounds by providing security only for transcripts whose length (call it c) is fixed and known ahead of time. Intuitively, snapshot-oblivious RAMs provide strong security for attacks of short duration, such as the snapshot attacks targeted by many encrypted databases. We give an ORAM-style definition of this new primitive, and present several constructions. The underlying design principle of our constructions is to store the history of recent operations in a data structure that can be accessed obliviously. We instantiate this paradigm with data structures that remain on the client, giving a snapshot-oblivious RAM with constant bandwidth overhead. We also show how these data structures can be stored on the server and accessed using oblivious memory primitives. Our most efficient instantiation achieves O(log c) bandwidth overhead. By extending recent ORAM lower bounds, we show this performance is asymptotically optimal. Along the way, we define a new hash queue data structure—essentially, a dictionary whose elements can be modified in a first-in-first-out fashion—which may be of independent interest.

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.

This talk will discuss a novel application of cryptography, the zero-knowledge middlebox. There is an inherent tension between ubiquitous encryption of network traffic and the ability of middleboxes to enforce network usage restrictions. An emerging battleground that epitomizes this tension is DNS filtering. Encrypted DNS (DNS-over-HTTPS and DNS-over-TLS) was recently rolled out by default in Firefox, with Google, Cloudflare, Quad9 and others running encrypted DNS resolvers. This is a major privacy win, protecting users from local network administrators observing which domains they are communicating with. However, administrators have traditionally filtered DNS to enforce network usage policies (e.g. blocking access to adult websites). Such filtering is legally required in many networks, such as US schools up to grade 12. As a result, Mozilla was forced to compromise, building a special flag for local administrators to instruct Firefox not to use Encrypted DNS. This example points to an open question of general importance, namely: can we resolve such tensions, enabling network policy enforcement while giving users the maximum possible privacy? Prior work has attempted to balance these goals by either revealing client traffic to trusted hardware run by the middlebox (e.g. Endbox) or using special searchable encryption protocols which enable some policy enforcement on encrypted traffic (e.g. Blindbox, Embark) by leaking information to the middlebox. Instead, we propose utilizing zero-knowledge proofs for clients to prove to middleboxes that their encrypted traffic is policy-compliant, without revealing any other additional information. Critically, such zero-knowledge middleboxes don’t require trusted hardware or any modifications to existing TLS servers. We implemented a prototype of our protocol using Groth16 proofs which can prove statements about an encrypted TLS 1.3 connection such as “the domain being queried in this encrypted DNS packet is not a member of the specified blocklist.” With current tools, our prototype takes on the order of ten seconds to produce one proof. While this is too slow for use with interactive web-browsing, it is close enough that we consider it a tantalizing target for future optimization. This talk will cover the tension between encryption and policy-enforcing middleboxes, including recent developments in Encrypted DNS and the necessity of DNS filtering. It will briefly survey existing solutions before presenting and arguing for the new zero-knowledge middlebox paradigm. Finally, the talk will describe our prototype implementation and several optimizations developed for it, as well as future avenues for improvement and open research questions.

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.

In this talk I will present the design, analysis, and implementation of Pancake, the first system to protect key-value stores from access pattern leakage attacks with small constant factor bandwidth overhead. First, I will outline our new formal security model, and explain why it captures realistic attacks. Then, I will describe our frequency smoothing mechanism, which provably transforms plaintext accesses into uniformly-distributed encrypted accesses. Finally, I will explain the implementation and evaluation of the Pancake system itself. We integrated Pancake into three key-value stores used in production clusters, and demonstrated its practicality: on standard benchmarks, PANCAKE achieves 229× better throughput than non-recursive Path ORAM - within 3-6× of insecure baselines for these key-value stores.

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.

Message franking enables cryptographically verifiable reporting of abusive messages in end-to-end encrypted messaging. Grubbs, Lu, and Ristenpart recently formalized the needed underlying primitive, what they call compactly committing authenticated encryption (AE), and analyze security of a number of approaches. But all known secure schemes are still slow compared to the fastest standard AE schemes. For this reason Facebook Messenger uses AES-GCM for franking of attachments such as images or videos.We show how to break Facebook’s attachment franking scheme: a malicious user can send an objectionable image to a recipient but that recipient cannot report it as abuse. The core problem stems from use of fast but non-committing AE, and so we build the fastest compactly committing AE schemes to date. To do so we introduce a new primitive, called encryptment, which captures the essential properties needed. We prove that, unfortunately, schemes with performance profile similar to AES-GCM won’t work. Instead, we show how to efficiently transform Merkle-Damgärd-style hash functions into secure encryptments, and how to efficiently build compactly committing AE from encryptment. Ultimately our main construction allows franking using just a single computation of SHA-256 or SHA-3. Encryptment proves useful for a variety of other applications, such as remotely keyed AE and concealments, and our results imply the first single-pass schemes in these settings as well.