Running post-quantum experiments

This article has also been posted to Thom Wiggers’s blog.

Fundamentally, the Transport Layer Security protocol (TLS), which secures most of the Internet connections, has mainly been a key exchange authenticated by digital signatures[1]. Even though it has undergone major changes since 1994, when SSL 1.0 was introduced by Netscape, it’s main mechanism has remained the same. The key exchange that is used was first based on RSA and later on (elliptic curve) Diffie-Hellman. The signatures used for authentication have almost always been RSA-based, though in recent years other kinds of signatures have been adopted, mainly ECDSA and Ed25519. This recent change to elliptic curve cryptography at both at a key exchange and signature level has resulted in considerable speed and bandwidth benefits in comparison to classic Diffie-Hellman and RSA.

TLS is the main protocol that protects the connections we use everyday. It is everywhere: it is used when we buy products online, when we register for a newsletter or when we access any kind of website. But, with the imminent threat of the arrival of quantum computers (a threat that seems to be getting closer and closer), we need to reconsider again the future of TLS. A wide-scale post-quantum experiment was carried out by Cloudflare and Google: two post-quantum key exchanges were integrated into Cloudflare’s TLS stack and deployed at their edge servers and in Chrome Canary clients. The goal of that experiment was to evaluate the performance and feasibility of deployment of two post-quantum key exchanges in TLS.

Similar experiments have been proposed for introducing post-quantum algorithms into the TLS handshake itself. Unfortunately it seems infeasible to replace both the key exchange and signature with post-quantum primitives as post-quantum cryptographic primitives are bigger, or slower (or both) than their predecessors. The proposed algorithms under consideration in the NIST post-quantum standardization process use larger mathematical objects than what is used for elliptic curves, traditional Diffie-Hellman or RSA. As a result, the size of public keys, signatures and key exchange material is much bigger than those from elliptic curves, Diffie-Hellman or RSA.

How can we solve this problem? How can we use post-quantum algorithms as part of the TLS handshake without making the material too big to be transmitted? In this blogpost, we will introduce a new mechanism for making this happen, explain how it can be integrated into the TLS 1.3 handshake and talk about implementation details. The key observation in this mechanism is that, while post-quantum algorithms have bigger communication size than their predecessors, post-quantum key exchanges have somewhat smaller sizes than post-quantum signatures, so we can try to replace signatures with key exchanges in some places to save space. We will only focus on the TLS 1.3 handshake as it is the TLS version that should be currently used.

The past experiments: making the traditional TLS 1.3 handshake post-quantum

TLS 1.3 was introduced in August 2018 with many security and performance improvements (notably, having only one round-trip to complete the handshake). But TLS 1.3 is designed for a world with classical computers, and some of its functionalities will be broken by quantum computers when they arrive.

The primary goals of TLS 1.3 are to provide authentication (the server side of the channel is always authenticated, the client side is optionally authenticated), confidentiality and integrity by using a handshake protocol and a record protocol. The handshake protocol, the one of interest for us today, establishes the cryptographic parameters for securing and authenticating a connection. It can be thought of as of having three main phases, as defined in RFC8446:

  • The Parameter Negotiation phase (referred to as ‘Server Parameters’ in RFC8446), which establishes some handshake parameters (whether the client is authenticated, application-layer protocol support, etc).

  • The Key Exchange phase, which establishes shared keying material and selects the cryptographic parameters to be used. Everything after this phase will be encrypted.

  • The Authentication phase, which authenticates the server (and, optionally, the client) and provides key confirmation and handshake integrity.


The main idea of past experiments that introduced post-quantum algorithms into the handshake of TLS 1.3 was to use them in place of classical algorithms by advertising them as part of the supported groups (an extension used by the client to indicate which named groups -Elliptic Curve Groups, Finite Field Groups- it supports for key exchange) and key share (an extension which contains the endpoint’s cryptographic parameters) extensions, and, therefore, establishing with them the negotiated connection parameters. Key encapsulation mechanisms (KEMs) are an abstraction of the basic key exchange primitive and were used to generate the shared secrets. In the case of using a pre-shared key, its symmetric algorithms can be easily replaced by post-quantum KEMs, as well; and, in the case of password-authenticated TLS, there has been some proposed ideas on how to use post-quantum algorithms with them.

TLS and PQKEMs

Most of the above ideas only provide what is often defined as ‘transitional security’, as its main focus is providing quantum-resistant confidentiality, but do not take into account quantum-resistant authentication. The idea of using post-quantum signatures for TLS authentication is possible, but the sizes of post-quantum signatures are larger than traditional ones. Furthermore, it is worth noting that using post-quantum signatures is much heavier than using post-quantum KEMs.

We can estimate the impact of such a replacement on network traffic by simply looking at the sum of the cryptographic objects that are transmitted during the handshake. In a typical TLS 1.3 handshake using elliptic curve X25519 and RSA-2048, such a handshake would transmit 1376 bytes corresponding to: the public keys for key exchange, the certificate, the signature of the handshake, and the certificate chain. If we were to replace X25519 by the post-quantum KEM Kyber512 and RSA by the post-quantum signature Dilithium II, two of the more efficient proposals, the size of the transmitted data would increase to 10036[2] bytes. This increase is mostly due to the size of the post-quantum signature algorithm.

The question then is: how can we achieve full post-quantum security and create a handshake that is efficient to be used?

A more efficient proposal: KEMTLS

There is a long history of other mechanisms, besides signatures, being used for authentication. Modern protocols, such as the Signal protocol, the Noise framework or WireGuard, rely on key exchange mechanisms for authentication, which are somewhat unsuitable for the TLS 1.3 case as they expect the long-term key material to be known in advance by the interested parties.

The OPTLS proposal by Krawczyk and Wee authenticates the TLS handshake without signatures by using a non-interactive key exchange (NIKE). However, the only somewhat efficient construction for a post-quantum NIKE is CSIDH, the security of which is the subject of ongoing debate. But, we can build on this idea by using KEMs for authentication. KEMTLS, the current proposed experiment, replaces the handshake signature by a post-quantum KEM key exchange. It was designed and introduced by Peter Schwabe, Douglas Stebila and Thom Wiggers in the publication ‘Post-Quantum TLS Without Handshake Signatures’.

KEMTLS, therefore, achieves the same goals as TLS 1.3 (authentication, confidentiality and integrity) in the face of quantum computers. One small difference compared to the TLS 1.3 handshake is that KEMTLS allows the client to send encrypted application data since the second client-to-server TLS message flow when client authentication is not required, and in the third client-to-server TLS message flow when mutual authentication is required. Note that with TLS 1.3 the server is able to send encrypted and authenticated application data in its first response message (although, in most uses of TLS 1.3, this feature is not actually used). With KEMTLS, then, when client authentication is not required, the client is able to send its first encrypted application data after the same amount of handshake round trips as in TLS 1.3.

Intuitively, the handshake signature in TLS 1.3 proves possession of the private key corresponding to the public key certified in the TLS 1.3 server certificate. For these signature schemes, this is the straightforward way to prove possession; but it’s also possible to make such proof through key exchanges. By carefully considering the key derivation sequence, only the server holding the private key that corresponds to the certified public key can decrypt any messages sent by the client to the server. Therefore, implicit authentication is fulfilled. It is worth noting that KEMTLS still relies on signatures by certificate authorities to authenticate the long-term KEM keys.

As said, KEMTLS’ application data transmitted during the handshake is implicitly, rather than explicitly authenticated (as in TLS 1.3), and has slightly weaker downgrade resilience and forward secrecy; but full downgrade resilience and forward secrecy is achieved once the KEMTLS handshake completes.

TLS 1.3 Handshake KEMTLS Handshake

Comparison of both handshakes: Classic TLS 1.3 one (left), KEMTLS one (right)

By replacing the handshake signature by a KEM key exchange, we reduce the size of the data transmitted in the example handshake using Kyber512 and Dilithium II to 8344 bytes, a significant reduction. Even for algorithms, such the NTRU-assumption based KEM NTRU and signature algorithm Falcon, that have a less-pronounced size gap, we still reduce bytes. KEM operations are typically computationally much lighter than signing operations as well, which makes the reduction even more significant.

KEMTLS was presented at ACM CCS 2020. You can read more about its details in the paper. It was initially implemented in the RustTLS library by Thom Wiggers using optimized C/assembly implementations of the post-quantum algorithms provided by the PQClean and Open Quantum Safe projects.

Cloudflare and KEMTLS: the implementation

As part of our effort to show that TLS can be completely post-quantum safe, we implemented the full KEMTLS handshake over the Golang’s TLS 1.3 suite. The implementation was done in several steps:

  • We first needed to clone our own version of Golang, so we could add different post-quantum algorithms to it. You can find our own version here. This code gets constantly updated with every release of Golang, following these steps.
  • We needed to implement post-quantum algorithms in Golang, which we did in our own cryptographic library CIRCL.
  • As we cannot force Certificate Authorities to use certificates with long-term post-quantum KEM keys, we decided to use Delegated Credentials. A delegated credential is a short-lasting key that the certificate’s owner has delegated for use in TLS 1.3. Therefore, they can be used for having post-quantum KEM keys. See its implementation in our Golang code here.
  • We implemented mutual auth (client and server authentication) KEMTLS by using Delegated Credentials for the authentication process. See its implementation in our Golang code here. You can also check this test for an overview of how it works.


Implementing KEMTLS was a straightforward process, although it did require changes to the way Golang handles a TLS 1.3 handshake and how the key schedule works.

A “regular” TLS 1.3 handshake in Golang (from the server perspective) looks like this:

Implemented Golang TLS 1.3 Handshake

We had to interrupt at the point that the server sends the Certificate (sendServerCertificate()) in order to send the KEMTLS specific messages. In the same way, we had to add the appropriate KEM TLS messages to the client’s handshake. And, as we did not want to change so much the way Golang handles TLS 1.3, we only added one new constant to the configuration that can be used by a server in order to ask for the Client’s Certificate (the constant is serverConfig.ClientAuth = RequestClientKEMCert).

The implementation is easy to work with: if a delegated credential or a certificate has a public key of a supported post-quantum KEM algorithms, the handshake will proceed with KEMTLS. If the server requests for a Client KEMTLS Certificate, the handshake will use client KEMTLS authentication.

Running the Experiment

So, what is next? What is next is to take the code we have produced and run it in the actual Cloudflare infrastructure to measure how efficiently it works.

Thanks

Many thanks to everyone involved in the project: Chris Wood, Armando Faz-Hernández, Thom Wiggers, Bas Westerbaan, Peter Wu, Peter Schwabe, Goutam Tamvada, Douglas Stebila, Thibault Meunier, and the whole Cloudflare cryptography team.


[1] It is worth noting that the RSA key transport in TLS ≤1.2 has the server only authenticated by RSA public key encryption, although the server's RSA public key is certified using RSA signatures by Certificate Authorities.

[2] These numbers, as it is noted in the paper, are based on the round-2 submissions