International Association
for Cryptologic Research

Cryptographic schemes often contain verification steps that are essential for security. Yet, faulty implementations missing these steps can easily go unnoticed, as the schemes might still function correctly. A prominent instance of such a verification step is the re-encryption check in the Fujisaki–Okamoto (FO) transform that plays a prominent role in the post-quantum key encapsulation mechanisms (KEMs) considered in NIST's PQC standardization process. In KEMs built from FO, decapsulation performs a re-encryption check that is essential for security, but not for functionality. In other words, it will go unnoticed if this essential step is omitted or wrongly implemented, opening the door for key recovery attacks. Notably, such an implementation flaw was present in HQC's reference implementation and was only noticed after 19 months. In this work, we develop a modified FO transform that binds re-encryption to functionality, ensuring that a faulty implementation which skips re-encryption will be exposed through basic correctness tests. We do so by adapting the "verifiable verification" methodology of Fischlin and Günther (CCS 2023) to the context of FO-based KEMs. More concretely, by exporting an unpredictable confirmation code from the public key encryption and embedding it into the key derivation function, we can confirm that (most of) the re-encryption step was indeed performed during decapsulation. We formalize this concept, establish modified FO transforms, and prove how unpredictable PKE confirmation codes turn into noticeable correctness errors for faulty implementations. We show how to apply this technique to ML-KEM and HQC, both with negligible overhead, by leveraging the entropy lost through ciphertext compression or truncation. We confirm that our approach works through mathematical proofs, as well as experimental data. Our experiments show that the implementation flaw in HQC's reference implementation indeed makes basic test cases fail when following our approach.

Hiding the metadata in Internet protocols serves to protect user privacy, dissuade traffic analysis, and prevent network ossification. Fully encrypted protocols require even the initial key exchange to be obfuscated: a passive observer should be unable to distinguish a protocol execution from an exchange of random bitstrings. Deployed obfuscated key exchanges such as Tor's pluggable transport protocol obfs4 are Diffie-Hellman-based, and rely on the Elligator encoding for obfuscation. Recently, Günther, Stebila, and Veitch (CCS '24) proposed a post-quantum variant pq-obfs, using a novel building block called obfuscated key encapsulation mechanisms (OKEMs): KEMs whose public keys and ciphertexts look like random bitstrings. For transitioning real-world protocols, pure post-quantum security is not enough. Many are taking a hybrid approach, combining traditional and post-quantum schemes to hedge against security failures in either component. While hybrid KEMs are already widely deployed (e.g., in TLS 1.3), existing hybridization techniques fail to provide hybrid obfuscation guarantees for OKEMs. Further, even if a hybrid OKEM existed, the pq-obfs protocol would still not achieve hybrid obfuscation. In this work, we address these challenges by presenting the first OKEM combiner that achieves hybrid IND-CCA security with hybrid ciphertext obfuscation guarantees, and using this to build Drivel, a modification of pq-obfs that is compatible with hybrid OKEMs. Our OKEM combiner allows for a variety of practical instantiations, e.g., combining obfuscated versions of DHKEM and ML-KEM. We additionally provide techniques to achieve unconditional public key obfuscation for LWE-based OKEMs, and explore broader applications of hybrid OKEMs, including a construction of the first hybrid password-authenticated key exchange (PAKE) protocol secure against adaptive corruptions in the UC model.

Elligator is widely used to encode elliptic-curve public keys in protocols that require random-looking bytestrings. These include password authenticated key exchange protocols (e.g., EKE) as well as protocols which attempt to avoid fingerprinting (e.g., Tor's obfs4 pluggable transport). We consider a replacement for Elligator in the post-quantum setting. We present Kemeleon: novel encodings for ML-KEM public keys and ciphertexts into bytestrings which are computationally indistinguishable from random. Kemeleon includes variants that allow for optimized implementations or deterministic encodings. We then consider how to combine traditional and post-quantum obfuscated key encapsulation mechanisms (KEMs). In contrast with hybrid key exchange where simple concatenation yields a secure solution, hybrid obfuscation is more subtle, and can require a nested construction when computational assumptions are involved. From Kemeleon and hybrid obfuscated KEMs, we show how to construct obfuscated key exchange as well as the first known hybrid password authenticated key exchange protocol which is secure in the adaptive-corruptions model.

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.

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 key exchange protocol that establishes initial shared secrets in the handshake of the Signal end-to-end encrypted messaging protocol has several important characteristics: (1) it runs asynchronously (without both parties needing to be simultaneously online), (2) it provides implicit mutual authentication while retaining deniability (transcripts cannot be used to prove either party participated in the protocol), and (3) it retains security even if some keys are compromised (forward secrecy and beyond). All of these properties emerge from clever use of the highly flexible Diffie--Hellman protocol. While quantum-resistant key encapsulation mechanisms (KEMs) can replace Diffie--Hellman key exchange in some settings, there is no KEM-based replacement for the Signal handshake that achieves all three aforementioned properties, in part due to the inherent asymmetry of KEM operations. In this paper, we show how to construct asynchronous deniable key exchange by combining KEMs and designated verifier signature (DVS) schemes. There are several candidates for post-quantum DVS schemes, either direct constructions or via ring signatures. This yields a template for an efficient post-quantum realization of the Signal handshake with the same asynchronicity and security properties as the original Signal protocol.

The Signal protocol for end-to-end encrypted messaging provides a range of desirable security properties: asynchronicity, offline deniability, mutual implicit authentication, forward secrecy, and post-compromise security. Transitioning Signal to a post-quantum secure version with the same guarantees proves tricky, however. This is due to the fact that post-quantum key encapsulation mechanisms cannot be used as a drop-in replacement for the clever use of the Diffie--Hellman protocol in Signal's initial key exchange X3DH. In this talk, we elaborate on this obstacle, which may arise in further high-level protocols with subtle security guarantees, and show how to achieve asynchronous deniable key exchange from key encapsulation mechanisms and designated verifier signatures. In particular, we present a provably-secure construction for the post-quantum Signal initial key agreement which achieves the same security guarantees as the currently used X3DH.

In this paper, we study algorithm substitution attacks (ASAs), where an algorithm in a cryptographic scheme is substituted for a subverted version. First, we formalize and study the use of state resets to detect ASAs, and show that many published stateful ASAs are detectable with simple practical methods relying on state resets. Second, we introduce two asymmetric ASAs on symmetric encryption, which are undetectable or unexploitable even by an adversary who knows the embedded subversion key. We also generalize this result, allowing for any symmetric ASA (on any cryptographic scheme) satisfying certain properties to be transformed into an asymmetric ASA. Our work demonstrates the broad application of the techniques first introduced by Bellare, Paterson, and Rogaway (Crypto 2014) and Bellare, Jaeger, and Kane (CCS 2015) and reinforces the need for precise definitions surrounding detectability of stateful ASAs.

We analyze the handshake protocol of the Transport Layer Security (TLS) protocol, version 1.3. We address both the full TLS 1.3 handshake (the one round-trip time mode, with signatures for authentication and (elliptic curve) Diffie–Hellman ephemeral ((EC)DHE) key exchange), and the abbreviated resumption/“PSK” mode which uses a pre-shared key for authentication (with optional (EC)DHE key exchange and zero round-trip time key establishment). Our analysis in the reductionist security framework uses a multi-stage key exchange security model, where each of the many session keys derived in a single TLS 1.3 handshake is tagged with various properties (such as unauthenticated versus unilaterally authenticated versus mutually authenticated, whether it is intended to provide forward security, how it is used in the protocol, and whether the key is protected against replay attacks). We show that these TLS 1.3 handshake protocol modes establish session keys with their desired security properties under standard cryptographic assumptions.

We present KEMTLS, an alternative to the TLS 1.3 handshake that uses key-encapsulation mechanisms (KEMs) instead of signatures for server authentication. Among existing post-quantum candidates, signature schemes generally have larger public key/signature sizes compared to the public key/ciphertext sizes of KEMs: by using an IND-CCA-secure KEM for server authentication in post-quantum TLS, we obtain multiple benefits. A size-optimized post-quantum instantiation of KEMTLS requires less than half the bandwidth of a size-optimized post-quantum instantiation of TLS 1.3. In a speed-optimized instantiation, KEMTLS reduces the amount of server CPU cycles by almost 90% compared to TLS 1.3, while at the same time reducing communication size, reducing the time until the client can start sending encrypted application data, and eliminating code for signatures from the server's trusted code base.

The Signal protocol is a cryptographic messaging protocol that provides end-to-end encryption for instant messaging in WhatsApp, Wire, and Facebook Messenger among many others, serving well over 1 billion active users. Signal includes several uncommon security properties (such as “future secrecy” or “post-compromise security”), enabled by a technique called ratcheting in which session keys are updated with every message sent. We conduct a formal security analysis of Signal’s initial extended triple Diffie–Hellman (X3DH) key agreement and Double Ratchet protocols as a multi-stage authenticated key exchange protocol. We extract from the implementation a formal description of the abstract protocol and define a security model which can capture the “ratcheting” key update structure as a multi-stage model where there can be a “tree” of stages, rather than just a sequence. We then prove the security of Signal’s key exchange core in our model, demonstrating several standard security properties. We have found no major flaws in the design and hope that our presentation and results can serve as a foundation for other analyses of this widely adopted protocol.