Keywords

1 Introduction

Transport Layer Security (TLS) is one of the most widely used protocols on the Internet today [11, 22], and provides confidentiality, integrity, and authenticity to communications between two parties. The most recent version, TLS 1.3 [29], uses ephemeral (elliptic curve) Diffie-Hellman (-EC-DH) to establish keys, which are used to encrypt parts of the handshake and the traffic that will be sent in the connection. Authentication of the server and (optionally) of the client can be achieved by using digital signatures. The corresponding public keys for those signatures are transmitted during the handshake in digital certificates, which are signed by a certificate authority (CA).

Given that TLS 1.3 is the most widely used protocol today to secure connections [22], it is vital to start thinking about how to integrate post-quantum cryptography into it to protect from the imminent threat of quantum computing. Advances in quantum computing are promising and motivate a swift move to quantum-resistant algorithms. However, widespread adoption and protocol standardization are slow processes that can take several years to reach consensus among the partiesFootnote 1. In fact, the National Institute of Standards and Technologies (NIST) is organizing a multi-year competition to select post-quantum algorithms for standardization [27]. Several proposals on how to integrate post-quantum cryptography into TLS have already been suggested in the form of specifications, implementations, and experiments.

Related Work. Many early experiments focused on transitional security to protect against adversaries capable of recording today’s communications with the hope of decrypting them in the future with a quantum computer. They focus on the key exchange phase of the handshake and add quantum-resistant confidentiality. This latter property is achieved by replacing the (EC-)DH key exchange by one based on a post-quantum Key Encapsulation Mechanism (KEM). However, this strategy does not address quantum-resistant authentication.

In 2016, a post-quantum experimentation project was initiated by Google [7], and was later expanded to a large-network scale in collaboration with Cloudflare in 2019 [21, 24]. In the latter experiment, connections made from experimental versions of the Chrome browser to Cloudflare’s edge servers used post-quantum key exchange algorithms in the TLS 1.3 handshake to secure connections and provide quantum-resistant confidentiality. The handshake used a “hybrid” key exchange protocol that combined post-quantum key exchange algorithms with traditional algorithms in order to safely use experimental cryptography without sacrificing any security guarantees. The experiment included two hybrid post-quantum key exchange protocols: X25519 [5] with the lattice-based KEM NTRU-HRSS [14] and X25519 with the supersingular-isogeny-based KEM SIKE [16]. These experiments focused on post-quantum confidentiality, but still relied on traditional authentication using non-quantum-resistant digital signature algorithms.

From a specification level, these works on quantum-resistant confidentiality mechanisms have taken priority [8, 13, 19, 31, 32, 37, 42], without much actual integration into real-world systems.

While these previous experiments provided valuable insights about the performance impact of post-quantum cryptography in real networks, post-quantum confidentiality is only one part of the picture: full post-quantum security also requires post-quantum authentication. In this sense, there are some research efforts towards this goal by using post-quantum signatures. But, most post-quantum signature schemes participating in the NIST competition have large public keys or signatures, and/or have significant performance considerations in their cryptographic operations. Sikeridis et al. [35] suggest that only the lattice-based candidates Dilithium [25] and Falcon [28] are viable contenders to be used in the TLS handshake, taking into account the trade-off between lengthy signatures and computationally heavy cryptographic operations.

Post-quantum KEM operations are, in practice, more efficient than post-quantum signature operations. A new approach, called KEMTLS  [33], achieves authentication using KEMs instead of relying on digital signatures. This technique consists of encapsulating under the long-term KEM public key advertised in the peer’s certificate, obtaining a shared secret in the process. Only the peer that has the private key corresponding to the public key in the advertised certificate can decapsulate the shared secret and decrypt any encrypted data sent under that key. Thus, KEMTLS uses post-quantum KEMs for both confidentiality and authentication to achieve full post-quantum security. A tweaked version of KEMTLS, called KEMTLS-PDK  [34], achieves the same properties while reducing the number of round-trips needed.

Contributions. The focus of this paper is analyzing how the integration of post-quantum cryptography impacts the TLS 1.3 handshake from a performance, implementation, and configuration perspective. We developed a framework for establishing TLS 1.3 handshakes using post-quantum algorithms on a real-world system: a distributed network that is subject to actual Internet traffic conditions and that spans two continents. We examined several handshake configurations: one that uses KEMs for confidentiality and post-quantum signature schemes for authentication, which we called PQTLS; and we evaluate the KEMTLS protocol and its reduced round trip version called KEMTLS-PDK. We measured the latency of these handshakes and compare them against the baseline TLS 1.3 handshake by considering both server-only and mutual authentication. Additionally, we touch upon the engineering process of implementing all these protocols in the Go language, and report some constraints found in the design of KEMTLS. Our implementations are publicly available for further experimentation.

Organization. In Sect. 2, we describe the integration of post-quantum algorithms into the TLS 1.3 handshake. Section 3 covers details of our implementation and our integration into the testbed network used for experimentation. In Sect. 4, we discuss our experimental methodology and measurement results, and finally in Sect. 5, we state our conclusions.

2 Post-quantum Cryptography in TLS 1.3

We first give an overview of the TLS 1.3 handshake, and then discuss proposed specifications, implementations, and experiments for integrating the PQTLS, KEMTLS and KEMTLS-PDK post-quantum handshakes.

2.1 Reviewing the TLS 1.3 Protocol

Standardized in 2018, the TLS 1.3 protocol emerged in response to dissatisfaction with the outdated design of the TLS 1.2 handshake, its two-round-trip overhead, and the increasing number of practical attacks on older versions of TLS [1,2,3, 6]. The pressure to increase efficiency also motivated the creation of alternative protocols such as the QUIC protocol [15]. In light of this, the main improvements of TLS 1.3 are: reducing the handshake’s latency, encrypting as many messages as possible of the handshake itself, improving resilience to cross-protocol attacks, and removing legacy features [39]. It achieves a one-round-trip time (1-RTT) handshake and even a 0-RTT handshake through a resumption mode.

The defaultFootnote 2 mode of the protocol uses certificates for authentication and (EC-)DH for shared secret generation. In this mode, the handshake starts with the client sending a \(\mathtt {ClientHello}\) (\(\mathtt {CH}\)) message to the server. This message advertises the supported (EC-)DH groups and the ephemeral (EC-)DH keyshares offered by the client and specified in the and extensions, respectively. The \(\mathtt {CH}\) message also advertises the signature algorithms supported in the extension. It also contains a nonce and a list of supported symmetric-key algorithms (ciphersuites).

The server processes the \(\mathtt {ClientHello}\) message and chooses the appropriate cryptographic parameters to be used in the connection. If (EC-)DH key exchange is in use (meaning the client sent the extension), the server sends a \(\mathtt {ServerHello}\) (\(\mathtt {SH}\)) message containing a extension with the server’s (EC-)DH key corresponding to one of the advertised by the client. The \(\mathtt {SH}\) message also contains a server-generated nonce and the ciphersuite chosen.

An ephemeral shared secret is then computed at both ends (the client computes it when it receives \(\mathtt {SH}\)). After this point, all subsequent handshake messages are encrypted using keys derived from this secret.

The server then sends a certificate chain (\(\mathtt {ServerCertificate}\) message) and a message that contains a proof that the server possesses the private key corresponding to the public key advertised in its leaf certificate. This proof is a signature over the handshake transcript and it is sent in the \(\mathtt {ServerCertificateVerify}\) message. The advertised in \(\mathtt {CH}\) are used to decide which algorithms can be used to generate this signature. The goal of this message is to provide proof of possession of the server’s private key, which is essential for achieving authentication. The server also sends the \(\mathtt {ServerFinished}\) message that provides integrity of the handshake up to this point. It contains a message authentication code (MAC) over the entire transcript providing key confirmation and binding the server’s identity to any computed keys.

Optionally, the server can send a \(\mathtt {CertificateRequest}\) message, prior to sending its \(\mathtt {ServerCertificate}\) message, requesting a certificate from the client for authentication. At this point, the server can immediately send application data to the unauthenticated client. Upon receiving the server’s messages, the client verifies the signature of the \(\mathtt {ServerCertificateVerify}\) message and the MAC of the \(\mathtt {ServerFinished}\) message. If requested, the client must respond with their own authentication messages, \(\mathtt {ClientCertificate}\) and \(\mathtt {ClientCertificateVerify}\), to achieve mutual authentication. Finally, the client must confirm their view of the handshake by sending a MAC over the handshake transcript in the \(\mathtt {ClientFinished}\) message.

It is only after this process that the handshake is completed, and the client and server can derive the keying material required by the record layer to exchange application data protected with authenticated encryption.

2.2 PQTLS: Signed Post-quantum TLS 1.3

A variety of specifications, implementations and experiments explain how to integrate post-quantum cryptography into the TLS 1.3 handshake. Regarding the post-quantum key exchange phase of TLS 1.3 (without addressing post-quantum authentication), several Internet-Drafts are proposed [13, 19, 31, 37, 42], as well as some experimental demonstrations [9, 21, 23, 24]. On the other hand, fewer works have focused on post-quantum authentication. In [18, 35], the authors recommended that the adoption of at least two post-quantum signature algorithms is viable for the TLS 1.3 handshake.

There are no theoretical obstacles for transitioning TLS 1.3 to a post-quantum world. One can use post-quantum signature algorithms for authentication and the (EC-)DH key exchange can be replaced by a post-quantum KEM; we call this approach PQTLS.

In practice, however, this replacement is not so simple. CAs must adapt their software to include post-quantum signatures, and, historically, the Web Public Key Infrastructure (PKI) and other X.509 PKIs have limited which algorithms can be used. It could take a long time until new algorithms are widely deployed. These changes may occur in the future but, for the purpose of experimentation and rapid deployment, these issues become limitations.

We propose a practical approach for overcoming this problem. Specifically, we rely on a delegation mechanism for credentials. A Delegated credential (DC) is an authenticated credential valid for a short period (at most 7 days) that can be used to decouple the handshake authentication algorithm from the authentication algorithms used in the certificate chain: a delegated credential can contain an algorithm to be used in the handshake and, in turn, it is cryptographically bound to the end-entity certificate as it is authenticated by it. The process of authenticating the DC is executed at the TLS stack level.

Using DCs in itself does not give us full post-quantum security, but it allows us to support post-quantum authentication algorithms that are not supported by existing CAs. An existing certificate is used to authenticate this delegated credential (by signing in a classical way in our experiments), and the advertised algorithm in the DC is used to authenticate the handshake.Footnote 3 The Internet Engineering Task Force (IETF) draft describing this technique, “Delegated Credentials for TLS” [4], is on track for standardization.Footnote 4

Using delegated credentials comes with other advantages for our cases. Unlike a regular certificate, a delegated credential is smaller and has no other extensions, such as revocation lists and certificate statuses, which makes it a perfect fit for experiments where the size of parameters is important. Also, DCs are validated only at the TLS stack level, which reduces the number of codebases or systems where we needed to roll out new algorithms.

If full post-quantum security is wanted, the whole certificate chain will need to contain post-quantum algorithms. A peer wanting to authenticate another peer with its certificate (and the public key in it) in the TLS 1.3 handshake requires confidence that the associated private key is owned by the certificate owner’s peer. This confidence is obtained through the use of public key certificates that bind these values to an identity. A CA signs certificates after asserting proof of possession of the private key. If the peer does not hold the public key of the CA that signed the other peer’s certificate, then it might need an additional certificate to obtain that public key. These certificates are called ’intermediates’.

For a client to authenticate a server it uses this chain of certificates: a root CA’s one, followed by at least one intermediate CA certificate, and then the leaf certificate of the server. Certificates can be cached, pre-installed or suppressed, which means that less data needs to be transmitted during the handshake; but these mechanisms are not widely deployed. In turn what this means is that for a full post-quantum TLS 1.3 handshake, peers will need to transmit the whole certificate chain and verify all their authentication proofs (at least three signatures or other proofs of authentication). If a DC is used in this scenario, data transmitted is increased, as well of the number of authentication operations.

2.3 KEMTLS: KEMs Everywhere

Using post-quantum signatures for authentication comes with another challenge. The proposed signature schemes participating in the NIST post-quantum competition have public keys or signatures much larger than their classical counterparts. For most algorithms, this size increase for post-quantum signatures is bigger than for post-quantum KEMs. The large size of cryptographic material can become an issue in the PQTLS scenario.

KEMTLS suggests the use of KEMs as the primary asymmetric building block for both the key exchange and authentication phases of the TLS 1.3 handshake. Its goal is to achieve a TLS 1.3 handshake that provides full post-quantum security (confidentiality and authentication) in an efficient way. KEMs instead of signatures are used for authentication because the KEM’s public keys and ciphertexts are smaller.

Like in PQTLS, the client advertises their support of post-quantum KEMs as part of the extension, and their supported ephemeral KEM public keys as part of their extension. Support for KEMTLS authentication, via KEM leaf certificates or DCs with KEMs, is indicated by including KEMs in the extension.

The server, in turn, determines the appropriate cryptographic parameters to be used in the connection, and replies with a ciphertext: an encapsulation against one of the advertised ephemeral KEM public keys of the \(\mathtt {ClientHello}\) message. The encapsulation generates a second output: an unauthenticated ephemeral shared secret. From this point onward, all subsequent messages will be encrypted under the secret, after applying the appropriate key schedule operations. The server also sends its certificate chain (\(\mathtt {ServerCertificate}\) message): the leaf certificate (or DC) should advertise a post-quantum KEM public key. Optionally, the server can send a \(\mathtt {CertificateRequest}\) message, which is sent prior to the \(\mathtt {ServerCertificate}\) message, asking the client to authenticate.

Contrary to TLS 1.3, the server cannot provide explicit proof of possession (using digital signatures) of the private key corresponding to the public key advertised as part of the leaf certificate (or DC). Instead, in KEMTLS, the client must receive the \(\mathtt {ServerCertificate}\) message first, and reply with the encapsulation of the public key advertised in it. This encapsulation (a ciphertext) is sent as part of a new TLS message called \(\mathtt {ClientKEMCiphertext}\). The KEMTLS handshake diverges from the TLS 1.3 standard, as the server must wait for this message adding another flight or half round-trip to the protocol.

The second output of the client key encapsulation is an implicitly authenticated shared secret. This secret is mixed into the key schedule operations and will afterwards be used to encrypt all subsequent messages. Only the intended server can decrypt any messages encrypted under this key. By being able to do so, the server proves possession of the private key corresponding to the public key in it’s certificate. If the server did not request client authentication (server-only authentication), the client can immediately send their \(\mathtt {ClientFinished}\) message in this flight, which contains a MAC over the entire transcript. The client can also send at this point application data, which is implicitly authenticated, and has slightly weaker downgrade resilience and forward secrecy compared to when digital signatures are used.

When receiving the \(\mathtt {ClientKEMCiphertext}\) message and decapsulating their parameters, the server can send their confirmation message \(\mathtt {ServerFinished}\), authenticating the handshake transcript. In the same flight, the server can now send application data encrypted by the shared secret of the decapsulation mechanism. Once the client receives and verifies the \(\mathtt {ServerFinished}\) message, the server is explicitly authenticated, and the handshake has full downgrade resilience and strong forward secrecy.

Ciphersuite Negotiation and Middlebox Compatibility. TLS 1.3 allows clients and servers to negotiate the used algorithms. For key exchange, the supported algorithms are advertised in the extension. For authentication, the mandatory extension contains a list of algorithms that can be used by the peer to pick the appropriate certificate advertised by the corresponding peer. Post-quantum KEMs can simply be added to these lists and negotiated accordingly.

Any compliant TLS 1.3 implementation that does not understand or wish to negotiate KEMTLS will simply ignore any advertised post-quantum KEMs for the key exchange, and will not send a leaf certificate (or DC) with a KEM public key. As all messages following \(\mathtt {ServerHello}\) are encrypted, changes in the protocol should be opaque to any non-decryption traffic interception; otherwise, a barrier on its adoption will be observed, similar to the “Middlebox” issues that arose when moving from TLS 1.2 to TLS 1.3 [20, 38]. Issues may still arise if traffic interception servers enforce stricter constraints on key sizes than those required by the TLS 1.3 standard; these kinds of issues are harder to control.

Mutual Authentication. TLS 1.3 requires that “the client’s identity should be protected against both passive and active attackers” [29, Sec. E.1]. Thus, both TLS 1.3 and KEMTLS cannot send the client’s certificate (its identity) before the server has been authenticated. In TLS 1.3, the client can authenticate to the server, after receiving a request to do so from it, by providing its certificate and a signature over the handshake transcript.

In the sketch of client authentication in KEMTLS  [33, App. C], upon request from the server, the client responds with the \(\mathtt {ClientCertificate}\) message, where the leaf certificate (or DC) must contain a post-quantum KEM public key. This message must be sent in the same flight as when the \(\mathtt {ClientKEMCiphertext}\) message is sent (but after it). In turn, the server sends the \(\mathtt {ServerKEMCiphertext}\) message containing an encapsulation against the client certificate’s KEM public key after processing the \(\mathtt {ClientKEMCiphertext}\) and \(\mathtt {ClientCertificate}\) messages. The client must wait for a \(\mathtt {ServerKEMCiphertext}\) message from the server prior to sending their \(\mathtt {ClientFinished}\) or any other message. Therefore, the client proves their identity by showing that both sides can arrive to the same shared key: the output of the encapsulation of the client’s public key sent in the leaf certificate (or DC). Finally, once the server receives the \(\mathtt {ClientFinished}\), it can send \(\mathtt {ServerFinished}\), which achieves full downgrade resilience and forward secrecy.

The straightforward addition of these messages adds a round-trip to the handshake, as they can not be sent until the server has been authenticated. This extra round does not occur in the TLS 1.3 handshake because an explicit proof of authentication (the signature) is sent in the same flight as the certificate.

For a practical instantiation for our experiments, we use classically signed DCs that wrap KEM public keys to provide certified KEM keys.

2.4 KEMTLS-PDK: Reducing Round Trips

KEMTLS-PDK is a technique that relies on pre-distributed keys and has the goal of improving KEMTLS round-trips. It assumes the client knows the server’s public key beforehand. This is not an uncommon situation as, for example, web browsers cache certificates of frequently accessed servers, mobile apps pin certificates, or server certificates are pre-distributed through DNS [17].

During the handshake, servers can authenticate earlier to the client, when KEM authentication keys are pre-distributed. We implement this mechanism using the TLS cached information extensionFootnote 5 [30], so the client sends an encapsulation against the server’s public KEM key in the first flight (alongside the \(\mathtt {ClientHello}\) message: either as a separate message or as an extension for it). This allows the server to be explicitly authenticated by sending \(\mathtt {ServerFinished}\) in the first message to the client and to immediately send application data.

On the other hand, the situation is more complex for achieving earlier client authentication since the client has to proactively know that the server will ask for its authentication. Nonetheless, this assumption does occur in certain applications such as in virtual private networks (VPN), where the client could send the certificate as early as possible.

Recall that for privacy reasons, TLS 1.3 requires that the server must be authenticated prior to transmitting the client certificate, and that this certificate must be sent encrypted. For the former requirement, KEMTLS-PDK assumes the client knows the server’s certificate so it is sent after the \(\mathtt {ClientKEMCiphertext}\) message in the first flight (as a separate message from the \(\mathtt {ClientHello}\) one). For the latter requirement, the client certificate is encrypted under the shared secret resulting from the encapsulation mechanism used for \(\mathtt {ClientKEMCiphertext}\). Thus, it is possible to remove a full round-trip from KEMTLS with mutual authentication.

Early client authentication can be secured by caching a \(\mathtt {CertificateRequest}\) message using the TLS cached information extension. The client certificate will then contain a key with an authentication algorithm that is likely known to be supported by the server. However, further investigation is needed for coming with a mechanism to encrypt the client’s certificate.

3 Implementation Details

3.1 Implementation in Go

Go is a high-level programming language with support for the TLS protocol (including version 1.3). Its standard library is open, which allowed us to made modifications to its internals without requiring third-party libraries. While Go is well-known for developing web server applications, it also has mechanisms to interact with low-level features of the computer architecture. This is particularly useful for accessing architecture-specific capabilities, which are only available through assembler code.

Some implementations of post-quantum algorithms are available. The teams currently contending at the ongoing NIST’s post-quantum competition provide implementations in C/C++. The Open-Quantum Safe [36] project wraps C implementations to run in Go through the cgo programming interface. However, performance degradation in it can be observed due to this wrapping procedure. The CIRCL [10] library implements a number of post-quantum algorithms natively in Go, including SIDH and SIKE [16]. As part of our contributions, we integrate to the CIRCL library AVX2-optimized implementations of the Dilithium signature scheme (round 2) and the Kyber key encapsulation mechanism.

Go provides a clean implementation of TLS 1.3. However, the implementation is conservative in regards to the type of extensions and algorithms that it supports. Changing the TLS 1.3 implementation to include delegated credentials and PQTLS required including some extensions and adding certain algorithm identifiers. It also meant adding a way for generating and validating delegated credentials, as well as adding the ability to include the delegated credentials X.509 extension to generated certificates. We also added the cached information extension [30] and modified it to work with TLS 1.3 for KEMTLS-PDK.

Integrating KEMTLS and KEMTLS-PDK was more challenging. Doing so required the interruption of the handshake’s flow depending on whether there is cached information, whether it is server-only authentication, or whether it is mutual authentication. As noted, the flow of messages in KEMTLS and KEMTLS-PDK is different depending on the authentication modes: server-only, mutual or with cached information. This differs from the standard TLS 1.3 handshake that follows the same flow of messages regardless if server-only or mutual authentication is performed. These differences were an important lesson learned during our implementation as it was often a source of errors.

We made available all of these modifications in a fork of Go at https://github.com/cloudflare/go/tree/cf-pq-kemtls. This code integrates CIRCL and can be used as a replacement of the standard Go to compile other Go programs. Hence, anyone wanting to use post-quantum algorithms or the new handshake protocols can benefit from our code by compiling programs with our modified Go.

3.2 A Testbed Network

To test and measure TLS connections, we looked for a service that operates under common Internet conditions and spans across different geographical locations. We chose Drand [40], a distributed randomness beacon written in Go, as the target of our experimentation. In this network, Drand servers are linked so they can collectively produce publicly-verifiable random numbers at fixed intervals of time. A threshold signature scheme prevents collusion or biasing the generation of numbers. Nodes in the network communicate with one another using a gRPC protocol [26] with TLS authentication. Additionally, the Drand service exposes public randomness through an HTTPS endpoint.

Changes in the Drand code base are minimal. We needed to provide and configure a certificate with the DCs extension enabled for servers and clients. We also needed to state which protocol will be initiated (KEMTLS or PQTLS) by stating so at the TLS configuration level. If KEMTLS-PDK wanted to be used, a “regular” KEMTLS handshake is first run, information is cached (the \(\mathtt {ServerCertificate}\) message), and then cached information is used in a fresh KEMTLS-PDK handshake by configuring it at the TLS configuration level. We added those configuration options for ease of experimentation: in a more realistic scenario stating which key exchange and signature algorithms are supported should be enough to trigger the appropriate protocol execution.

At run time, fresh delegated credentials are generated each time that a request arrives. However, these credentials can be further cached and stored so they can be reused between connections. A mechanism that routinely checks the validity of these credentials can also be implemented. This shows that delegated credentials can be easily implemented and used without needing to constantly modify certificate storage or retrieval. It is worth noting that adding delegated credentials increases the number of validations that need to be executed: the certificate has to be validated, the delegated credential has to be validated and the handshake has to be validated.

4 Measurement Experiment and Discussion

The goal of our experiment is to analyze the effects on the TLS handshake when using post-quantum algorithms. To do that, we measure the time it takes for a TLS 1.3 handshake using certificate-based authentication to complete, and compare all experiments to this standard measure.

4.1 Experiment Setup

We build a Drand cluster with one leader node and three worker peers. Each node independently ran in a data center located in Portland, USA. The connection of each internal node and the external HTTPS interface are configured to support post-quantum handshake protocols.

A Drand client retrieves randomness from the Drand network. We opted for locating the client far from the Drand network itself, so it is located in Lisbon, Portugal. With this setup our experiment faces the same traffic conditions found in transatlantic connections. Source codes of the client program are available at https://github.com/claucece/KEMTLS-local-measurements.

We choose a combination of cryptographic algorithms for setting up the following handshake configurations:

  • TLS 1.3 handshake using Ed25519 certificates for authentication (baseline).

  • TLS 1.3 + DC handshake with Ed25519 certificate and delegated credentials either using Ed25519 or Ed448 algorithms for authentication.

  • PQTLS handshake with SIKEp434 and Kyber512 for key exchange, and hybrid signatures using round-two Dilithium mode 3 and mode 4, respectively, paired with Ed25519 and Ed448 for authentication (the authentication algorithms are advertised in DCs).

  • KEMTLS handshake with SIKEp434 and Kyber512 for both key exchange and authentication (the authentication algorithms are advertised in DCs).

  • KEMTLS-PDK handshake using the same configuration as KEMTLS (server authentication only).

4.2 Measurements

For each client to server connection, we measured the time elapsed until completion of the TLS handshake, that is until the client can send encrypted application data, for each different handshake configuration. We also measured the elapsed time for each flight of the handshake, i.e., the time elapsed that a peer (server or client) waits for receiving messages from their counterpart. We initiated two timers: one for the client (which started when the \(\mathtt {CH}\) message was constructed and sent) and one for the server (which started when the \(\mathtt {CH}\) message is received). Therefore, the first and second flight, as seen in the tables, do not include network latency, as the timer is started prior to the message being sent or just when it is received, respectively. Note that the round trip times (RTT) from the third flight onward are affected by the conditions of the state of the network. We tested the scenarios over an average-latency network.

To reduce the effects caused by the state of the network, the Drand client was instructed to fetch randomness from the Drand server consecutively during one hour. The total number of connections during this period amounts to approximately \(5\times 10^3\) connections. From them, we calculated the average time of the connections and report the timings in Table 1 and Table 2. We also measured the total average time until the handshake is completed (note that these times include the sending and receiving of encrypted application data). These measures are listed in Table 3 and Table 4.

In server-only authentication, the handshake performs the following flights:

  • \(1^\text {st}\) (\(C \Rightarrow S\)) Sending \(\mathtt {ClientHello}\) for all cases.

    KEMTLS-PDK : this message includes the \(\mathtt {ClientKEMCiphertext}\) message, and a hash of the cached server’s \(\mathtt {ServerCertificate}\) message.

  • \(2^\text {nd}\) (\(C \Leftarrow S\)) Processing of \(\mathtt {ClientHello}\).

    Standard and PQTLS : reply with the \(\mathtt {ServerHello}\), \(\mathtt {ServerCertificate}\), \(\mathtt {ServerCertificateVerify}\) and \(\mathtt {ServerFinished}\) messages.

    KEMTLS : reply with the \(\mathtt {ServerHello}\) and \(\mathtt {ServerCertificate}\).

    KEMTLS-PDK : reply with the \(\mathtt {ServerHello}\) and \(\mathtt {ServerFinished}\) messages.

  • \(3^\text {rd}\) (\(C \Rightarrow S\)) Processing of received messages based on the protocol.

    Standard and PQTLS : processing of \(\mathtt {ServerHello}\), \(\mathtt {ServerCertificate}\), \(\mathtt {ServerCertificateVerify}\) and \(\mathtt {ServerFinished}\) messages.

    Reply with \(\mathtt {ClientFinished}\) and immediate sending of encrypted application data.

    KEMTLS : processing of \(\mathtt {ServerHello}\) and \(\mathtt {ServerCertificate}\). Reply with \(\mathtt {ClientKEMCiphertext}\) and \(\mathtt {ClientFinished}\) messages and immediate sending of encrypted application data.

    KEMTLS-PDK : processing of \(\mathtt {ServerHello}\) and \(\mathtt {ServerFinished}\) messages. Reply with \(\mathtt {ClientFinished}\) and immediate sending of encrypted application data.

  • \(4^\text {th}\) (\(C \Leftarrow S\)) Processing of received messages based on the protocol.

    Standard and PQTLS : processing of \(\mathtt {ClientFinished}\) message and of encrypted application data.

    KEMTLS : processing of \(\mathtt {ClientKEMCiphertext}\) and \(\mathtt {ClientFinished}\) messages. Reply with \(\mathtt {ServerFinished}\) message.

    KEMTLS-PDK : processing of \(\mathtt {ClientFinished}\) message and of encrypted application data.

In mutual authentication, the handshake performs the following flights:

  • \(1^\text {st}\) (\(C \Rightarrow S\)) Sending \(\mathtt {ClientHello}\) for all cases.

  • \(2^\text {nd}\) (\(C \Leftarrow S\)) Processing of \(\mathtt {ClientHello}\).

    Standard and PQTLS : reply with the \(\mathtt {ServerHello}\), \(\mathtt {ServerCertificate}\), \(\mathtt {ServerCertificateVerify}\), \(\mathtt {CertificateRequest}\) messages followed by the \(\mathtt {ServerFinished}\) message.

    KEMTLS : reply with the \(\mathtt {ServerHello}\), the \(\mathtt {ServerCertificate}\) and the \(\mathtt {CertificateRequest}\) messages.

  • \(3^\text {rd}\) (\(C \Rightarrow S\)) Processing of received messages based on the protocol.

    Standard and PQTLS : processing of \(\mathtt {ServerHello}\), \(\mathtt {ServerCertificate}\), \(\mathtt {ServerCertificateVerify}\), \(\mathtt {CertificateRequest}\) messages followed by the \(\mathtt {ServerFinished}\) message.

    Reply with the \(\mathtt {ClientCertificate}\), the \(\mathtt {ClientCertificateVerify}\) and the \(\mathtt {ClientFinished}\) messages, and immediate sending of encrypted application data.

    KEMTLS : processing of the \(\mathtt {ServerHello}\), the \(\mathtt {ServerCertificate}\) and the \(\mathtt {CertificateRequest}\) messages.

    Reply with \(\mathtt {ClientKEMCiphertext}\) and \(\mathtt {ClientCertificate}\) messages.

  • \(4^\text {th}\) (\(C \Leftarrow S\)) Processing of received messages based on the protocol.

    Standard and PQTLS : processing of the received \(\mathtt {ClientCertificate}\), \(\mathtt {ClientCertificateVerify}\) and \(\mathtt {ClientFinished}\) messages, and received encrypted application data.

    KEMTLS : processing of \(\mathtt {ClientKEMCiphertext}\) and \(\mathtt {ClientCertificate}\) messages. Reply with \(\mathtt {ServerKEMCiphertext}\) message.

  • \(5^\text {th}\) (\(C \Rightarrow S\)) This case only happens in KEMTLS. It includes the processing of \(\mathtt {ServerKEMCiphertext}\) message and sending of the \(\mathtt {ClientFinished}\) message. Immediate sending of encrypted application data.

  • (\(C \Leftarrow S\)) This case only happens in KEMTLS. It includes the processing of \(\mathtt {ClientFinished}\) message and any application data. Sending of the \(\mathtt {ServerFinished}\) message.

Table 1. Average time in \(10^{-3}\) s of messages for server-only authentication. Note that timings are measured per-client and per-server: each one has its own timer. The ‘KEX’ label refers to the Key Exchange and the ‘Auth’ label refers to authentication.
Full size table

4.3 Discussion

As noted, we initiated two timers for our measurements: one for the client (which started when the \(\mathtt {CH}\) message was constructed and sent) and one for the server (which started when the \(\mathtt {CH}\) message is received). This is the reason why the first and second flights see small timings as they do not take into account network latency. Starting from the third flight, the impact of network latency can be seen. An important point to note as well is that encrypted application data is sent already on the 3rd flight of all experiments except for KEMTLS for mutual authentication (as the client has to wait two flights in order to be able to send application data), which can increase the timing numbers.

When adding delegated credentials to the TLS 1.3 handshake, a peer receiving a delegated credential must validate that it was signed by the appropriate end-entity certificate (which is sent as part of the handshake) and must validate the certificate chain, as well. In our measurements, we observed a short increase in the latency of the flights when DCs are added; but the impact is almost negligible (specially, in the second flight when the DCs are received).

This is not the case when adding either post-quantum signatures or post-quantum KEMs for certain algorithms. The first observable difference appears in the \(\mathtt {ClientHello}\) in both server-only authentication and mutual authentication: this message advertises both classic and post-quantum key exchange algorithms because this could be the realistic scenario for systems when transitioning to post-quantum cryptography. The timings increase specially when using SIKEp434 as a KEM in both KEMTLS and PQTLS, because its KEM decapsulation time takes in average 8.92 ms (when using the implementation of the CIRCL library). The predominant factor that slows down PQTLS is the number of signature validations; but this is similar (when using Kyber512) to using Ed448.

Table 2. Average time in \(10^{-3}\) s of messages for mutual authentication. Note that timings are measured per-client and per-server: each one has its own timer. The ‘KEX’ label refers to the Key Exchange and the ‘Auth’ label refers to authentication.
Full size table

In regards to KEMTLS, its biggest drawback is the number of round-trips that it has to perform, specially when performing mutual authentication. The KEM cryptographic operations do not seem to heavily impact the connection if the underlying algorithm operations are fast. An ideal scenario for post-quantum cryptography is the use of KEMs for both confidentiality and authentication provided that the number of round trips do not increase, which is the case of KEMTLS-PDK for server authentication. This prediction matches with the timings in tables: note that the best scenario is KEMTLS-PDK for server-only authentication, specifically, when it is used with Kyber512.

Let’s look now at the measurements in regards to the kind of peer authentication they perform:

In the case of server-only authentication, KEMTLS performs faster than PQTLS and, in both cases, a client can immediately send application data on the third flight (when the client sends its \(\mathtt {ClientFinished}\)). Nevertheless, for KEMTLS the server still has to wait for the \(\mathtt {ClientFinished}\) to arrive and to send their \(\mathtt {ServerFinished}\) in turn, in order to be able to send application data. Sending of the \(\mathtt {ServerFinished}\) completes the handshake for the server, and provides full downgrade-resilience and forward-secrecy for the whole connection. However, this extra half-round trip forces the server to wait for a time before sending application data, which could not be an ideal scenario for real-world systems. In contrast, the client can send application data after sending their \(\mathtt {ClientFinished}\) (as noted in the measurements) but it has weaker security protections (weak downgrade-resilience and forward-secrecy), and, therefore, a client might also wait until receiving the \(\mathtt {ServerFinished}\) message to send its data in turn. This adds an extra round-trip which is not noted in the measurements. If we look at Fig. 1, we see that the best protocol to use is KEMTLS, if we don’t take into consideration that application data sent at that point has weaker security properties. The ideal case is using KEMTLS-PDK which allows the sending of application data much earlier and with the stronger notions of the security properties.

For mutual authentication, KEMTLS has the biggest impact on the handshake completion timings, as an extra flight is needed prior to be able to send encrypted application data, as seen in Fig. 1. SIKEp434, on average, increases the handshake timings by approximate 10ms compared with Kyber512 for the verification of the peer’s Certificate in both cases. For this reason, the PQTLS completion time is also slowed down when using SIKEp434 even without the extra round-trip addition. Although, we do not provide timings for the KEMTLS-PDK handshake with mutual authentication, our timings can provide an insight about the cost of the operations and the relevance of the algorithm selection.

Fig. 1.
figure 1

Comparison of: on the left, server authentication flows for the 3rd, and 4th flights; on the right, mutual authentication flows for the 5th and 6th flights. Both using Kyber512.

Full size image
Table 3. Total average handshake completion time (in \(10^{-3}\) s) for server-only authentication.
Full size table
Table 4. Total average handshake completion time (in \(10^{-3}\) s) for mutual authentication.
Full size table

4.4 Optimizations

The cost of transmitting post-quantum parameters is tangible in our measurements. These costs can be further optimized by using a form of certificate compression [12] or of suppression of the intermediate certificates [41]. Still, the costs of post-quantum operations needed remains.

5 Conclusions

Our experimental results are the first ones that integrate different post-quantum handshake alternatives to the TLS 1.3 handshake into a real-world system. These results have shown us how post-quantum algorithms can impact the handshake completion time, and, therefore, impact the establishment of real-world connections. In general, on the reliable network that we used, the different post-quantum TLS 1.3 handshake alternatives do not have a handshake completion time that is ostensibly different to a regular TLS 1.3 handshake. The only somewhat exception to this is KEMTLS, as the extra half or full round trip that is added does increase the completion time. For this reason, it is vital to think more in depth around KEMTLS-PDK, as it could reduce the completion time.

In this paper, we dive into the implementation of post-quantum algorithms in native Go language, adapt different handshake configurations and modify TLS extensions, and we explore the deployment of a test bed distributed network for enabling measurements. As a result, we developed a measurement framework that allows to perform transatlantic post-quantum TLS 1.3 connections for retrieving random numbers from a Drand network.

We remark that an important piece to achieve crypto-agility on the transition to post-quantum algorithms is the use of delegated credentials. They allowed us to advertise post-quantum KEMs or post-quantum signatures without generating new certificates or asking certificate authorities to support new algorithms.

Future work can involve increasing the number of connections tested, modifying the latency of the network, and testing with more post-quantum algorithms; we intend to continue our experiments. We further can extend our experiments to implement KEMTLS-PDK with mutual authentication, but more investigation is needed to determine the security requirements for encrypting the \(\mathtt {ClientCertificate}\) message. Another interesting topic for further investigation lies around on how to properly integrate post-quantum algorithms into certificate chains and experiment with certificate authorities.