All posts
cryptography post-quantum ML-KEM

Why We Chose ML-KEM-768 for Post-Quantum Key Exchange

A deep dive into our decision to use NIST's ML-KEM-768 standard and what it means for the security of your calls.

SpeakEasy Security Team ·

In August 2024, NIST finalized three post-quantum cryptographic standards: FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA). When we designed SpeakEasy’s cryptographic stack, we had to make a deliberate choice about which algorithms to use, which security levels to target, and how to compose them correctly. This post explains our reasoning.

The Problem with Classical Key Exchange

Every encrypted call on the internet today depends on key exchange algorithms — typically ECDH over Curve25519 or P-256. These algorithms are computationally secure against classical computers. Against a sufficiently powerful quantum computer running Shor’s algorithm, they are not.

This isn’t a distant theoretical concern. Adversaries with the resources to record large volumes of encrypted traffic are doing so today, betting that quantum computers capable of breaking today’s key exchange will arrive within the next decade or two. The “harvest now, decrypt later” (HNDL) threat means that the security of your calls today determines whether those calls remain private in 2035.

Why ML-KEM Specifically

ML-KEM (Module Lattice Key Encapsulation Mechanism) is NIST’s standardized key encapsulation mechanism based on the CRYSTALS-Kyber algorithm. We chose it for several reasons:

Hardness assumption. ML-KEM’s security is based on the Module Learning With Errors (MLWE) problem. The best known classical and quantum attacks against MLWE require exponential time. This is substantially different from the polynomial-time quantum attacks against classical discrete logarithm and integer factorization problems.

Performance. Lattice-based schemes are fast. ML-KEM-768 key generation, encapsulation, and decapsulation each complete in well under a millisecond on modern hardware. The performance overhead compared to X25519 is negligible in the context of a call setup.

Conservative security level. ML-KEM comes in three variants targeting different security levels:

  • ML-KEM-512: NIST Level 1 (roughly equivalent to AES-128)
  • ML-KEM-768: NIST Level 3 (roughly equivalent to AES-192)
  • ML-KEM-1024: NIST Level 5 (roughly equivalent to AES-256)

We chose ML-KEM-768 as the right balance between security margin and practical key/ciphertext sizes. Level 3 provides substantial security against all currently known attacks while keeping the public key at 1184 bytes and the ciphertext at 1088 bytes — manageable for real-time communication.

NIST standardization. ML-KEM is FIPS 203. Using a NIST-standardized algorithm means that our cryptographic choices can be verified by third parties against a published specification, that future audits have a clear baseline, and that we benefit from the extensive public analysis the candidates received during the multi-year standardization process.

How We Use ML-KEM-768

ML-KEM is a key encapsulation mechanism, not a key agreement protocol. It works like this:

  1. The recipient generates an ML-KEM-768 key pair and publishes the public key.
  2. The initiator runs Encaps(public_key) which produces a ciphertext and a shared secret.
  3. The initiator sends the ciphertext to the recipient.
  4. The recipient runs Decaps(secret_key, ciphertext) to recover the same shared secret.

The shared secret is then used as input to HKDF-SHA-256 to derive session keys, binding the ML-KEM output to both parties’ long-term identity keys authenticated via ML-DSA-65.

This is not used in isolation. We compose ML-KEM-768 with X25519 in a hybrid construction: the final session key is derived from both the classical X25519 shared secret and the ML-KEM-768 shared secret. This means the construction is as strong as the stronger of the two underlying primitives — if ML-KEM is somehow broken, X25519 still provides classical security. If X25519 is broken by a quantum adversary, ML-KEM still provides post-quantum security.

The Double Ratchet on Top

Key exchange only protects the session establishment. Once the session is established, we need forward secrecy and break-in recovery for the actual message flow. This is what the Double Ratchet algorithm provides.

The standard Signal Double Ratchet uses Diffie-Hellman ratchet steps for forward secrecy. We replace the DH ratchet with KEM-based ratchet steps using ML-KEM-768, giving the entire session forward secrecy and break-in recovery properties under the post-quantum threat model.

The result: even if an adversary records every encrypted packet you send today and later obtains a quantum computer capable of breaking ML-KEM-768, they cannot retroactively decrypt your call audio or message history. Each ratchet step generates a fresh shared secret, and old secrets are deleted from memory once they are no longer needed.

Authentication: ML-DSA-65

Key encapsulation handles confidentiality. Authentication — ensuring you’re actually talking to the person you think you are — is handled by ML-DSA-65 (FIPS 205), a digital signature algorithm based on the CRYSTALS-Dilithium candidate.

Long-term identity keys are ML-DSA-65 key pairs. When two SpeakEasy users establish a session, each party signs their ephemeral KEM public key with their long-term identity key. This prevents man-in-the-middle attacks, provided you have authenticated the other party’s identity key through some out-of-band mechanism.

That out-of-band authentication is what safety numbers are for. SpeakEasy derives a human-readable fingerprint from both parties’ identity keys. If both parties’ safety numbers match when read aloud or compared visually, no one is in the middle.

What We Don’t Do

We do not use any hybrid classical/post-quantum schemes where the classical and post-quantum components’ secrets are XOR’d together. Combining secrets via XOR is fragile; we use HKDF to combine them properly.

We do not use SIDH/SIKE or any isogeny-based scheme. SIKE was completely broken in 2022 with a classical polynomial-time attack, reinforcing that algorithm selection and ongoing analysis matter.

We do not roll our own cryptographic primitives. Every algorithm we use is a NIST-standardized scheme or an established protocol (AES-GCM, HKDF, Double Ratchet) with decades of analysis behind it.

Ongoing Review

Post-quantum cryptography is a young field. The algorithms we use today are the best available standardized options, but cryptographic analysis continues. We will track developments in the research community and update our cryptographic stack if warranted by new cryptanalytic results.

Our cryptographic library is open source. We encourage independent review.