Paper 2024/702

Security Analysis of Signal's PQXDH Handshake

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.0 – August 2024: – added post-quantum(-only) analysis (Section 5.2) via separate clean predicates (Figure 9) and theorem statement (Theorem 5.2) for quantum adversaries – discuss key confusion between DH and KEM keys as well as ephemeral and semi-static KEM keys in Sections 1 and 4.3 and incorporate them into Theorems 5.1 and 5.2 – define and use hash functions with the "human ignorance" approach [Rog06] (cp. Definitions 2.4 and 2.5, Theorems 3.6 to 3.11) – rename the adversarial model LEAK^ for the KEM binding notion to LEAK^{ r}