Paper 2024/702

Security Analysis of Signal's PQXDH Handshake

Rune Fiedler, Technische Universität Darmstadt
Felix Günther, IBM Research Europe – Zurich
Abstract

Signal recently deployed a new handshake protocol named PQXDH to protect against "harvest-now-decrypt-later" attacks of a future quantum computer. To this end, PQXDH adds a post-quantum KEM to the Diffie-Hellman combinations of the prior X3DH handshake. In this work, we give a reductionist security analysis of Signal's PQXDH handshake in a game-based security model that captures the targeted "maximum-exposure" security against both classical and quantum adversaries, allowing fine-grained compromise of user's long-term, semi-static, and ephemeral key material. We augment prior such models to capture not only the added KEM component but also the signing of public keys, which prior analyses did not capture but which adds an additional flavor of post-quantum security in PQXDH. We then establish fully parameterized, concrete security bounds for the classical and post-quantum session key security of PQXDH, and discuss how design choices in PQXDH make a KEM binding property necessary and how a lack of domain separation reduces the achievable security. Our discussion of KEM binding and domain separation complements the concurrent tool-based analysis of PQXDH by Bhargavan, Jacomme, Kiefer, and Schmidt (USENIX Security 2024), which pointed out a potential re-encapsulation attack if the KEM shared secret does not bind the public key. In contrast to the tool-based analysis, we analyze all protocol modes of PQXDH and its "maximum-exposure" security. We further show that both Kyber (used in PQXDH) and the NIST standard ML-KEM (expected to replace Kyber) satisfy a novel binding notion we introduce and rely on for our PQXDH analysis, which may be of independent interest.

Note: version 2.1 – May 2025 (corresponding to the PKC 2025 proceedings version): – fix an oversight in the cleansigE predicate (Figure 9) pointed out by Keitaro Hashimoto, Shuichi Katsumata, and Thom Wiggers

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2025
DOI
10.1007/978-3-031-91823-0_5
Keywords
SignalPQXDHkey exchangeKEM bindingpost-quantumhybrid
Contact author(s)
rune fiedler @ cryptoplexity de
mail @ felixguenther info
History
2025-05-07: last of 2 revisions
2024-05-07: received
See all versions
Short URL
https://ia.cr/2024/702
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/702,
      author = {Rune Fiedler and Felix Günther},
      title = {Security Analysis of Signal's {PQXDH} Handshake},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/702},
      year = {2024},
      doi = {10.1007/978-3-031-91823-0_5},
      url = {https://eprint.iacr.org/2024/702}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.