This post is the second in the series covering the technical decisions surrounding post-quantum cryptography. The first article in the series covered post-quantum signature sizes. You don't have to read the first article to enjoy this one.
This week, IETF officially released the last RFC needed to fully standardise post-quantum key establishment in TLS, so it's very appropriate that we take a closer look at key establishment for the next installment.
This aspect of the migration is both simpler and more complicated at the same time. In a nutshell, the threat against key establishment is immediate, and there is a strong urgency to address it. The technical challenge is simpler and the design came together with relatively little drama. That's the simpler part. For the more complicated side, the NSA chose a path that's in contrast with the mainstream technical community and created a rift at the IETF that persists. Read on to find out more.
The threat of "Harvest Now, Decrypt Later"
Cryptographic protocols consist of many moving parts, but, generally speaking, they have to deal with three key aspects: authentication, key establishment, and encryption. Algorithms that run on quantum computers don't pose the same threat for all of these three. For example, against authentication, the threat materialises only when authentication is needed. In TLS, for example, authentication is ephemeral, so we're not in immediate danger. We won't be until quantum computers become a practical reality.
Quantum computers largely won't impact encryption, but key establishment is under attack today, long before we even have a working [cryptographically-relevant] quantum computer. That's because a capable adversary can collect encrypted traffic today, keep it around, only to break it later, when they obtain access to a quantum computer. This threat is better known as "harvest now, decrypt later", or HNDL.
Given this asymmetry in the threats, it's not surprising that the work first started on finding a new approach to key establishment. In fact, Google announced their first experiment almost exactly 10 years ago. That was roughly around the time NIST started to plan their post-quantum cryptography competition.
Ten years later, hybrid key establishment dominates
Today, all modern browsers support a hybrid key establishment approach that combines traditional cryptography (based on elliptic curves) with ML-KEM, the algorithm that NIST selected as their first for this purpose. There are three flavours in play, called X25519MLKEM768, SecP256r1MLKEM768, and SecP384r1MLKEM1024. The construction is the same in all three cases, with the main differences being the selected elliptic curve parameters and security levels.
At the technical level, this new key establishment consists of the following layers:
- Elliptic curve Diffie-Hellman (ECDH), part of the TLS 1.3 specification from the beginning
- ML-KEM, standardised by NIST in 2024 (but announced as winner in 2022)
- RFC 9954: Hybrid Exchange in TLS 1.3
- RFC 10024: Post-Quantum Traditional Hybrid Key Agreement Mechanisms for TLS 1.3
Why so many moving parts? Well, in the beginning we only had ECDH. We then had to invent ML-KEM to deal with the quantum computer threat. Because ML-KEM is fairly new and not as well established, and because EC cryptography is so small and fast, it was decided that a hybrid approach would provide best security. Unfortunately, TLS had no way to use hybrid key establishment, so RFC 9954 had to be designed. Finally, RFC 10024 had to be produced to tie it all together.
Also notice how both RFCs explicitly say "for TLS 1.3". The IETF is trying its best to tell us that these works don't apply to earlier protocols. In fact, TLS 1.2 is in feature freeze (RFC 9851), and new documents are being written to deprecate what can be deprecated (RFC 10015).
According to Cloudflare, who have a dashboard that tracks what they see from post-quantum cryptography, about 71% of human traffic arriving to their CDN uses hybrid key establishment and is thus protected from quantum computer threats.
That's the headline number, but if you scroll down, you'll see that only about 11% of the origin servers have the same protection. Despite 10 years of work, we're not even close to widespread support of quantum-resilient key establishment server-side. That first number (71%) sounds great, but that capable adversary you're worried about, they'll attack where you're weak, not where you're strong.
It was more work than I made it sound
You might think that we sorted out key establishment quickly, but it only looks that way from a distance. As mentioned already, Google started a long time ago. That first experiment, which started in July 2016, ended in November the same year. It was established that the approach was feasible.
The second experiment commenced in late 2019, as a collaboration between Cloudflare and Google. This one used the same hybrid approach with two other algorithms, NTRU-HRSS and SIKE. Notably, three years later, SIKE ended up being broken. And that reinforced the idea of the hybrids.
After NIST's selection of ML-KEM, the focus was on using it in hybrid constructions. It started to find its way into the libraries, and the browser vendor added support for it. Cloudflare enabled in October 2022, using the X25519Kyber512Draft00 and X25519Kyber768Draft00 "work in progress" algorithms. It took another two years for ML-KEM to be standardised, and everyone later switched to X25519MLKEM768 and friends.
Impact of ML-KEM on TLS handshake performance
In the previous installment, I spent the entire article discussing the significant increases in post-quantum signature sizes. In practice, the transition to hybrid key establishment already increased the size of the TLS handshake, by about 1,100 bytes each way.
In 2024, Google reported a median 4% increase in handshake latency due to this change. AWS reported a small increase in the handshake time in a controlled environment, due to increased computation requirements. The main conclusion is that the increase in latency is driven by the need to transfer more data to complete the TLS handshake, and that was for only about 1kb. The signature increase is going to add more than 10x that.
NSA doesn't like hybrid cryptography
The migration of the key establishment algorithms seems like a success story, but there is a small bump on the road, stemming from the fact that the US National Security Agency (the all-mighty NSA) doesn't like hybrid cryptography.
In September 2022, the NSA launched their Commercial National Algorithm Suite 2.0 (new name; the previous name was NSA Suite B). On its own, this was a great move, as it established a migration timeline early and provided clarity for which algorithms should be used. Unfortunately, their requirements for key establishment go against the world.
In the technical community, most people [my impression, not a scientific measurement] prefer a hybrid approach for the extra safety it provides. The feeling is that we need more time to accept the new post-quantum algorithms and test them further for safety. Cryptographers, by nature, are very conservative. To illustrate this point, this week saw two interesting research papers, one possibly denting the security of lattice problems and the other of Classic McEliece. Nothing broken just yet, but we love to say how the attacks only get better.
The division in the community is the most visible in the IETF's TLS Working Group, as anyone following the mailing list will tell you. The point of contention is this: should the IETF publish an informational RFC documenting pure ML-KEM key establishment? On one side we have people who say that, because of the NSA's requirements, this algorithm will be used, and we all need to work off the same specification. On the other side, we have people who're saying that we've already deployed the hybrid approach with success, why give legitimacy to a less safe approach?
To clarify, the current direction is not only to mark this work informational (so not a standard), but also to mark it as not recommended. But that wasn't enough to avoid endless conversations on the list. This document (draft-ietf-tls-mlkem-09) is currently in Last Call. It's also already implemented in some browsers, prioritised behind the hybrids but there to be used with servers that prefer the pure ML-KEM approach.
Ivan Ristic is the Chief Scientist for Red Sift and former founder of Hardenize. Learn more about how Red Sift helps organizations with their Certificate Monitoring.