Hybrid ML-KEM costs bytes, not CPU: X25519 vs. ML-KEM key exchange benchmark

This project benchmarks classical ECDH (X25519), post-quantum ML-KEM (FIPS 203 / Kyber), hybrid X25519+ML-KEM, and ML-DSA-signed ML-KEM key exchange. Each mode runs as a real handshake over TCP sockets, built on liboqs and Python's cryptography library.

NIST recently finalized the first post-quantum cryptography standards (FIPS 203/204/205), and the urgency behind that isn't really about quantum computers existing today. It's "harvest now, decrypt later": an adversary can record encrypted traffic now and decrypt it retroactively once a cryptographically relevant quantum computer exists. For data with a long confidentiality shelf life, medical records, infrastructure credentials, state secrets, that threat is already live regardless of when the hardware actually shows up.

That's why most organizations are moving to hybrid key exchange (classical plus PQC combined) rather than jumping straight to pure PQC. You need both primitives broken to lose confidentiality, which is a meaningfully higher bar. Chrome/BoringSSL and OpenSSH already ship hybrid X25519+ML-KEM by default.

What I wanted to actually measure was what that migration costs, in handshake latency and bytes on the wire. And once key exchange is covered, what does the other half of a real handshake cost, actually proving you're talking to the server you think you are?

This project started after reading Rios et al., "Toward the Quantum-Safe Web: Benchmarking Post-Quantum TLS" (IEEE Network, 2025), which benchmarks full TLS 1.3 handshakes across NIST PQC standards using OpenSSL/liboqs/oqs-provider in Docker. This got even more interesting once I started interning on Wells Fargo's cybersecurity team, where I saw up close how a large financial institution is actually approaching the move to post-quantum cryptography.

This isn't a full TLS 1.3 implementation, just a minimal handshake protocol built directly on oqs (for ML-KEM and ML-DSA) and cryptography (for X25519). That keeps the comparison focused on the primitives themselves instead of burying them inside a full TLS stack.

The first three modes only give you confidentiality. Nothing stops a man-in-the-middle from swapping the key material mid-transit, which is the same gap you'd have without TLS certificates. Signed mode closes it: the server signs its ephemeral ML-KEM public key with ML-DSA-65, and the client verifies that signature before trusting the key. This step tends to get left out of KEM-only PQC benchmarks, and it turned out to matter quite a bit once I measured it.

To separate cryptographic compute cost from network cost, every socket gets wrapped in a DelayedSocket that injects configurable one-way latency (0 / 20 / 75 ms), standing in for localhost, same-region, and cross-region-ish conditions.

All charts and raw data live in results/. Each full run covers 60 trials per configuration across 4 modes, 3 ML-KEM security levels, and 3 latency tiers.

At 0ms simulated latency, classical X25519 averages about 0.29ms. ML-KEM alone comes in close behind it, 0.26-0.29ms depending on security level, not meaningfully faster or slower than classical despite being a completely different primitive. Hybrid mode, doing both operations, lands around 0.51-0.59ms, roughly the sum of the two as you'd expect. Adding ML-DSA signing pushes it further, to about 0.71-0.77ms, still under a millisecond, but clearly the most expensive of the four on pure compute.

Classical X25519 is 72 bytes round trip. ML-KEM-768 alone runs about 2,280 bytes, roughly 32x larger. Hybrid X25519+ML-KEM-768 comes to 2,352 bytes, close to the sum of both. Add ML-DSA-65 signing and it jumps to about 7,549 bytes, more than 3x hybrid mode and over 100x classical. Most of that increase is the ML-DSA public key and signature themselves, which run into the kilobytes even at NIST security level 3.

This was the most surprising result. Classical, PQC, and hybrid modes all scale with network latency exactly as expected, one round trip, so total handshake time is about 2x the simulated one-way latency (about 40.5ms at 20ms latency, about 150.8ms at 75ms latency). Signed mode doesn't follow that pattern. At the same latencies, it takes about 81.3ms and 301.5ms respectively, almost exactly double. That points to signed mode requiring two network round trips instead of one, likely because the server sends its ML-DSA public key as a separate message before sending the signed ML-KEM key, rather than bundling both into a single flight.

On a fast local network this barely registers. But on any link with real latency, satellite, cellular edge, cross-region, this means the authentication step doesn't just add a few kilobytes, it doubles the network cost of the whole handshake. That's a much bigger deal for real-world deployment planning than the byte overhead alone suggests.

At 0ms simulated latency, classical X25519 averages around 0.29ms. ML-KEM alone comes in close behind it, 0.26-0.29ms depending on security level, not meaningfully faster or slower than classical despite being a completely different kind of primitive. Hybrid mode, doing both operations, lands around 0.51-0.59ms, roughly the sum of the two. Adding ML-DSA signing pushes it further, to around 0.71-0.77ms, still well under a millisecond, but clearly the most expensive of the four on pure compute.

Classical X25519 is 72 bytes round trip. ML-KEM-768 alone runs about 2,280 bytes, roughly 32x larger. Hybrid X25519+ML-KEM-768 comes to 2,352 bytes, close to the sum of both. Add ML-DSA-65 signing and it jumps to about 7,549 bytes, more than 3x hybrid mode and well over 100x classical. Most of that increase is the ML-DSA public key and signature themselves, which run into the kilobytes even at NIST security level 3.

Classical, PQC, and hybrid all scale with network latency the way you'd expect for a single round trip, about 40.5ms total at 20ms simulated latency, about 150.8ms at 75ms. Signed mode breaks that pattern: at the same latencies it takes about 81.3ms and 301.5ms, almost exactly double. That points to signed mode needing two network round trips instead of one, most likely because the server sends its ML-DSA public key as a separate message before sending the signed ML-KEM key, rather than bundling both into a single flight.

At 0ms latency this barely shows up. But on any link with real latency, satellite, cellular edge, cross-region, this means the authentication step doesn't just add kilobytes, it doubles the network cost of the whole handshake. That's a bigger deal for real-world deployment planning than the byte overhead alone would suggest.

On typical internet-facing services, hybrid PQC's wire overhead alone probably isn't your bottleneck. Network RTT and TLS record processing will dwarf it, which lines up with what Cloudflare and Google have reported from real hybrid PQC rollouts at scale.

Hybrid, not pure PQC, is still the right default for the key exchange side of a migration. The cost gap between pure ML-KEM and hybrid is small enough not to matter much.

Authentication is where the real migration cost shows up, and it's worse than a byte-count comparison suggests. Swapping ECDSA or RSA certificates for ML-DSA isn't just a multi-kilobyte tax, in this implementation it costs an entire extra network round trip. On high-latency links that matters more than the raw byte overhead does. Worth investigating whether the ML-DSA public key and signature could be bundled into the same message flight as the ML-KEM key instead of sent separately, since that round trip may not be structurally necessary.

Getting it running

There's one real gotcha here worth calling out up front: oqs, the Python bindings for liboqs, needs the underlying C liboqs library actually built and available on your system. Installing the Python package alone doesn't give you that, it just installs the wrapper. Skip this step and the first time you try to import oqs, you'll hit RuntimeError: No oqs shared libraries found.

git clone https://github.com/RayDCodes/pqc-migration-bench.git cd pqc-migration-bench

Set up a virtual environment:

python3 -m venv venv source venv/bin/activate # Windows: venv\Scripts\Activate.ps1 pip install -r requirements.txt

Install the liboqs Python bindings along with the native library. On Linux, including WSL and GitHub Codespaces, this usually just works as long as you have a build toolchain installed:

sudo apt install build-essential cmake ninja-build -y pip install git+https://github.com/open-quantum-safe/liboqs-python.git

On native Windows, this same command tends to fail since there's no C build toolchain by default, and even installing Visual Studio Build Tools plus CMake doesn't always get you a clean build. If you run into this, the path of least resistance is developing inside WSL or a GitHub Codespace instead of fighting the native Windows build, which is what I ended up doing.

python -c "import oqs; print(oqs.get_enabled_sig_mechanisms())"

You're looking for ML-DSA-65 somewhere in that list.

cd src python bench.py --quick --out ../results/smoke_test.csv

This runs a small, fast subset (10 trials, 2 latency tiers, one mechanism) just to confirm everything's wired up correctly.

python bench.py --out ../results/handshake_results.csv

This covers all 4 modes across 3 ML-KEM security levels and 3 latency tiers at 60 trials each, and takes a few minutes to finish.