Why post-quantum signatures are breaking TLS handshake limits

When it comes to the transition to post-quantum cryptography, some aspects are easier than others. Transitioning key establishment to a quantum-resistant approach took some work, but we arrived at a solution (a hybrid approach, combining elliptic curves with ML-KEM) without a lot of trouble. When it comes to certificates and authentication, that's going to take much more work, and it all comes down to the differences in signature sizes between the algorithms we're using today (traditional) versus the algorithms we want to use tomorrow (post-quantum).

Whenever we engineer something, for example a cryptographic protocol, we take a variety of factors into account, consider the possibilities and their advantages and disadvantages, then make our decisions in such a way that we satisfy the constraints forced upon us. Security is usually not negotiable (although often falls on a spectrum), but performance is an important factor. Historically, we like security, but we love cryptography that's fast.

Some things pull you in, and that's what happened with elliptic cryptography. It seemed a perfect tool, both secure and performant, with fast operations and small signature sizes. Over the years, more and more protocols transitioned to this family of cryptographic algorithms, until it ended up embedded in everything. Requirements were easy to solve by adding another signature, until the whole thing came to an abrupt stop thanks to quantum computers. (If you need a refresher, our Guide to Post-Quantum Cryptography is a good and reasonably light read.)

The post-quantum transition of cryptography, forced by the threat of a cryptographically-relevant quantum computer (CRQC), is an excellent reminder of the fact that, in the digital world, there is no such thing as inherent security. It's all the games we play. We play with maths and find interesting properties, which we then put together in useful ways. What we call security is fleeting because the state of the art continuously advances. You may have heard already that attacks only get better.

Our classical computers can't break RSA and ECDSA maths, but, as it turns out, quantum computers can. To defend against the latter, we play more games, using different maths. We devise new algorithms. The only problem is, the properties of these new algorithms are different. In this particular instance, the performance remains on part, but the keys and signatures take much more space.

In the following table, we compare the key aspects of ML-DSA to those of traditional cryptography. We show values for the common algorithms and strengths we normally see in leaf certificates and intermediates, which use stronger cryptography. We focus only on ML-DSA because that's our main bet at the moment. If you'd like to understand what other algorithms look like, head over to the PQC Signature Zoo.

As you can see, the entry-level ML-DSA variant uses signatures that are 10x larger than RSA and 34x larger than ECDSA. This increase in public cryptography size changes the assumptions we made when we built our further layers of cryptography, so much that it might lead to things no longer working as they should.

As an aside, if you see slight differences in the claimed signature and public key sizes across articles on the Internet, that's likely because some use the raw primitive sizes and some take into account how the data is packaged for transport over the wire, as I do here.

At its core, an X.509 certificate is a packaging and transport vehicle for a public key, signed with an authority's key. When certificates initially debuted, we had only RSA keys. At the now-usual 2,048 bits, an RSA key takes 272 bytes and its signature 256. ECDSA, on the other hand, consumes 65 bytes for the public key (without compression) and 72 for the signature. With additional necessary metadata embedded in each certificate, the typical size of a leaf certificate may be about 1-2 KB.

One certificate is not sufficient to access a server securely. In practice, we rely on certificate chains, which have at least 2 certificates transported over the network. (A complete chain might consist of 3 certificates, when the root is taken into account, but this end-of-chain certificate shouldn't be transmitted.)

This additional intermediate doubles the size requirements. Intermediates and roots tend to use stronger cryptography, and that makes them larger still.

On top of this, protocols need at least one signature to authenticate the live cryptographic handshake. At this point, for a TLS handshake, we're talking about 3 signatures and 2 public keys, at a minimum.

In the early days of SSL, the CPUs were slow and cryptography too demanding. The cryptographic operations were the main bottleneck. (We also had much smaller web pages than today.) Now, the bottleneck is something you may not have heard of, TCP's initial congestion window.

Without spending too much time on it, the initial congestion window is the maximum amount of data you can send at the beginning of a TCP connection without incurring another network trip. The window used to be much smaller, but the modern limit is at about 14.5 KB. QUIC, a modern replacement for TCP (and implemented on top of UDP), has a limit that's only about 4,500 bytes, albeit for a different reason (anti-amplification defense, designed to dampen amplification DoS attacks that are easy to carry out over UDP).

Translated, if the server can't fit all its certificates and additional protocol-related cryptography in those 14.5 KB, it's going to have to wait to receive a go-ahead from the client at the most sensitive time of the conversation, the very beginning. On a small network, this performance penalty might be in double-millisecond digits. On mobile networks, it could be hundreds.

If your protocol uses UDP (QUIC again), large packets may require fragmentation, which is often dropped by middleboxes. On networks with significant packet loss, the performance is dragged down even further.

Vanilla X.509 certificates, described earlier, are not what we commonly use these days. On private networks perhaps, but in Web PKI we require the extended version of X.509 that's enriched with Certificate Transparency (CT) information. The CT ecosystem provides extended security guarantees that guarantee that all public certificates are recorded in public logs. The publishing is witnessed, currently by at least 2 operators. Each operator contributes a signature, which is embedded in X.509 certificates via the Signed Certificate Timestamp (SCT) extension.

With CT added to the mix, we're up to 5 signatures and 2 public keys in a typical TLS handshake.

Without going into the details of the calculations (that's possibly material for another blog post), here are the approximate numbers I came up with for typical chains in use today:

• ECDSA certificate chain: 586 bytes
• RSA certificate chain: 1,712 bytes
• ML-DSA certificate chain: 14,724, 18,640, or 18,565 bytes

The ML-DSA numbers require an explanation. We get the smallest size (14,724) if we use ML-DSA-44 for the entire chain, but this goes against best practice. The second value (18,640) we get if the intermediates and roots use stronger cryptography, which takes into consideration that these keys need to remain secure for a longer period of time. The third value is for use with CNSA 2.0 (NSA's Commercial National Security Algorithm suite), which accepts only ML-DSA-87.

Clearly, in the best case with a ML-DSA chain, the public cryptography alone busts the 14 KB initial congestion window, and nobody is happy with that. This increase is likely to lead to a small but important impact in our day to day usage. Constrained devices (e.g., IoT) may struggle to implement post-quantum cryptography at all.

This calculation focuses on the basics, but there are a variety of situations where the TLS handshake will further increase in size. For example:

• Sometimes we need to add another intermediate to the certificate chain, for example when transitioning from one hierarchy to another and want to maintain compatibility with older root stores.
• It gets slightly worse if we decide to use hybrid authentication, mixing traditional and post-quantum cryptography in the same certificate. We might want to do that because we don't trust these new post-quantum algorithms and prefer a "belt-and-braces" approach.
• It gets slightly worse again if you want to support revocation checking via OCSP, but this is a feature that's seldom used on the public internet these days.

We've seen that a naive transition to post-quantum algorithms means we have to plan for a potentially significant performance impact. In my next blog post, I'll explore the evidence that might help us substantiate these fears.