A closer look at the performance of ML-KEM

This blog post is a part of a series where I discuss the post-quantum migration from an engineering perspective. Our mission is to understand what problems need addressing, and how and why certain decisions are being made. Ultimately, we need to understand. The first two posts covered the challenges related to the increased signature sizes and new key establishment methods. In the third, we examined the network and TLS protocol layers to uncover what aspects influence the performance and how those will be affected by the migration.

In this fourth post, we look at the new key establishment options that involve ML-KEM to understand how they perform in practice. This is the part of the post-quantum migration that has already been implemented, at least in the TLS protocol. The decisions have been made, so let's see how they've impacted the performance on the wire.

Before we embarked on the post-quantum migration, TLS 1.3 provided two options for key establishment, both based on the Diffie-Hellman algorithm; one classic and the other the elliptic curve variant. We usually refer to these as DHE and ECHDE. (The last "E" in the abbreviation stands for ephemeral. That's a good thing, because it provides forward secrecy.) ECHDE was and is the dominant option, due to its better security properties at smaller key sizes, better performance, and smaller storage requirements on the wire.

With the post-quantum migration, TLS switched to hybrid key establishment, which combines ECDHE with the ML-KEM standard adopted by NIST. Because this is a hybrid, every TLS handshake carries information about two algorithms; we're literally doing everything twice. How has that impacted the protocol?

To find out, I dusted off an old tool of mine (forked off an earlier work by Vincent Bernat) I'd used before for this type of measurement. I ported it to run on OpenSSL 3.5.5, which ships with Ubuntu 26.04 LTS. This version of OpenSSL [or thereabouts] currently ships on the latest LTS operating systems.

My tool is designed to measure the CPU and network transport requirements of various cipher suites, key exchange algorithms, and protocols. In this instance, I chose to test four options:

• ECDSA-256 key coupled with ECDHE-X25519 – the baseline, a modern and fast option.
• RSA-2048 key coupled with ECDHE-X25519 – slightly slower on account of RSA.
• ECDSA-256 key coupled with X25519MLKEM768 – the new PQC hybrid option.
• ECDSA-256 key coupled with ML-KEM-1024 – the new PQC non-hybrid option.

We can only test TLS 1.3, because TLS 1.2 and earlier won't be fixed for post-quantum cryptography.

Measurement is done on the same computer by running one full client and one full server, both in the same process but on separate threads. We measure the CPU consumption and monitor the size of each handshake. Each run performed 2,000 handshakes and was then repeated 3-5 times for the numbers to stabilise. Do note that the CPU measurements are CPU time, which is sufficient for our needs to understand how one key establishment compares to another, but they're otherwise not comparable to any measurements taken elsewhere.

First, let's take a look at the CPU usage during key establishment.

We can see immediately why, currently, ECDSA is the preferred key algorithm over RSA. With the latter option, the server has to do 2.5x more work during every handshake. There's also a significant asymmetry in the CPU time spent in the client and the server: servers do 3x more work overall.

I included RSA for contrast but, for our purposes, we can exclude that measurement and focus on the remaining three, which all use ECDSA. The verdict? We see that there aren't significant differences in CPU time no matter which key establishment is used. That's because ML-KEM is very fast. Although there are non-trivial relative increases, in absolute terms the differences are minor.

Next, let's examine the amount of data going back and forth between client and server.

Here, we see significant differences. Comparing the two ML-KEM measurements with X25519 as the baseline, we see that X25519MLKEM768 adds 1,176 bytes to the client handshake and 1,088 bytes to the server handshake. Of these two, the server increase (2x) is more significant, because it's taking space in the initial congestion window, which is the bottleneck we will be hitting in practice.

ML-KEM-1024, which is a stronger algorithm, takes even more space. The server side of the handshake increases by 1,537 bytes, or roughly 2.6x larger.

If you recall from my earlier articles, we're using ML-KEM-1024 for the pure ML-KEM measurement because that's the minimum the NSA will accept as part of their Commercial National Security Algorithm (CNSA) 2.0 requirement.

These measurements are not telling the whole story because client and server are both running on the same machine, with only miniscule network latency involved. Even at this level, we can see that pure ML-KEM is slightly worse than other methods; it requires roughly the same CPU, but requires more bytes in the handshake.

In practice, we have to take into account that TLS clients can send a small number of key shares in their initial ClientHello. Today, X25519 and X25519MLKEM768 are being sent, but ML-KEM-1024 isn't. This means that every server that wants the latter option has to respond with a retry request on every single full TLS connection, which adds another round trip to the handshake.

Adding ML-KEM-1024 as the third key share by default is unlikely to make sense, given that most of the world won't use it. For now, servers that need a pure PQC option will have to accept the performance penalty.

This is not likely to be a problem on local networks, where round trips are measured in low single-digit milliseconds, but the performance hit will definitely be noticeable on the public internet. If we knew what key establishments were being supported by a particular server, we could send only one key share, but at this time we don't have technology to distribute this information. A RFC currently in progress ("TLS Key Share Prediction") is exploring using DNS for this purpose, via the SVCB and HTTPS records.