Sizing Up Post-Quantum Signatures for the Web

TLDR

1. In a typical TLS handshake on the Web there are at least six signatures and two public keys.
2. Even if they fit in the congestion window, with larger signatures, we see a double-digit percentage slowdown which can be a hard sell for browser vendors and content servers to adopt.
3. Because of the lead time, we shouldn’t wait too long to adopt PQ signatures on the web. It would be ideal if these six signatures and two public keys would fit together within 9kB.


Dear forum,

Nowadays, around 90% of all web-browsing is protected using TLS (“https”). [0] To make our browsing post-quantum secure, we need to update the key exchange and signatures in TLS. [1] For the former, with respect to performance, the majority of the KEM finalists will do. This is great, as without it, traffic encrypted today could be decrypted by a quantum computer in the future.

There is less urgency for post-quantum signatures in TLS. Only when there is a sufficiently large and stable computer, do we need to have updated the signatures. However, we expect the lead-time to be much higher: more parties and infrastructure involved. Also, none of the finalists, alternates, or even upcoming schemes we’re aware of fit the bill perfectly on their own.

The cause is that there are typically six signatures in a typical handshake with different requirements.

1. Online. The handshake signature is the only one that is created on every handshake.
2. Offline. The other signatures are created in advance.
a. With public key. The certificate chain contains public keys.
b. Without public key. The public keys for the two SCTs (for certificate transparency) and the OCSP staple are not included in the handshake.

There are several proposals to reduce the number of signatures, for instance [2,3]. We think changing protocols to suit the performance characteristics of PQ-crypto is the smart move. However, such changes could take years to adopt. Thus we need to understand the performance of plain TLS with drop-in PQ signatures.

The different variables and constraints make it a challenging puzzle. The best thing is to just try the options. There have been some nice papers measuring or simulating PQ TLS [4,5,6,7]. For TLS as used on the Web, they do not give us a complete picture:

1. The SCT and OCSP staples aren’t considered. Leaving half (three) the signatures out changes results considerably.
2. The networks tested or emulated offer insights, but are far from representative of real-world conditions. Either tests were conducted between two datacenters (which does not include real-world last-mile conditions such as Wi-Fi or spotty mobile connections); or a network was simulated with unrealistic packet loss behavior.

Here Cloudflare can contribute. Setting up an experiment with a modified browser is quite involved, especially with all the possible variations. Instead, as a first step, we decided to measure the most striking variable: the size.

To simulate larger signatures on an unmodified client, we pad the certificate chain with 1kB dummy certificates. We found a small fraction of clients or middleboxes had issues with them. Hence, for our experiment, we launched background requests on a small fraction of challenge pages to a page configured with these dummy certificates. For each connection we measured the handshake time. The graph and additional details can be found in the attached excerpt of an upcoming [9] blog post.

We see two effects. First, every kilobyte added requires a bit more time, due to limited bandwidth and possible physical-layer retransmissions. Secondly, when we fill our congestion window, we need to wait an extra RTT.

In previous discussions on the topic, often only the second effect is considered. A commonly heard solution is to increase the initial congestion window. In our experiment we used an initial congestion window of 30 instead of the default of 10. We see that the first effect already leads to a double-digit slowdown below 10kB — well before filling the congestion window.

The TLS handshake is just one step in a long chain required to show you a webpage. Casually browsing, it would be hard to notice a TLS handshake that’s 60% slower. But such differences add up. To make a website really fast, you need many seemingly insignificant speedups. Browser developers take this seriously: only in exceptional cases [8] does Chrome allow a change that slows down a microbenchmark by even a percent.

Because of the many parties and complexities involved, we should avoid waiting too long to adopt post-quantum signatures in TLS. That’s a hard sell if it comes at the price of a double-digit slowdown, not least to content servers but also to browser vendors and clients.

A timely adoption of PQ signatures on the web would be great. Our data so far suggests that this will be easiest, if six signatures and two public keys would fit in 9kB.

Best,

Bas Westerbaan
Cloudflare Research


[0] See, for instance
https://radar.cloudflare.com/
https://transparencyreport.google.com/https/overview
https://web.archive.org/web/20201111210500/https://netmarketshare.com/report.aspx?options=%7B%22filter%22%3A%7B%7D%2C%22dateLabel%22%3A%22Custom%22%2C%22attributes%22%3A%22share%22%2C%22group%22%3A%22secure%22%2C%22sort%22%3A%7B%22share%22%3A-1%7D%2C%22id%22%3A%22https%22%2C%22dateInterval%22%3A%22Monthly%22%2C%22dateStart%22%3A%222019-10%22%2C%22dateEnd%22%3A%222019-10%22%2C%22segments%22%3A%22-1000%22%7D
[1] Also DNS needs an upgrade, but we’ll leave that for another time.
[2] https://thomwiggers.nl/project/kemtls/
[3] https://www.amazon.science/publications/speeding-up-post-quantum-tls-handshakes-by-suppressing-intermediate-ca-certificates
[4] Sikeridis, Kampanakis, Devetsikiotis. Assessing the overhead of post-quantum cryptography in TLS 1.3 and SSH. CoNEXT’20.
[5] Paquin, Stebila, Tamvada. Benchmarking Post-Quantum Cryptography in TLS. PQCrypto 2020.
[6] Sikeridis, Kampanakis, Devetsikiotis. Post-Quantum Authentication in TLS 1.3: A Performance Study. NDSS2020.
[7] And just a few days ago: https://eprint.iacr.org/2021/1447
[8] https://chromium.googlesource.com/chromium/src/+/refs/heads/main/docs/speed/addressing_performance_regressions.md#if-you-believe-the-regression-is-justified
[9] To appear at https://blog.cloudflare.com/sizing-up-post-quantum-signatures

Long-term signatures can be efficiently distributed through DNS caches,
as in Section 3.4 of https://dl.acm.org/doi/10.1145/2508859.2516737.
Essentially all of the long-distance transmission is then replaced with
much faster lookups from the local ISP.

I agree that this is going beyond what KEMTLS does. I also agree with
your general comment that "such changes could take years to adopt".
There's a risk that focusing purely on the desired end scenario will
lose the race against attackers building quantum computers. Certainly
we should understand whether the costs of post-quantum signatures will
prevent an easy rollout within the TLS details that exist today.

Regarding your graphs, the median delay looks like about 8ms added for
each 10 kilobytes, meaning about 10Mbps, while the top-quartile delay
looks like about 20ms added for each 10 kilobytes, meaning about 4Mbps.
It'd be great to see more data points and some historical data to get an
idea of how the network speeds are evolving. I presume Cloudflare is
continually collecting metrics on bulk-download speeds.

---Dan

P.S. The statement "only in exceptional cases [8] does Chrome allow a
change that slows down a microbenchmark by even a percent" doesn't
appear to be correct. The cited Chrome page

https://chromium.googlesource.com/chromium/src/+/refs/heads/main/docs/speed/addressing_performance_regressions.md#if-you-believe-the-regression-is-justified

doesn't say "exceptional"; on the contrary, it spends several paragraphs
listing "some common justification scenarios", including "What do we
gain? It could be something like: ... Additional security".

Bas Westerbaan <b...@westerbaan.name> wrote:

Dear Bas, dear all,

> TLDR
How many of the offline signatures could realistically be stateful
hash-based signatures?

All the best,

Peter

Going a step further and looking up all of the long-term signatures in
DNS fundamentally changes the situation. The most popular signatures are
then automatically cached locally at the ISP for quick lookups by all of
the ISP's users. Often user devices will have their own DNS caches, and
the lookups of the same signature on that device will be even faster.

The reason to take specifically DNS rather than some ad-hoc associative
array is that DNS is the Internet's existing distributed caching system.
This eliminates issues of OS support and application coordination: the
DNS caches and DNS lookup mechanisms are already available, and one
simply has to use them.

One very easy way to integrate this into existing protocols is to
specify a new DNS-hash signature type that simply sends a 32-byte hash
of a signature. The device then looks up the 32-byte hash in DNS to
obtain the full signature.

(The full DNS name being looked up will be, e.g., a 51-byte text
encoding of the 32 bytes, plus a protocol identifier, plus the domain
name that the protocol is working with. For parallel retrieval of
several small packets concatenated to obtain a full signature, it will
be useful to allocate 1 extra byte in the DNS-hash signature to say the
number of packets being retrieved; the DNS name being looked up will
then include a counter. The full signature can have more type data.)

The same principles also apply to other long-term data such as public
keys and certificate metadata. Even short-term data, such as Google's
ephemeral key for the next 2 minutes, can be usefully cached to some
extent, especially at the ISP level.

The literature that I cited before shows how to obtain even better
latency---at the cost of more protocol modifications---by overlapping
the necessary lookups with the DNS lookups that are done anyway. Even
without this improvement, the latency can easily be lower than current
TLS whenever the DNS cache is hit.

It's good to understand the costs of every TLS server sending public
data to every TLS client. It's also good to understand how much easily
removable redundancy there is in the system. We want to get things
rolled out asap, but we also don't want short-term speed considerations
to be damaging everyone's long-term security.

---Dan

Unfortunately, this is not DNS any more, it is a new protocol that would require many years for deployment.
And there are a few ways it can break. DNSSEC cannot use any of the PQ Sig candidates due of the same reasons.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20211111173740.574204.qmail%40cr.yp.to.

NISTPQC should be looking at what can be easily rolled out today, but
should also be looking ahead 5 years, 10 years, 15 years, etc. Look at
how much changed from TLS 1.1 in 2006 to TLS 1.2 in 2008 to TLS 1.3 in
2018! To reiterate: we don't want to lose the race against attackers
building quantum computers; we also don't want short-term speed
It's most certainly DNS. There are constant experiments with sending new
types of data through DNS, and the most useful experiments end up being
widely used. Try typing "dig txt google.com" from a command line and
figuring out when those applications of DNS were introduced. I agree
that improvements could take years to adopt, but saying that a simple
use of DNS "would require many years" is exaggerating the difficulty.
There are many bigger things than post-quantum cryptography that DNSSEC
is unable to do because it starts from an artificially limited view of
(1) the problem space and (2) the solution space. (See, e.g., the series
of 15 "DNS security mess" talks on https://cr.yp.to/talks.html.) So it's
circular to refer to DNSSEC as an argument that something doesn't work.

---Dan