Effect of post-quantum algorithms on networking performance

In the first two posts in this series, I covered two key post-quantum cryptography efforts, one to fix key establishment and the other to fix authentication. Although they are two different problems, they do have something in common, both changes will affect the performance of encrypted networking protocols.

The effects of the key establishment changes are talked about a lot, but Google has observed a small increase in the handshake latency. Doesn't sound like much, but matters at scale. There is a much bigger worry about the size of post-quantum signatures, where the effects could be much worse, depending on what approach we take.

To understand why these things happen, we first need to understand the core encryption principles, and then how TLS uses them to deliver security. In this post, I dive into the details of the TLS handshake, highlighting the key establishment and authentication parts and the effect of the post-quantum changes on this crucial part of encrypted communication.

At a high level, when we talk about encryption, we really want what it can provide, and that's usually described as three aspects: confidentiality, authentication, and integrity. To achieve these properties, we combine cryptographic primitives to design protocols. In any cryptographic protocol, most of the complexity is in the handshake, which does roughly the following:

• Agree on common encryption parameters
• Authenticate, ideally both sides but more commonly just the server
• Agree on the encryption keys (key establishment)
• Validate the integrity of the handshake to ensure no tampering

There's a lot going on there. Popular protocols also have to solve interoperability, which is the art of getting hundreds of tools and products built by different manufacturers to talk to one another, despite often being poorly implemented, old, and often obsolete.

The actual encryption part is almost boring in comparison with the handshake, especially these days, when so-called authenticated encryption is the norm. You essentially say what encryption algorithm you want to use and with what key, feed it some input data, then you get some data out. To prevent attacks such as data replay, reordering, and deletion, all encrypted data packets form an immutable chain and share common and continuous integrity checking.

We've already established the complexity involved with cryptographic protocols. In TLS, a handshake consists of several flights. Within each flight, a bunch of protocol messages are sent from one side to the other, essentially at the same time. Here's a simple outline (there's a more detailed diagram in the RFC, if you're interested):

1. Client starts the handshake by sending a ClientHello message.
2. Server accepts the connection, switches to encryption, sends its certificate, proves it holds the corresponding private key, and then completes the handshake.
3. Client validates the server data and completes the handshake on its end. It then proceeds to send application data (e.g., HTTP).
4. Server completes the handshake on its end, then responds to the application data.

When we look at the handshake from the network perspective, we see that each flight consists of one or more network packets, depending on how much data needs to be sent. Because it takes time for the packets to reach the other end, and for the response to arrive, there is also a fair amount of waiting in between the flights. A full TLS handshake requires two round trips between client and server. We'll come to this again later.

Every handshake involves the following:

• Cryptographic operations on the CPU
• Construction of protocol messages
• Pushing bytes onto the network
• Waiting to hear from the other side
• Processing the received packets

If you need more information, head to the recently refreshed TLS 1.3 RFC 9846. After that, fire up Wireshark and observe the real handshakes as carried out by browsers and other tools.

We pay for cryptography with increased CPU processing and network latency. To address the former, we need to buy more CPUs. As for the latter, network latency slows our websites down, and translates to less revenue.

Let's look at these two in more detail:

• CPU: In the early days of cryptography, CPUs were much slower than today and represented a significant bottleneck. Back then, it was common to encrypt only parts of the traffic. Fortunately, things are now much better, and we can encrypt everything. Although cryptography has a measurable cost, it's not large compared to the benefits.
• Latency: The real cost of doing cryptography is in the incurred additional round trips. To perform a TCP handshake, we need one round trip. We send a request, which travels across the network, then we wait for the response to travel back. To perform a TLS handshake on top of an open TCP connection, we need two further round trips. Thus, if you're starting a new connection from London to New York, you can't do it without 3x90=270ms of just waiting for your packets to move back and forth. QUIC, which builds on top of UDP, can open a connection in less time, only 180ms.

When it comes to post-quantum cryptography, which, in the context of TLS, currently means ML-KEM (for key establishment) and ML-DSA (authentication), the differences in the CPU requirements are not meaningfully different.

It's a completely different story with network latency, and it's what has the potential to negatively affect performance by forcing conditions that increase the number of required round trips during the initial handshake phase. This can happen via one of two mechanisms:

• Key share assumptions: In TLS 1.3, clients have to "guess" what key shares might be supported by a server. Historically, all TLS 1.3 servers had support for X25519, so that's what everybody had been sending. Today, modern clients send X25519 as well as X25519MLKEM768 and that works most of the time. When it doesn't, the server has to request a retry of the ClientHello, which is done with a HelloRetryRequest message. This message contains the information about what key establishment methods are supported by the server. If the server supports a matching algorithm, it can try again, but this process adds another round trip.
• Slow start: At the start of a new connection, network conditions are not known, and protocols typically start slow, increasing speed as more and more packets are exchanged. This approach is usually called Slow Start in TCP, and there are equivalents in other protocols (e.g., QUIC). The amount of data that can be initially sent is called the initial congestion window. The default for servers today is about 14.5 KB, although CDNs may allow bigger values, for example 30-45KB. The bottom line is that, once you send all the data you're allowed to send, you have to wait for a response, which adds another round trip.

So, it's dealing with the initial congestion window that's the new bottleneck. If you recall from my earlier article where I discussed post-quantum signature sizes, a direct transition from ECDSA to ML-DSA signatures in the certificates and protocol messages could add anywhere from 14KB to 18KB to the TLS handshake, and that would completely bust the default initial congestion window for most servers.

While it's always possible to increase the size of the initial congestion window (assuming our networks can take it), we also have to take into account that negotiating TLS is not the end in itself, we need to layer an application protocol on top of it. In practice this means that you want to, ideally, deliver the entire website homepage all in one go, so that a browser can start to process it.

In addition to things costing more and slowing down, making significant changes to how things work often leads to breakage. It's certainly a problem we have to deal with when it comes to network performance.

As we've seen, in TLS the handshake starts with a ClientHello. In this message, the client submits its request to the server and provides the initial parameters. A long time ago, this message used to be quite small, under 256 bytes, even. Over the years, as the complexity of TLS increased, the size of ClientHello grew larger, but it stayed within the size of one network packet. As a result of this, a lot of software out there was written with an assumption that the entire ClientHello will arrive as a single packet.

This assumption broke recently when we upgraded the key establishment in TLS to incorporate ML-KEM-768, which demands an additional 1,216 bytes. Checking a real-world ClientHello just now, I observed it to be 2,117 bytes in the latest Chrome browser. That's well past the amount that can be sent via a single packet (about 1,440 bytes of useful data).

As a result, these new large ClientHellos travel across the network as two TCP segments, and some software and devices can't handle that, for one reason or another. It's usually the infamous middleboxes, devices designed to inspect network traffic.

TLS has had a long history of problems with middleboxes. Almost every time an evolution of the protocol was necessary, the middleboxes were standing in the way. This eventually led to the inception of GREASE, a method of incorporating random bogus data to prevent assumptions of what can and cannot appear in the TLS packets.

Even if you don't run into a problem with intermediary devices, with a larger ClientHello you're sending more data and more packets. Your communication is slower, and there's an increased likelihood of packet loss, potentially leading to retransmission. This is what's reported by Google as a 4% median increase in the handshake latency. On desktop, worse on mobile phones.