International Association
for Cryptologic Research

We present a system for key management and protection of data at rest. At the heart of our system is a new protocol for secure key derivation, departing from the common practice of envelope encryption. Our solution adheres to existing enterprise architecture best practices and performance requirements. Our system is implemented at industrial scale, managing tens of thousands of root keys and serving thousands of server side key derivation requests per second. Our system is not only performant in terms of latency and throughput, but also offers non-trivial monetary cost reduction. The talk will present the key derivation protocol, and discuss system’s security and scalability.

Encrochat was a communications network and service provider that offered modified Android smartphones offering end-to-end encrypted communication based on the Signal protocol. In 2020, French law enforcement — in collaboration with agencies in the UK and the Netherlands as well as the European Agency for Law Enforcement Cooperation (Europol) — compromised the Encrochat network and exfiltrated historical data as well as real-time messaging data and metadata for weeks. The compromise remained undetected for approximately two months, after which Encrochat administrators shut down the network. Encrochat was used by organised crime groups in Europe (and elsewhere), and the exfiltrated information was used as supporting evidence in over 6000 arrests and related prosecutions across Europe; the information also led to the seizure or freezing of over 900 million euros as criminal funds, and the seizure of hundreds of tonnes of illegal drugs. The London Metropolitan Police, which made use of the intelligence gathered, described this as “the most significant operation the Metropolitan Police Service has ever launched against serious and organised crime”. In this talk, we examine what is known about how Encrochat was compromised, and how we know what we know at this time. In particular, we will discuss: the security and cryptography features used in Encrochat; what is currently known about how law enforcement breached the Encrochat network in 2020 and a potential earlier compromise; how we pieced together what is currently known from public sources such as historical Internet data, court records, and news reports; and legal, practical, and social limitations on the attack.

This talk will cover Amazon Web Service’s (AWS) experience implementing and deploying cryptographic algorithms (henceforth, by “algorithm” we mean “cryptographic algorithm”), implemented with carefully targeted micro-architectural optimizations and formally verified with Automated Reasoning (AR). We will survey the challenges we faced, their solutions, and innovations we have made, using our development of X25519 and Ed25519 implementations as examples throughout. First we will motivate the choice of those algorithms and the challenges that we faced. Secondly, we will introduce our solutions to those challenges: implementations of X25519 and Ed25519 optimized for both x86_64 and aarch64 micro-architectures; HOL Light, the AR engine used to formally verify correctness of the implementations; and the technology stack used at AWS for algorithm deployment. Thirdly, we will present performance data for our new implementations. Finally, we will present ongoing and future work at AWS combining AR and algorithm implementations. In summary, we will argue that combining AR and algorithm implementations is possible and can yield fruitful results, as well as explaining how AWS deploys algorithms at scale.

This talk will outline the cryptographic protocols which are needed to implement private smart contracts (over and above that of basic FHE encryption and evaluation operations). Our motivation is the Zama fhEVM protocol, but the cryptographic primitives we will outline will be of general interest and apply to many FHE-enabled applications.

This presentation delves into the recent publication of the Messaging Layer Security (MLS) standard, its unique features, and its impact on the future of secure messaging. We will discuss the standardization process of MLS, highlighting what worked, areas for improvement, and how formal analysis has been pivotal in building this new standard for the first time in a way that significantly departs from TLS due to the complexity of the protocol. In the first section, we will explore the core properties of the final version of MLS, such as the continuous group key agreement at its core and diverse properties such as message consistency, features that distinguish it from the Signal protocol. The presentation will cover the tradeoffs chosen by the MLS as we decided to ensure membership agreement and transparency as well as message consistency and non-repudiation as a default unlike existing protocols. We will also explore consequences of those choices such as the increased ability of malicious insiders to perform denial of service attacks on the group in absence of specific extensions being designed for group state proofs of correctness. If time permits, we might mention how to add deniability to the protocol. The next section of the presentation will focus on the future of MLS, discussing Post-Quantum cryptography and our ability to retain PCS in this context. We will mention efficiency challenges, and metadata privacy models depending on service provider architectures which make significant differences in the concrete privacy properties of a deployment. This will be followed by an examination of implementations and deployments, such as in Cisco WebEx and Google's commitment to deploying MLS for Android Messages and RCS 2.0. This last use case is expected to represent over a billion Monthly Active Users in 2024. If time permits, we will discuss potential deployments on platforms like Android and the Web and the challenge it causes, especially with respect to tracking on the Web. A second part of the talk will be dedicated to interoperability challenges in the context of the Digital Market Act (DMA) and how the MIMI working group will tackle that challenge at the IETF. We will explore the influence of DMA on messengers, identify unresolved issues, and discuss the integration of MLS with MIMI, especially with respect to identifiers and privacy considerations. The presentation will conclude with a forward-looking statement about the continued evolution of MLS and its applications. This abstract captures the essence of our discussion: MLS is a substantial development in secure messaging, designed for large dynamic groups and expected to reach billions of monthly active users in the next few years through platforms like Android or the Web. MLS stands as a cornerstone for secure messaging, co-designed with academic input and integrated with technologies like SFrame for WebRTC or eventually later Media over QUIC (MOQ).

In this talk, we describe PQXDH, a new post-quantum key agreement protocol deployed by Signal, its formal analysis using the ProVerif and CryptoVerif protocol analysis tools, and how this analysis influenced version 2 of PQXDH. We focus on the lessons learned in this process and how formal verification can be a powerful tool in an industrial setting. The talk will be given jointly by Rolfe Schmidt and Karthikeyan Bhargavan.

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.

The scale and frequency of password database compromises has led to widespread and persistent credential stuffing attacks, in which attackers attempt to use credentials leaked from one service to compromise accounts with other services. In response, browser vendors have integrated password leakage detection tools, which automatically check the user’s credentials against a list of compromised accounts upon each login, warning the user to change their password if a match is found. In particular, Google Chrome uses a centralized leakage detection service designed by Thomas et al. (USENIX Security ’19) that aims to both preserve the user’s privacy and hide the server’s list of compromised credentials. In this paper, we show that Chrome’s implementation of this protocol is vulnerable to several microarchitectural side- channel attacks that violate its security properties. Specifically, we demonstrate attacks against Chrome’s use of the memory-hard hash function scrypt, its hash-to-elliptic curve function, and its modular inversion algorithm. While prior work discussed the theoretical possibility of side-channel attacks on scrypt, we develop new techniques that enable this attack in practice, allowing an attacker to recover the user’s password with a single guess when using a dictionary attack. For modular inversion, we present a novel cryptanalysis of the Binary Extended Euclidian Algorithm (BEEA) that extracts its inputs given a single, noisy trace, thereby allowing a malicious server to learn information about a client’s password. This paper was presented at USENIX Security 2023, and the full version can be found at https://www.usenix.org/system/files/usenixsecurity23-kwong.pdf

Count-Min Sketch (CMS) and HeavyKeeper (HK) are two realizations of a compact frequency estimator (CFE). These probabilistic data structures maintain a compact summary of high-volume streaming data and provide approximate estimates of the number of times an element occurred. CFEs are commonly used in streaming settings to identify elements with the largest frequencies (i.e., top-K elements, heavy hitters, elephant flows). Finding extreme elements is important for network planning, network monitoring, recommendation systems, etc. Traditionally, probabilistic guarantees on the accuracy of frequency estimates are proved under the implicit assumption that stream elements do not depend upon the internal randomness of the structure. This assumption is often not well-matched with reality; malicious actors could be incentivized to manipulate the data stream. In this talk, we reveal vulnerabilities in CMS and HK to adaptive attacks, by presenting attacks that cause significant estimation errors. For instance, elements never seen in the stream can be manipulated to resemble heavy hitters in CMS. This could, for example, cause network flow monitoring systems relying on CFEs to identify non-existent or benign flows as possible threats. Conversely, HK can make legitimate heavy hitters disappear. We analyze our attacks analytically and experimentally, obtaining a tight agreement between the two. These negative results seem unavoidable for (at least) sketch-based CFEs with parameters that are reasonable in practice. On the positive side, we build a new CFE (Count-Keeper) that can be seen as a composition of the CMS and HK structures. Count-Keeper estimates are typically more accurate (by at least a factor of two) than CMS for “honest” streams. Further, our attacks against CMS and HK are less effective (and more resource intensive) when used against Count-Keeper. Lastly, Count-Keeper has a native ability to flag estimates that are suspicious, which neither CMS or HK (or any other CFE, to our knowledge) admits.

The Internet has plenty of public images that are transformations (e.g., resize, crop, grayscale) of original unpublished ones. Various reasons recommend to keep private an original image, such as its economic value and its sensitive content. Several concrete scenarios, including selling images over the Internet, fighting misinformation and detecting deep fakes, would highly benefit from a system allowing to efficiently prove and verify the authenticity of a transformed image (i.e., the public image is a result of a faithful transformation over a private and authentic original image). This work presents the design of a system allowing the possessor of a signed private image to compute a faithful transformation, guaranteeing 1) confidentiality (no leak), 2) efficient proof generation (the proof can be computed with a cheap laptop), 3) integrity (only the advertised transformations have been applied) and 4) efficient fraud detection (fast detection of bogus proofs). Our system is based on a divide-et-impera approach through sub-transformations applied to tiles of the original image that are then reconnected together along with their sub-proofs. We discuss how to realize a few transformations. In particular, we have performed an experimental evaluation on the popular resize operation and the results confirm the viability of our approach. A faithful transformation of a high-resolution image of 30MP with a tile size of slightly less than 750KP can be generated on a common PC with 16GB of RAM and 8 cores, leaving free some resources for other light computations. The total amount of time to compute the proof for the entire image is slightly more than 45 minutes. Prior results require either an excessive amount of memory during the computation of a proof (resulting in huge proof generation time due to page faults) or the upload of the original image to some external cloud services negatively affecting confidentiality/decentralization.

Mosca introduced three crucial aspects for real-world cryptography in the quantum computing era: security shelf-life, migration time, and collapse time. While collapse time has been extensively studied, migration time has not received as much attention. Acknowledging the complexity of post-quantum cryptography (PQC) migration, NIST launched the `Migration to Post-Quantum Cryptography' project in June 2022. Migration to PQC involves three primary tasks: inventorying the use of cryptography, analyzing risks and determining migration priorities, and executing migration to PQC. The two tasks of inventorying and migration, in particular, demand capabilities of cryptographic visibility and cryptographic agility, respectively. This is especially important for enterprises that own and maintain numerous IT systems for migration at scale. While participating in NIST's `Migration to PQC' project, we investigated the possibility of using existing open sources to obtain cryptographic visibility and agility. More specifically, we modified or extended the features of existing open-source tools in the DevOps pipeline for automated inventorying of cryptographic usage, and also demonstrated changing cryptographic providers without altering applications making use of the well-designed Java Cryptography Architecture. We have gained a clearer understanding and several findings regarding migration to PQC, and this talk will provide insights for IT service providers as well as open-source community regarding PQC migration. Next, we briefly describe how we can make use of existing tools to gain cryptographic visibility and agility.

Over the past 25 years, research has highlighted the fact that high-end hardware can be used by attackers to recover secret keys from devices. Numerous studies have demonstrated innovative secret key extraction techniques that rely on dedicated professional equipment to capture data-dependent physical leakage from target devices. These methods employ equipment like scopes to obtain power traces, software-defined radio and probes to capture electromagnetic radiation (EMR) traces, as well as ultrasonic microphones to capture acoustic traces. While these methods have deepened our understanding regarding the cryptanalytic risks associated with various types of leakage (EMR, acoustic, power) and high-end sensors to secret keys, much less is known about the cryptanalytic risks posed by optical leakage and accessible ubiquitous equipment such as video cameras. In this talk, we will reveal the findings from the two research papers, optical cryptanalysis (CCS’23) and video-based cryptanalysis (SP’24), and discuss how attackers can extract cryptographic keys using video footage of a device’s power LEDs captured by standard video cameras. In the first part of the talk, we will review the history of the side-channel cryptanalytic attacks from the first timing attack that was published in 1996, through the cryptanalytic power-based attacks and cryptanalytic EMR attacks that were published since 1998 until the acoustic attack that was published at 2014 and conclude interesting insights regarding the lessons we learned from these works. Next, we will discuss information leakage from power LEDs (based on the findings presented at CCS 23), and understand why the intensity of the light emitted by a device’s power LED can be used as an alternative to power traces obtained from the device to recover secret keys (2048-bit RSA, 256-bit ECDSA and 378-bit SIKE keys) from commonly used cryptographic libraries (Libgcrypt, GnuPG, PQCryptoSIDH) using a photodiode. In the second part of the talk, we will discuss how standard video cameras (e.g., of an iPhone 13 PRO Max, and security camera) can be used as alternatives for the photodiodes (based on the findings presented at SP’24) to extract secret keys (256-bit ECDSA and 378-bit SIKE keys). We will discuss a video camera’s rolling shutter and understand how it can be used to increase the sampling rate of a video camera from the frame-per-second rate (60 measurements per second) to the rolling shutter rate (60,000 measurements per second). We will see videos of secret key recoveries that were taken by a smartphone and by an Internet-connected security camera to recover a 256-bit ECDSA key (using the Minerva side-channel attack) and a 378-SIKE key (using the HertzBleed side-channel attack). At the end of the talk, we will discuss countermeasures, and provide insights regarding the real potential of extracting cryptographic keys by video cameras in our days and in the near future, taking into account the expected improvements in the specifications of video cameras expected by Moore’s Law.

Certificate Transparency was a response to the 2011 attack on DigiNotar and other Certificate Authorities. These attacks showed that the lack of transparency in the way CAs operate was a significant risk to the Web Public Key Infrastructure (PKI). It led to the creation of the Certificate Transparency project to improve Internet security by bringing accountability to the system that protects HTTPS. Since 2013, the Certificate Transparency community has effectively monitored and fixed certificate anomalies. The award recognizes the enermous effort that it took to make Certificate Transparency a reality on the Web, and the tangible security benefits that it brings to all Web users.

Anonymous credentials, first proposed by Chaum in 1985, enable individuals to prove attributes about themselves without revealing personal information. For example, they can prove that they live in Ontario without revealing their full home address. The award celebrates a sequence of results, starting in 2001, that developed the first efficient and fully anonymous credential schemes. This is an active area of research with many beautiful results by many talented cryptographers. We hope that this recognition will encourage further adoption of this technology.

Microarchitectural side-channel attacks have shaken the foundations of modern processor design. This talk will discuss the latest research on this topic.

The recent Hertzbleed disclosure demonstrates how remote-timing analysis can reveal secret information previously only accessible to local-power analysis. At worst, this constitutes a fundamental break in the constant-time programming principles and the many deployed programs that rely on them. But all hope is not lost. Hertzbleed relies on a coarse-grained, noisy channel that is difficult to exploit. Indeed, the Hertzbleed paper required a bespoke cryptanalysis to attack a specific cryptosystem (SIKE). Thus, it remains unclear if Hertzbleed represents a threat to the broader security ecosystem. In this paper, we demonstrate that Hertzbleed's effects affect cryptosystems beyond SIKE. We demonstrate how latent gadgets in other cryptosystem implementations---specifically ``constant-time'' ECDSA and Classic McEliece---can be combined with existing cryptanalysis to bootstrap Hertzbleed attacks on those cryptosystems.

Incoming regulation on AI such as the EU AI act, requires impact assessment and risk management to ensure fairness, accountability, and provide transparency for “high-risk” AI systems. This seems to require that companies provide unfettered access to a third party auditor who will provide a “seal of approval” before an AI system can be deployed. This often creates a tension between companies trying to protect trade secrets and auditors who need “white box” access to the data and models. In this talk, we examine how cryptography can, not only help resolve this tension, but additionally provide stronger transparency guarantees to the end user. The talk will consist of two parts: 1) An overview of the AI Policy landscape tailored to a cryptographers. The goal of which is to "distill" policy demands into research questions that cryptographers can tackle. 2) Next we will present our construction for "zero-knowledge proofs of training" and discuss challenges and lessons that were learned along the way. The technical paper "Experiment with Zero-Knowledge Proofs of Training" was accepted at CCS 2023.

This talk will discuss a simple approach to “encrypt forever” with a single AES-GCM key. It is called Double-Nonce-Derive-Key AES-GCM (DNDK-GCM) and is based on extending the 96-bit nonce length to any s-bit nonce length for s < 256 (e.g., 192). The security of the resulting AEAD can be proven under the same assumptions that base the security of AES-GCM because no additional cryptographic primitive is involved. The talk will discuss these security margins and explain why it is possible to use DNDK-GCM for processing even a total of 264 bytes under one key and remain withing the NIST specified 2^(-32) margins. This implies that the cryptoperiod of a key is not limited by the cryptographic bounds that indicate key wear-out. As a bonus, we will also toss in a key commitment string. By now, DNDK-GCM has become the default encryption mode on Meta infrastructure. The talk will provide a detailed performance analysis to show the cost of DNDK-GCM, relative to AES-GCM, and to some other AEADs that are being used at Meta. It will explain some considerations and challenges associated with defining and migrating to a new default on live cloud systems, discuss the standards compliance aspect, and provide some numbers on the scale at which this mode operates.

Deployment of end-to-end encryption (E2EE) has improved the confidentiality and the integrity of data in various contexts, including messaging, cloud storage, and other web applications. E2EE protocols, such as messaging and file storage, have been studied extensively, instilling confidence in their security. Consequently, there has been a meteoric rise in the adoption of these tools, and E2EE is now a core component of complex systems that impact billions of users. As these applications evolve into intricate, feature-rich ecosystems, our understanding of their security becomes increasingly opaque, and whether the strong security guarantees of the underlying E2EE protocols extend to the broader systems is unclear. As such, a new line of work has analyzed the security of various deployed E2EE applications, finding numerous attacks and proposing mitigations. The purpose of this talk is to bring attention to an emerging threat model for E2EE applications, and motivate future work within the cryptography community. At a high-level, our threat model considers an adversary that simply sends chosen payloads to a victim client, and subsequently observes the encrypted application state. We refer to attacks in this setting as injection attacks. The core of our presentation will consist of an overview of this threat model, highlighting a common root cause of injection attacks. Then, we will present concrete vulnerabilities uncovered in real-world systems across two application domains: backups of messaging applications (based on a recent paper that we will present at S&P ‘24), and password managers (based on ongoing work, which will be made public after we finish the disclosure process). Lastly, we conclude with some general takeaways and directions for future work.

No abstract

No abstract

End-to-end encryption security guarantees crucially rely on the assumption that the user has the correct identity public key for the person they wish to communicate with. Traditionally, E2EE communication systems have required the user to perform cumbersome manual checks to verify these keys, e.g. by physically scanning QR codes, or by verbally reading a fingerprint. In practice, these verifications are rarely performed. Key transparency, first introduced in CONIKS, allows much of this verification to be automated. Roughly, the communication service provider regularly publishes a commitment to the identity key directory; this commitment must be publicly and consistently visible to all users. Every key request is accompanied by a proof that the key is correct w.r.t. the committed directory. Finally, the user’s device regularly monitors the committed directory to ensure that the user’s key is correctly reflected. This talk will present the motivation for key transparency and introduce the approach and intuition behind the constructions. It will then discuss some areas of active research and open problems.

Zero-Knowledge proofs form the cornerstone of privacy-based cryptography. Research on their efficient realizations based on number-theoretic and hash-based assumptions dates back several decades, and there are now fairly optimized solutions based on these foundations. With the coming of quantum computing, one will eventually need to consider schemes whose security is based on quantum-resistant assumptions. Hash-based schemes are a very good candidate for this; but lattice-based ones could in principle be even more efficient. Basic cryptographic primitives based on lattices, such as KEMs and digital signatures, are faster than their classical counterparts, and shorter than hash-based constructions (such as signatures). Recent papers on lattice-based zero-knowledge have shown that these advantages could also extend into more advanced constructions. One can indeed use efficient lattice operations to construct SNARKs and ZK proofs with significantly shorter proof sizes than the hash-based counterparts. These proofs have already shown themselves useful in the designs of various privacy-based protocols, but like all ZK proofs, they are fairly non-trivial to instantiate and use. Just like proofs based on other assumptions, lattice-based ones are also quite intricate and non-trivial to use. Researchers working on number-theoretic and hash-based proofs have provided excellent libraries that make their proofs easy-to-use. In this work, we do the same for lattices. We implement a library that allows for easy consumption of SNARKs and ZK-proofs by protocol designers. The foundation of the library consists of algebraic operations upon which the most efficient recent lattice-based SNARKs and ZK proofs are built. These low-level implementations, as well as the ZK protocols, are written in C. We then create a Python wrapper that allows protocol designers to easily create instances and create proofs, as well as use the efficient C operations to be able to write their protocols entirely in Python without sacrificing much in the form of efficiency. We illustrate the usefulness of the library with several instantiations of protocols from the literature that utilize lattice-based ZK proofs, and will present live demos.

Security critical software comes with numerous side-channel leakages left unpatched due to a lack of resources or experts. The situation will only worsen as the pace of code development accelerates, with developers relying on Large Language Models (LLMs) to automatically generate code. In this work, we explore the use of LLMs in generating patches for vulnerable code with microarchitectural side-channel leakages. For this, we investigate the generative abilities of powerful LLMs by carefully crafting prompts following a zero-shot learning approach. All generated code is dynamically analyzed by leakage detection tools which are capable of pinpointing information leakage at the instruction level leaked either from secret dependent accesses or branches or vulnerable Spectre gadgets, respectively. Carefully crafted prompts are used to generate candidate replacements for vulnerable code which are then analyzed for correctness and for leakage resilience. After extensive experimentation, we determined that the way prompts are formed and stacked over a series of queries plays a critical role in the LLMs' ability to generate correct and leakage-free patches. We develop a number of tricks to improve the chances of correct and side-channel secure code. Moreover, when we compare various LLMs, we found that OpenAI's GPT4 is far superior compared to Google PaLM and Meta LLaMA in generating patches with nearly all leakages fixed in a microbenchmark of vulnerable codes as well as Spectre v1 gadgets. We also found that GPT4 is more successful than GPT3.5 in generating both correct and secure code, with many failed attempts observed in the latter. As for efficiency, GPT4 provides a far more efficient patch with up to 10 times less overhead when compared to the clang compiler-supported lfence Spectre mitigation. The GPT4-based configuration costs in API calls a mere few cents per vulnerability fixed.

Transparency logs are a powerful tool that makes it possible to bring accountability where it is unpractical to improve trust. Certificate Transparency pioneered and popularized the use of transparency logs, but also presents a model that is not very reusable due to its peculiar PKI context, and the technology has markedly improved since. In this talk we'll discuss the new designs, what properties they provide and when they are appropriate as a solution, how they are implemented, deployed, and scaled, and how they enable new transparency log applications, with plenty of real world examples.

The past year has marked significant progress in secure messaging technologies. In March 2023, the Messaging Layer Security (MLS) protocol was standardized by the IETF, followed by Signal's introduction in May 2023 of PQXDH, a post-quantum alternative to the X3DH handshake. In the first part of this presentation, we identify scalability challenges that may hinder the widespread adoption of MLS and Signal in a post-quantum context, particularly in regions with limited mobile data plans. This analysis is backed by real-world quantitative data. In the second part of this talk, we propose a novel protocol with improved bandwidth consumption. It incorporates efficient post-quantum primitives, specifically multi-recipient public key encryption (mPKEs), optimized for secure messaging. We anticipate that our approach will be an order of magnitude more efficient than direct adaptations of existing protocols in practical scenarios.

Censorship circumvention tools enable clients to access endpoints in a network despite the presence of a censor. Censors use a variety of techniques to identify content they wish to block, including patterns that are characteristic of proxy or circumvention protocols. In response to this class of blocking behavior, circumvention practitioners have developed a family of "fully encrypted" protocols (FEPs), intended to have traffic that appears indistinguishable from random. For such protocols to be effective it is crucial that one can establish shared keys and protocol agreement without revealing to observers that an obfuscated protocol is in use. Despite their social significance to millions of users, there is no formal description of security for this handshake phase. This talk recounts the development of the obfs4 handshake, a highly-adopted FEP used to enable access to the Tor network in censored regions, which has incurred an iterative design process in response to censor behavior. We then present concrete results from our work formalizing obfuscated key exchange, capturing the goals of these protocols concretely and analyzing the obfs4 design. We demonstrate how to extend the obfs4 design to defend against stronger censorship attacks and to make it quantum-safe. With our analysis in mind, we point to challenges that remain in modeling and improving upon obfuscated protocols for future work.

The increasing harms caused by hate, harassment, and other forms of abuse online have motivated major platforms to explore hierarchical governance. The idea is to allow communities to have designated members take on moderation and leadership duties; meanwhile, members can still escalate issues to the platform. But these promising approaches have only been explored in plaintext settings where community content is public to the platform. It is unclear how one can realize hierarchical governance in the huge and increasing number of online communities that utilize end-to-end encrypted (E2EE) messaging for privacy. This talk will argue for the importance of adapting hierarchical governance to E2EE platforms, share some of our recent work towards privacy-preserving hierarchical governance, and discuss ongoing challenges in this space.

Our web search queries reveal sensitive information about us: where we are (“Hikes in Toronto”), how we are feeling (“Causes of neck pain”), what we are doing (“How to find a lawyer”), and much more. Even if we use privacy-conscious search engines, such as DuckDuckGo, the search engine’s servers see our query strings in plaintext. As a result, search engines today accumulate a trove of sensitive data about us; this data is an attractive target for theft in a data breach, abuse by an authoritarian government, or sale to a third party. This talk will present Tiptoe, a search engine that learns nothing about what its users are searching for. With Tiptoe, a client sends only the encryption of its search query to the search engine’s servers. The search engine then executes a cryptographic protocol to identify the web pages that best answer the user’s query—without ever decrypting the query, without learning what the user is searching for, and without learning what search results it is sending back. Tiptoe’s privacy guarantee is based on cryptography alone; it does not require any trusted hardware or non-colluding servers. The Tiptoe search engine answers these queries in the span of seconds: searching over a public web crawl (360 million pages) incurs 57 MiB of client-server communication and 2.7 seconds of client-perceived latency.

Video conferencing apps like Zoom have hundreds of millions of daily users, making them a high-value target for surveillance and subversion. While such apps claim to achieve some forms of end-to-end encryption, they usually assume an incorruptible server that is able to identify and authenticate all the parties in a meeting. Concretely this means that, e.g., even when using the “end-to-end encrypted” setting, malicious Zoom servers could eavesdrop or impersonate in arbitrary groups. In this work, we show how security against malicious servers can be improved by changing the way in which such protocols use passwords (known as passcodes in Zoom) and integrating a password-authenticated key exchange (PAKE) protocol. To formally prove that our approach achieves its goals, we formalize a class of cryptographic protocols suitable for this setting, and define a basic security notion for them, in which group security can be achieved assuming the server is trusted to correctly authorize the group members. We prove that Zoom indeed meets this notion. We then propose a stronger security notion that can provide security against malicious servers, and propose a transformation that can achieve this notion. We show how we can apply our transformation to Zoom to provably achieve stronger security against malicious servers, notably without introducing new security elements.

Billions of devices running the RISC-V Open Source ISA have been shipped, and an increasing number of those implement cryptography instructions from the Cryptography Extensions Task Group (CETG). As a significant development, the RISC-V Android platform requires a CPU with vector cryptography extensions. We describe RISC-V extensions currently being developed for High Assurance and Post-Quantum Cryptography.

Meta has recently begun rolling out default end-to-end encryption to their billions of Messenger users. We announced the project in 2019, and it has involved a long process of development and iteration in order to enable the migration to succeed. Messenger operates within a number of product constraints that increase the complexity of end-to-end encryption from standard approaches described elsewhere, all stemming from users’ expectations that a rich Messenger experience is available across all their devices. For example, we support: * multiple devices for each user, including ephemeral web sessions low-end devices with limited local storage or processing capacity; * message history; which has historically been available to all devices logged in to a Messenger account; * a number of rich features such as social integrations (e.g. sharing posts, previews, sticker search). The underlying architecture can dramatically impact the challenges faced in encrypting messages. Some challenges included: * data was sometimes structured in our backend such that there weren’t clear payloads to encrypt; * our surfaces, such as Facebook Lite, which have historically achieved a lightweight app by rendering the user’s entire screen server-side. Alongside Messenger’s product challenges, it’s helpful to actually be clear about the actual intention of end-to-end encryption. Specifically, in the non-cryptographic privacy goals that it implies around confidentiality and authenticity of messages. To put these into practice within the organisation, we required a more comprehensive approach, which - in retrospect - breaks down into a series of sub-requirements: * Confidential & authentic message transmission & storage. * Private feature implementations. * Limitations on what can be logged. * Application security. * Process to determine what we’re protecting. * A level of verifiability. We learned some general lessons from rolling out end-to-end encryption; including the challenge of communicating such changes to a global audience, as well as in testing and rolling out an inherent shift in product model and architecture in-place within an existing product. This included findings, such as: * Communicating end-to-end encryption with padlock icons in the user interface was at times interpreted differently in different contexts - with interpretations ranging from Meta having locked the chat to implying that the chat itself was subversive. * Replacing a product in-place makes testing especially challenging, as many factors end up being tested simultaneously, with outcomes which are difficult to disentangle. Our approach to message history raised a number of difficulties, including a fundamental tension that exists for storing end-to-end encrypted data; that forces the implementer to choose between sacrificing guaranteed message history availability, guaranteed messaging availability, and the ability to login to Facebook without introducing user-managed keys. To store e2ee messages, we designed a new cryptographic protocol which provides indexed storage, key rotation, and a diversity of recovery methods. The rollout of this created significant product challenges, as users had to make a choice around whether to use this solution, and - if so - how they should manage their recovery codes. This was particularly difficult because many users did not have a good understanding of the changes, we didn’t necessarily have the ability to interrupt the user at an appropriate time for them to think it through, nor did many of them want to engage with these prompts in the first place - despite the importance of making the right choice. Finally, we will look at some of the product features which presented particular challenges for us, and how we addressed making them work. These features include: * Sharing posts from Facebook into messages; which typically provides the user a preview of the post content, but for which the previewed content may be audience-controlled. * Sticker search; for which we wanted to protect the search terms from association with the user. End-to-end encryption for Messenger was a larger change than we had initially anticipated, which introduced complexity in most places that it touched. We learned a lot from addressing this new set of challenges, and we hope that these lessons can apply more broadly in future to help end-to-end encryption gain wider spread adoption.

Secure 2-party computation (2PC) enables secure inference that offers protection for both proprietary machine learning (ML) models and sensitive inputs to them. However, the existing secure inference solutions suffer from high latency and communication overheads, particularly for transformers. Function secret sharing (FSS) is a recent paradigm for obtaining efficient 2PC protocols with a preprocessing phase. We provide SIGMA, the first end-to-end system for secure transformer inference based on FSS. By constructing new FSS-based protocols for complex machine learning functionalities, such as Softmax and GeLU, and also accelerating their computation on GPUs, SIGMA improves the latency of secure inference of transformers by 11 − 19× over the state-of-the-art that uses preprocessing and GPUs. We present the first secure inference of generative pre-trained transformer (GPT) models. In particular, SIGMA executes GPT-Neo with 1.3 billion parameters in 7.4s and HuggingFace’s GPT2 in 1.6s.

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.

The advent of quantum computers has sparked significant interest in post-quantum cryptographic schemes, as a replacement for currently used cryptographic primitives. In this context, lattice-based cryptography has emerged as the leading paradigm to build post-quantum cryptography. However, all existing viable replacements of the classical Diffie-Hellman key exchange require additional rounds of interactions, thus failing to achieve all the benefits of this protocol. Although earlier work has shown that lattice-based Non-Interactive Key Exchange~(NIKE) is theoretically possible, it has been considered too inefficient for real-life applications. In this work, we challenge this folklore belief and provide the first evidence against it. We construct an efficient lattice-based NIKE whose security is based on the standard module learning with errors (M-LWE) problem in the quantum random oracle model. Our scheme is obtained in two steps: (i) A passively-secure construction that achieves a strong notion of correctness, coupled with (ii) a generic compiler that turns any such scheme into an actively-secure one. To substantiate our efficiency claim, we provide an optimised implementation of our passively-secure construction in Rust and Jasmin. Our implementation demonstrates the scheme's applicability to real-world scenarios, yielding public keys of approximately $220$\,KBs. Moreover, the computation of shared keys takes fewer than $12$ million cycles on an Intel Skylake CPU, offering a post-quantum security level exceeding $120$ bits.

The SSH protocol provides secure access to network services, particularly remote terminal login and file transfer within organizational networks and to over 15 million servers on the open internet. SSH uses an authenticated key exchange to establish a secure channel between a client and a server, which protects the confidentiality and integrity of messages sent in either direction. The secure channel prevents message manipulation, replay, insertion, deletion, and reordering. At the network level, SSH uses the SSH Binary Packet Protocol over TCP. In this paper, we show that as new encryption algorithms and mitigations were added to SSH, the SSH Binary Packet Protocol is no longer a secure channel: SSH channel integrity (INT-PST) is broken for three widely used encryption modes. This allows prefix truncation attacks where some encrypted packets at the beginning of the SSH channel can be deleted without the client or server noticing it. We demonstrate several real-world applications of this attack. We show that we can fully break SSH extension negotiation (RFC 8308), such that an attacker can downgrade the public key algorithms for user authentication or turn off a new countermeasure against keystroke timing attacks introduced in OpenSSH 9.5. We also identified an implementation flaw in AsyncSSH that, together with prefix truncation, allows an attacker to redirect the victim’s login into a shell controlled by the attacker. In an internet-wide scan for vulnerable encryption modes and support for extension negotiation, we find that 77% of SSH servers support an exploitable encryption mode, while 57% even list it as their preferred choice. We identify two root causes that enable these attacks: First, the SSH handshake supports optional messages that are not authenticated. Second, SSH does not reset message sequence numbers when encryption is enabled. Based on this analysis, we propose effective and backward-compatible changes to SSH that mitigate our attacks.

In Fall 2021, the president of Museums Moving Forward (MMF) approached us, cryptographers at Boston University, about using MPC to support one of their new projects. In this talk, we will share the story of the resulting deployment of MPC for social good. While our talk will cover the technical details of features we developed in the web-based JIFF framework in response to MMF’s needs, our primary focus will be the lessons that we learned about deploying MPC for social good throughout the process. Working collaboratively across disciplinary boundaries required developing shared language, bridging epistemological gaps, and designing new MPC features on the fly to recover from mistakes. Our goal is to uncover the messiness that usually gets suppressed in technical write-ups of cryptographic deployments. Understanding these pitfalls is critical for the continued growth of MPC and indispensable for cryptographers developing working relationships with non-technical stakeholder groups.

In recent years, FHE has made significant gains in performance and usability. As a result, we see a first wave of real-world deployments and an increasing demand for practical applications of FHE. However, deploying FHE in the real world requires addressing challenges that have so far received less attention, as the community was primarily focused on achieving efficiency and usability. Specifically, the assumption of a semi-honest evaluating party, which is at the core of most FHE research, is incompatible with a large number of deployment scenarios. Scenarios that violate this assumption do not simply suffer from correctness issues, as one might expect, but in fact enable an adversary to completely undermine the confidentiality guarantees of FHE, up to and including very practical key-recovery attacks. As a response, a variety of works have tried to augment FHE for settings beyond the traditional semi-honest assumption. This fundamentally revolves around guaranteeing some form of integrity for FHE, while retaining sufficient malleability to allow homomorphic computations. However, it remains unclear to what extent existing approaches actually address the challenges of real-world deployment, as we identify significant gaps between the assumptions these works generally make and the way state-of-the-art FHE schemes are used in practice. In this talk, we survey and analyze existing approaches to FHE integrity in the context of real-world deployment scenarios, identify capabilities, shortcomings, and promising candidates. We also implemented and evaluated these constructions experimentally on realistic workloads, and we give some numbers. Finally, we conclude with a discussion on current capabilities, recommendations for future research directions, and an overview of the hurdles on the path to our ideal end-goal: a cryptographic equivalent of a trusted execution environment, i.e., a cryptoprocessor enabling fully private and verifiable computation.

Common verification steps in cryptographic protocols, such as signature or message authentication code checks or the validation of elliptic curve points, are crucial for the overall security of the protocol. Yet implementation errors omitting these steps easily remain unnoticed, as often the protocol will function perfectly anyways. One of the most prominent examples is Apple's goto fail bug where the erroneous certificate verification skipped over several of the required steps, marking invalid certificates as correctly verified. This vulnerability went undetected for at least 17 months. In this talk, we ask whether cryptographic implementations have to be so brittle. What if we could make crypto bugs surface through noticeable errors in a program's functionality? We introduce a mechanism which supports such detection of implementation errors on a cryptographic level. Instead of merely returning a binary acceptance decision, we let verification procedures return more fine-grained information in form of what we call a confirmation code. We then show how to escalate verification errors affecting these confirmation codes to functional errors on the overall protocol level. Concretely, we show that when confirmation codes satisfy a carefully defined unpredictability property, we can provably integrate them into secure connection establishment via key exchange and tie security to basic functionality: if verification steps in the key exchange are faulty, the connection establishment will fail, making an implementation error like goto fail detectable through a simple connection test. We present intuitive (and provably secure) confirmation codes for RSA-PSS signatures, HMAC, and the validation of elliptic curve points and discuss what is needed for their practical deployment.

Recent progress in large language models (LLMs) has led to demand for measures to detect AI-generated text, as evidenced by Biden's recent executive order, and pledges by several major companies to embed watermarks in the outputs of their models. A promising and popular solution for detecting AI-generated content is watermarking, where a hidden signal is embedded in the LLM's output. Intuitively, desirable properties of LLM watermarks are clear: they should not hurt the quality of the model, and human-generated text should not be falsely flagged as watermarked. However, these properties are challenging to define because of idiosyncracies in human text and a lack of a clear text quality measure, especially when LLMs have a wide variety of downstream applications. In [CGZ23], we show how {cryptography} can be leveraged to formally define these properties of quality and lack of false positives, which we call undetectability and soundness. Undetectability requires that no efficient algorithm can distinguish between the original LLM and the watermarked LLM. Soundness requires that any fixed text is detected as watermarked with negligible probability. [CGZ23] constructs a fairly simple watermarking scheme that achieves these properties. In this talk, we begin by giving background on policy discussion and media coverage surrounding detection of AI-generated text. We then present our work in [CGZ23], in particular covering the model, definitions, and scheme. We conclude by discussing directions for future work, emphasizing interesting cryptographic questions.

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.

The world of U.S. equities trading is highly competitive, involves many participants, and has significant global impact. Traders in this arena are responsible for overseeing the movement of billions of dollars, often on behalf of others, and thereby have a responsibility to develop reliable and well-performing trading strategies. “Controlling information leakage” is widely considered fundamental to high-quality, competitive trading strategies. In other words, good trading strategies maintain a level of privacy from an outside market observer. However important and highly valued this information leakage control property may seem, to our knowledge there exists no formal definition for this property in the context of equities trading strategies. Our work addresses this and creates a strong foundation for theoretical and practical work in this domain.

One of the most popular symmetric encryption schemes in use on the Internet is ChaCha20-Poly1305. It is the default choice in tools like OpenSSH and Wireguard, and one of only three supported ciphersuites in TLS 1.3. ChaCha20Poly1305 utilizes a polynomial-based hash function for constructing Message Authentication Codes via the Wegman-Carter MAC construction. This entails evaluating the polynomial hash over the data, and blinding the output with a pseudorandom value obtained by enciphering a nonce with a blockcipher. More specifically, it uses Poly1305, originally designed with specific hardware in mind. Today, nearly 20 years later, we ask the following question: Given today's advancements and applications would we still converge to this same design?

Earlier this year, WhatsApp announced their plans to launch key transparency for all WhatsApp users. Key transparency solutions help strengthen the guarantee that end-to-end encryption provides to private, personal messaging applications in a transparent manner available to all. In this presentation, we will cover how key transparency works, what the improved end user experience is for those wishing to verify their contacts' public keys, and various deployment challenges and considerations we encountered when building our key transparency system. We also have released an open-source library called Auditable Key Directory (AKD) which we use in our deployment, and can potentially serve as a reference point for others that wish to deploy key transparency in the future.

In early 2021, Apple announced the AirTag: a quarter-sized low-powered device that utilizes the privacy-preserving FindMy network to find physical objects. The release of Airtags has been highly controversial, in part because stalkers have misused them to track potential victims. In response to this threat, Apple came up with a strategy to detect stalkers at the cost of innocent AirTag users's privacy. Their methodology is currently in the process of being standardized by the IETF. In this talk, we will show that the hard trade-off presented by Apple is not necessary and that it is possible to efficiently achieve both privacy and stalker detection. We hope that by bringing this pressing issue to the attention of the community, we can spur more meaningful discussion on what privacy properties offline-finding networks should provide and incentivize the adoption of more privacy-preserving protocols.

Frequently, users on the web need to show that they are, for example, not a robot, old enough to access an age restricted video, or eligible to download an ebook from their local public library without being tracked. Anonymous credentials were developed to address these concerns. However, existing schemes do not handle the realities of deployment or the complexities of real-world identity. Instead, they implicitly make assumptions such as there being an issuing authority for anonymous credentials that, for real applications, requires the local department of motor vehicles to issue sophisticated cryptographic tokens to show users are over 18. In reality, there are multiple trust sources for a given identity attribute, their credentials have distinctively different formats, and many, if not all, issuers are unwilling to adopt new protocols. We present and build zk-creds, a protocol that uses general-purpose zero-knowledge proofs to 1) remove the need for credential issuers to hold signing keys: credentials can be issued to a bulletin board instantiated as a transparency log, Byzantine system, or even a blockchain; 2) convert existing identity documents into anonymous credentials without modifying documents or coordinating with their issuing authority; 3) allow for flexible, composable, and complex identity statements over multiple credentials. Concretely, identity assertions using zk-creds take less than 150ms in a real-world scenario of using a passport to anonymously access age-restricted videos. This paper was published at IEEE Security and Privacy 2023, and the full version can be found at https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10179430.