Also mentioned
ML-KEMML-KEMModule-Lattice-based Key Encapsulation MechanismModule-Lattice-Based Key-Encapsulation Mechanism, the NIST-standardized post-quantum KEM derived from CRYSTALS-Kyber and specified in FIPS 203.Read the full entry (new tab), FIPSFIPSFederal Information Processing StandardFederal Information Processing Standards, publicly announced standards developed by NIST for use in U.S. government computer systems, including cryptographic algorithms and modules.Read the full entry (new tab), NISTNISTNational Institute of Standards and TechnologyThe U.S. National Institute of Standards and Technology, the agency that develops and publishes cryptographic standards, including the FIPS series and post-quantum algorithms.Read the full entry (new tab) are defined in the glossary.
The finding
Post-quantum prekeys were issued one-shot, but the server had no mechanism to retire them after use. The same ML-KEM encapsulation could be replayed, defeating forward secrecy. The fix is the same discipline as classical one-time prekeys: atomically consume on use.
Adding post-quantum protection to a messaging protocol is rarely a single change. Identity keys, signed prekeys, one-time prekeys, the initial root-key derivation, the message ratchet, group key derivation, backups, multi-device sync. Each is a place where asymmetric primitives live, and each is its own migration decision.
What we found
In this audit engagement, the team had correctly added an ML-KEM encapsulation against a post-quantum prekey. But the prekey was treated as reusable: the server returned it, and returned it again, without removing it from the pool when it was consumed.
Why it matters
There are two distinct failures here, and it is worth keeping them apart. First, replay: an attacker who can serve the same one-time prekey twice lets Bob accept a duplicated initial message, the X3DH §4.2 replay concern, which is exactly why one-time prekeys exist and must be consumed on use. Second, forward secrecy: because the prekey is never retired, its private key stays live on the server, so a later compromise of that key can recover the shared secret of every past session that used it (X3DH §4.6). The bug is the missing retirement; the two consequences follow from it.
The fix is not novel: it is the discipline X3DH already specifies. One-time prekeys, classical or post-quantum, must be consumed atomically: the server hands one out for a session and deletes it in the same step, and never serves it twice; the private key is destroyed on use so it cannot decrypt anything later. Note this applies to ONE-TIME prekeys. Signed prekeys are reused by design and rotated, which is exactly why they carry weaker replay/forward-secrecy guarantees.
The last-resort prekey is a deliberate trade-off, not a bug
Signal's deployed PQXDH keeps a reusable "last-resort" signed post-quantum prekey for when the one-time pool is exhausted, accepting exactly the degraded replay/forward-secrecy properties described above, and the spec is explicit that a compromise of that key would compromise earlier session secrets. Distinguish a missing retirement mechanism (the bug) from a documented last-resort fallback (a designed trade-off).
Ignoring the prekey distribution channel
ML-KEM-768 prekeys are 1184 bytes each (and, in PQXDH, signed), so a pool that previously distributed 100 classical prekeys per user now moves well over 100 KB per user. Plan the distribution channel: bandwidth, pool sizing, and battery on mobile clients that fetch and verify them. The same constant overhead turns up wherever a post-quantum ciphertext rides a small message, and we measured it in a Nostr client.
References
- Signal: X3DH Key Agreement Protocol (§3.3 delete-on-use, §4.2 replay, §4.6 forward secrecy) and PQXDH (signed one-time + last-resort PQ prekeys).
- Analysis: Security Analysis of Signal's PQXDH Handshake (IACR eprint 2024/702), and the Signal blog on PQXDH.
- NIST: FIPS 203 / ML-KEM: Table 3 for the 1184-byte prekey figure.
- Wikipedia: Signal Protocol, Forward secrecy, Replay attack.