LEO-Range: Physical Layer Design for Secure Ranging with Low Earth Orbiting Satellites

Bundled Authenticated Key Exchange: A Concrete Treatment of Signal's Handshake Protocol and Post-Quantum Security

Speakers: Keitaro Hashimoto (National Institute of Advanced Industrial Science and Technology (AIST)); Shuichi Katsumata (National Institute of Advanced Industrial Science and Technology (AIST) and PQShield); Thom Wiggers (PQShield)

Conference: USENIX Security

YouTube: This is a peer-reviewed conference paper, not a recorded talk. There is no video URL.

Overview

This technical article delves into a significant research paper presented at USENIX Security, titled "Bundled Authenticated Key Exchange: A Concrete Treatment of Signal's Handshake Protocol and Post-Quantum Security." Authored by Keitaro Hashimoto, Shuichi Katsumata, and Thom Wiggers, the work addresses critical challenges in formally analyzing and securing the Signal protocol's handshake mechanisms, particularly in the face of emerging quantum computing threats. The paper introduces a novel cryptographic model called Bundled Authenticated Key Exchange (BAKE), which offers a unified and concrete framework for understanding the security properties of Signal's X3DH and PQXDH protocols, as well as for designing future post-quantum secure handshakes.

The research is highly relevant given Signal's pervasive use as the foundation for end-to-end encryption in popular messaging applications like WhatsApp and Facebook Messenger, collectively securing billions of conversations. Prior analyses of these protocols, and proposals for post-quantum alternatives, have relied on tailored models that often made ad-hoc adaptations to standard authenticated key exchange (AKE) definitions. This fragmentation has led to unclear concrete security guarantees and difficulties in comparing different protocols. The BAKE model overcomes these limitations by explicitly modeling prekey bundles and their associated states, enabling a more accurate and comprehensive security assessment.

A key contribution of this work is the analysis of Signal's current protocols—the classically secure X3DH and the "harvest-now-decrypt-later" (HNDL) secure PQXDH—against the rigorous BAKE framework. The authors formally demonstrate that these protocols, while robust for their intended purposes, do not achieve what they define as "optimal security." Furthermore, the paper introduces RingXKEM, a fully post-quantum Signal handshake protocol specifically designed to achieve this optimal security within the BAKE model. RingXKEM's design incorporates innovative techniques like Merkle trees for efficient prekey bundle storage, a feature that could not have been captured by previous, less comprehensive models. The findings of this research have been acknowledged by Signal developers, indicating a potential impact on future protocol designs and implementations.

Background

The Signal protocol has established itself as the de-facto standard for end-to-end encrypted messaging, underpinning secure communications for billions of users across various platforms. Its initial handshake mechanism, X3DH (Extended Triple Diffie-Hellman), was designed to facilitate secure conversations, particularly when one party might be offline. X3DH relies on a combination of long-term identity keys, signed prekeys, and ephemeral keys to establish a shared secret, which is then used by the Double Ratchet protocol for ongoing message encryption.

The advent of quantum computing, however, poses a significant threat to classical cryptographic primitives like Diffie-Hellman key exchange. In response to this, Signal introduced PQXDH in late 2023, an iteration of X3DH designed to provide harvest-now-decrypt-later (HNDL) security. This means that even if an adversary harvests encrypted communications today, they should not be able to decrypt them later when powerful quantum computers become available, provided certain conditions are met, particularly regarding the post-quantum key encapsulation mechanism (KEM) prekeys. However, PQXDH's authentication still relies on classical cryptography.

A persistent challenge in the cryptographic analysis of Signal-like protocols has been the complexity introduced by prekey bundles. These bundles allow a sender to initiate a secure conversation with a potentially offline receiver by using pre-generated public key material. Previous security analyses of X3DH and PQXDH, as well as proposals for fully post-quantum alternatives, have typically employed highly tailored models specific to individual protocols. This often involved ad-hoc adaptations of "standard" AKE definitions, making it difficult to achieve concrete security guarantees or to compare the security properties of different protocols in a unified manner. Crucially, these tailored models often treated each prekey bundle or its components independently, failing to capture scenarios where protocols share state across multiple prekey bundles – a design pattern that can lead to more efficient and potentially more secure constructions. The lack of a unified model also made it difficult to formally analyze the implications of state compromises, such as the leakage of ephemeral keys associated with prekey bundles. This problem highlighted the need for a more comprehensive and practice-oriented cryptographic model that could accurately reflect the nuances of Signal's handshake protocols.

Key Findings

The paper introduces Bundled Authenticated Key Exchange (BAKE), a foundational and unified security model specifically designed to address the complexities of Signal's handshake protocols. BAKE formally models prekey bundles and their associated states, a critical advancement over previous approaches that often treated bundles independently. This enables the definition of various granular levels of security, accommodating classical, harvest-now-decrypt-later (HNDL), and fully quantum adversaries within a single framework.

Through the BAKE model, the authors conducted a rigorous analysis of Signal's existing protocols:

• X3DH and PQXDH Do Not Achieve Optimal Security: The analysis formally proves that both X3DH and PQXDH, while providing strong security for their intended purposes, exhibit well-documented weaknesses that prevent them from reaching what the BAKE model defines as "optimal security." These weaknesses include:
• Sender Impersonation on Receiver State Compromise: Both protocols are vulnerable to an attack where a sender can be impersonated to a receiver if the receiver’s state is compromised.
• Weak Forward Secrecy for Sender Sessions: Because a component of the prekey bundles (specifically, the ephemeral Diffie-Hellman public key opk in X3DH/PQXDH) is not signed, sender sessions only achieve weak forward secrecy. An adversary who compromises the receiver's identity secret key after a session is established can impersonate a sender.
• HNDL Limitations for PQXDH: While PQXDH aims for HNDL security, this is conditional. If a classical adversary obtains the secret associated with the post-quantum KEM prekey, all HNDL security is lost against a later quantum adversary. The BAKE model explicitly quantifies these known weaknesses as "unavoidable attacks," providing a clear comparison point for other protocols.

• Formal Treatment of Authentication: The BAKE model explicitly treats authentication as a primary goal, which enabled the authors to capture attacks previously overlooked or implicitly handled. This includes:
• KEM Re-encapsulation Attacks: These attacks, observed during PQXDH's development, force two users to establish the same key while disagreeing on the encapsulation key. BAKE explicitly identifies this as a violation of its Match predicate.
• Replay Attacks: The model captures replay attacks, where an adversary forces a receiver to derive the same session key multiple times, particularly when last-resort prekey bundles are reused. This was largely unaddressed by prior game-based models, highlighting the BAKE model's practical utility.

• Introduction of RingXKEM for Optimal Post-Quantum Security: The paper proposes RingXKEM, a novel, fully post-quantum Signal handshake protocol. RingXKEM is designed to achieve optimal security in the BAKE model against fully quantum adversaries. Its key innovations include:
• Post-Quantum Ring Signatures: Used for deniable post-quantum authentication.
• Post-Quantum KEM Key Exchange: Provides post-quantum secrecy.
• Merkle Tree Optimization: To address the large size of post-quantum signatures, RingXKEM authenticates prekey bundles using a Merkle tree. Only the root of the tree is signed by the identity key, significantly reducing server-side storage costs by storing a single large post-quantum signature instead of one per prekey bundle. This state-sharing mechanism across many prekey bundles is a feature unique to RingXKEM that could not have been adequately analyzed by previous models.

• Real-World Impact and Dialogue with Signal: The authors engaged in continuous dialogue with Signal developers, who confirmed the findings. In response, Signal is considering modifications to better separate the handshake from the Double Ratchet protocol and to refine the user’s view into the key derivation function, potentially incorporating suggestions from this research.

Technical Deep Dive

The Bundled Authenticated Key Exchange (BAKE) model is meticulously crafted to capture the specific mechanics and security considerations of Signal's handshake protocols. It defines a two-round protocol syntax comprising four PPT (Probabilistic Polynomial Time) algorithms:

1. BAKE.IdKeyGen($1^\lambda$): Generates an identity public key ik and secret key isk for a user.
2. BAKE.PreKeyBundleGen($isk_u$): Takes a user's identity secret key and outputs a list of L one-time prekey bundles and a special last-resort prekey bundle ($prek_{u,\perp}$), along with a unified user state st_u. A crucial innovation here is the return of a single state st_u that contains all private information for the generated prekey bundles. This allows for accurate modeling of state compromises, especially for ephemeral keys associated with unused bundles.
3. BAKE.Send($isk_s, ik_r, prek_{r,t}$): The sender algorithm uses its identity secret key, the receiver's identity key, and a chosen prekey bundle to output a session key K and a handshake message ρ.
4. BAKE.Receive($isk_r, st_r, ik_s, t, ρ$): The receiver algorithm processes the handshake message ρ using its identity secret key and current state st_r to derive a session key K' and a potentially updated state st_r. The state is rolled back if key agreement fails.

The BAKE security model employs an interactive, game-based approach between an adversary and a challenger. It introduces instance identifiers (iID) to track protocol executions, which are extended beyond standard AKE definitions to differentiate between one-time and reusable last-resort prekey bundles. Each iID records granular information such as role, Sender, Receiver, prek, prekidx, epoch, prekreuse, ρ, and key. The epoch mechanism tracks the expiration of key material, and prekreuse specifically monitors the reuse count of last-resort prekey bundles.

A cornerstone of BAKE's security definition is the concept of Origin Instances and Partners.

• Origin Instance (Definition 4): An instance iID' is an origin instance of iID if they share the same receiver and Φ_origin(iID) = Φ_origin(iID'). This predicate helps define which attacks are unavoidable. For instance, if an adversary can obtain the receiver's identity public key and the receiver's state containing the secret of a used one-time prekey bundle, they can trivially derive the session key, making this an "unavoidable attack" for the sender.
• Partner (Definition 5): Two instances iID and iID' are partners if they agree on the sender, receiver, roles, and crucially, derive the same session key. This definition inherently captures unknown key share attacks, where parties might derive the same key but disagree on the peer's identity.

The model also defines Match Soundness (Definition 6), a critical property ensuring the consistency of the Origin and Partner predicates. It demands that if two instances are partners, one must be an origin of the other, and that partners (for a given instance) are unique. For last-resort prekeys, it allows multiple sender instances to originate from the same base receiver instance but differentiates completed receiver instances associated with each use. This Match predicate is instrumental in explicitly capturing and preventing attacks like KEM re-encapsulation (which would violate uniqueness of partners) and replay attacks (which would create multiple partner instances for a single use of a last-resort prekey).

The paper then defines the predicate safeBAKE (Definition 8), which outlines the minimal set of unavoidable attacks that no BAKE protocol can prevent (Table 1). These include:

• Attack 1 & 2: Adversary reveals the session key of the tested instance or its partner.
• Attack 3 & 4: Adversary reveals the receiver's identity secret key and user state for a one-time or last-resort prekey bundle before it's used by the receiver, allowing key computation.
• Attack 5: Adversary compromises the peer's identity secret key before the session key is computed, allowing impersonation.

For X3DH and PQXDH, additional unavoidable attacks are identified (Table 3), reflecting their documented weaknesses:

• Attacks 6 & 7 (PQXDH-specific): If a HNDL adversary (classical A1, quantum A2) can reveal the receiver’s state containing a PQKEM prekey, all post-quantum security is lost.
• Attack 8-1 (Weak Forward Secrecy for Sender): An adversary can reveal the receiver's identity secret key after the session key is computed and, by tampering with the unsigned ephemeral key, impersonate the sender.
• Attack 8-2 (User-State Compromise Impersonation for Receiver): If the receiver’s user state is revealed before the session key is computed, an adversary can impersonate any user to the receiver.

RingXKEM (Algorithms 7-9), the proposed fully post-quantum protocol, leverages KEM, Merkle trees, and ring signatures. Its identity key consists of a KEM public key ek and a ring signature verification key rvk. Prekey bundles contain a KEM public key c_ek_u,t and a Merkle tree path path_u,t that authenticates c_ek_u,t against a signed Merkle root. The Merkle tree optimization is a key feature: instead of signing each of the L+1 KEM public keys individually (which would be costly with large post-quantum signatures), RingXKEM constructs a Merkle tree from all KEM public keys and signs only the root. This reduces server storage and upload costs significantly, requiring only a single 630-byte signature (for Gandalf ring signature) instead of L+1 signatures. The sender downloads the c_ek_r and its path_r and verifies it against the signed root_r. The session key is derived from two KEM encapsulations, one with the receiver's identity KEM key and one with the prekey KEM key. A ring signature σ is generated by the sender over public information and encrypted using an SKE key derived from the session keys, providing deniability. The receiver decrypts and verifies this signature. This construction, by sharing state (the Merkle tree root and its signature) across multiple prekey bundles, exemplifies the type of protocol that prior models struggled to capture.

Demo / Proof of Concept

As this submission is a peer-reviewed conference paper rather than a live presentation, there was no interactive demonstration or proof-of-concept in the traditional sense. Instead, the "demonstration" of this work lies in its rigorous formal proofs and detailed comparative analysis, which showcase the utility and power of the Bundled Authenticated Key Exchange (BAKE) model.

The authors formally prove the match soundness and key indistinguishability of X3DH, PQXDH, and their novel RingXKEM protocol within the BAKE framework. These proofs serve as concrete evidence of the model's ability to precisely define and differentiate security properties, including the subtle nuances of harvest-now-decrypt-later (HNDL) security and the impact of various state compromise scenarios. The comparative tables (Table 5 for security, Table 7 for efficiency) further illustrate the practical implications of their theoretical work, providing quantitative assessments of bandwidth, storage, and computational requirements for different instantiations. This analytical depth effectively demonstrates the advantages of the BAKE model for future protocol design and evaluation.

Defensive Implications

The research presented in this paper offers several crucial implications for developers, implementers, and users of secure messaging protocols, particularly those based on Signal.

1. Adopt the BAKE Model for Future Protocol Design and Analysis: The Bundled Authenticated Key Exchange (BAKE) model provides a robust, unified, and concrete framework for analyzing Signal-like handshake protocols. Developers designing new secure messaging handshakes or extending existing ones should consider adopting this model to ensure comprehensive security analyses, especially when dealing with prekey bundles, last-resort prekey bundles, and shared state management. This will lead to clearer security guarantees and easier comparison between different protocol designs.

1. Enhance Key Separation and Modularity within Signal: The paper highlights that Signal's current implementation intertwines the handshake with the Double Ratchet protocol and lacks clear key separation. Signal developers are already considering suggestions to improve this, such as introducing confirmation tags and better separation of key derivation. Implementing these changes would make the handshake a more modular component, simplifying analysis and potentially preventing issues like KEM re-encapsulation attacks without relying on non-standard KEM assumptions.

1. Address Downgrade Resilience in PQXDH: The analysis reveals that PQXDH, in its "compatibility mode" with X3DH, is vulnerable to downgrade attacks if the client doesn't enforce the usage of KEM prekeys. A malicious server or network attacker could omit post-quantum KEM prekeys, forcing a classically secure session without the user's knowledge. While challenging without sacrificing backward compatibility, implementers should explore mechanisms to authenticate protocol version and supported algorithms to prevent such silent downgrades, similar to how TLS 1.3 handles negotiation.

1. Recognize and Mitigate Documented Weaknesses in X3DH and PQXDH: Users and organizations relying on Signal should be aware of the formally proven weaknesses in X3DH and PQXDH:

• Weak Forward Secrecy for Senders: Senders in X3DH/PQXDH only achieve weak forward secrecy. While a receiver's identity key compromise after a session is established does not compromise past messages for the receiver, it allows impersonation of the sender.
• Receiver User-State Compromise Impersonation: If a receiver's user state is compromised before a session key is computed, an adversary can impersonate any user to that receiver. Signal users, particularly those with high-risk profiles, should be diligent about device security and regular rotation of identity keys or prekey bundles to mitigate the impact of such compromises.

1. Advocate for and Adopt Fully Post-Quantum Authentication: While PQXDH offers HNDL security for confidentiality, its authentication remains classically secure. The introduction of RingXKEM demonstrates the feasibility of a fully post-quantum Signal handshake, including post-quantum authentication using ring signatures. As the threat of quantum computers becomes more imminent, the industry should prioritize the transition to protocols that offer comprehensive post-quantum security for both confidentiality and authentication.

1. Implement Robust Replay Protection for Last-Resort Prekey Bundles: The BAKE model explicitly captures replay attacks that can occur with last-resort prekey bundles if not properly handled. While Signal implements countermeasures, the formal modeling emphasizes the importance of robust mechanisms (like tracking used handshake messages in D_ρ_⊥) to prevent an adversary from forcing a receiver to derive the same session key multiple times, which would violate match soundness.

Key Takeaways

• The Bundled Authenticated Key Exchange (BAKE) model is a novel, unified framework providing a concrete and rigorous approach to analyzing Signal-like handshake protocols, particularly for modeling prekey bundles and their states.
• Existing Signal protocols, X3DH and PQXDH, do not achieve "optimal security" in the BAKE model, exhibiting documented weaknesses such as weak forward secrecy for senders and susceptibility to receiver user-state compromise impersonation.
• PQXDH offers harvest-now-decrypt-later (HNDL) confidentiality against quantum adversaries but its authentication remains classical, and its HNDL security is contingent on KEM prekeys not being revealed to quantum adversaries.
• RingXKEM is a new, fully post-quantum Signal handshake protocol proposed in this work that achieves optimal security in the BAKE model against fully quantum adversaries, leveraging post-quantum KEM and ring signatures.
• RingXKEM introduces an efficient Merkle tree optimization for prekey bundle storage, allowing for shared state across bundles—a feature that previous tailored models could not adequately capture.
• The BAKE model's explicit treatment of authentication effectively captures and helps prevent critical attacks like KEM re-encapsulation and replay attacks, which were often overlooked or implicitly handled by prior game-based security models.

About the Speaker(s)

The research paper "Bundled Authenticated Key Exchange: A Concrete Treatment of Signal's Handshake Protocol and Post-Quantum Security" was authored by a collaborative team of cryptographers. Keitaro Hashimoto is affiliated with the National Institute of Advanced Industrial Science and Technology (AIST). Shuichi Katsumata holds positions at both AIST and PQShield, a company focused on post-quantum cryptography. Thom Wiggers is also associated with PQShield. Their collective expertise lies at the intersection of applied cryptography, formal security analysis, and the development of post-quantum cryptographic solutions for real-world protocols. Their work, as evidenced by this paper, focuses on rigorously defining and proving the security of complex cryptographic systems like the Signal protocol, with a keen eye towards practical implementation and the challenges posed by emerging quantum computing threats.