Evaluating the performance of post-quantum secure algorithms in the TLS protocol
Abstract
Aim: The imminent advent of large-scale quantum computers within the next years is expected to highly affect the security of several cryptosystems that are now considered secure; this mainly holds for classical, long-established, public key cryptographic algorithms such as RSA and elliptic curve cryptography. Apparently, any security protocol that relies on such ciphers, including the transport layer security (TLS) protocol which constitutes a somewhat de facto standard for the security on the web, will not be considered secure in the post-quantum era. To alleviate the security risks stemming from quantum computing, several proposals have been submitted to the relevant procedure initiated by NIST towards evaluating and standardizing one or more quantum-resistant public-key cryptographic algorithms. This paper focuses on embedding post-quantum secure cryptographic algorithms into the TLS protocol to analyze its performance. More precisely, the paper aims to analyze whether this transition to post-quantum secure algorithms will have a significant impact on the user experience due to the possible increase of client--server communication times.
Methods: Having as the starting point several important works in the field, several experiments were carried out, using combinations of cloud and local virtual machines per case and considering all the post-quantum cryptographic algorithm finalists for key exchange from the third round of the ongoing NIST process, for various cryptographic as well as network parameters.
Results: Our results exhibit that, for key exchange in TLS, the best performance among the post-quantum secure ciphers is achieved by the Saber and CRYSTAL-Kyber variants for all security levels, regardless of the underlying computing power. The performance is comparable to that of the corresponding one achieved by a classical elliptic curve algorithm for key exchange for both RTT and packet loss ratio — i.e., the network parameters seem to have the same effect on post-quantum secure algorithms as in the case of a conventional elliptic curve algorithm. However, the effect of the network parameters on the performance is more crucial than the effect of the underlying chosen ciphers.
Conclusion: According to the experiments, we conclude that there exist very promising algorithms that could be utilized in TLS in the near future, which may behave even better than the conventional elliptic curve algorithms for key exchange. It should also be pointed out that NIST announced on 5 July 2022 (i.e., after the completion of our research experiments) that, for general encryption used when we access secure websites, the CRYSTALS-Kyber algorithm has been selected, having as one of its advantages the speed of operation. Hence, the results of our paper are fully in line with the progress of the NIST process. Taking into account that the NIST process is still ongoing (now in its fourth round) with the aim to select more algorithms, as well as that some algorithms may be standardized outside NIST, it becomes evident that our results provide very useful insights on performance aspects of the post-quantum secure algorithms.
Keywords
1. INTRODUCTION
Cryptography is a main information security mechanism, providing services to achieve several security goals such as confidentiality, data and entity authentication, and non-repudiation; however, it actually goes far beyond these goals and is able to provide solutions in terms of fulfilling legal requirements with respect to personal data protection and privacy [1]. To this end, cryptographic algorithms constitute core elements in network security protocols, including the prominent transport layer security (TLS) protocol [2], which constitutes a somewhat de facto standard for web security [3]. Indeed, TLS ensures: (i) entity authentication through digital certificates that are digitally signed (via a public key digital signature algorithm) by trusted certification authorities; (ii) confidentiality through encrypting (via the use of symmetric ciphers) the content of the communications, while the symmetric key for encryption/decryption is being securely exchanged via public key (i.e., asymmetric) cryptographic techniques; and (iii) data integrity, via ensuring that the encryption is authenticated (via message authentication codes or suitable modes of operations allowing for authenticated encryption). Any weakness in cryptographic algorithms affects the overall security of the protocol (see, e.g., [4] for a survey on such cryptographic threats for TLS).
The imminent advent of quantum computers will highly change the situation with regard to which cryptographic algorithms should be considered secure. Indeed, having large-scale quantum computers will allow executing algorithms that can efficiently solve difficult problems that cannot be solved today by contemporary conventional computing systems. More precisely, due to a quantum algorithm proposed by Peter Shor in 1994 [5], all commonly used public-key systems (including RSA, elliptic curve cryptography, and the Diffie–Hellman algorithm that is being used in the TLS protocol) will no longer be secure. Symmetric cryptography is also affected, but not to the same extent: there is a known quantum algorithm developed by Grover in 1996 [6] that suffices to decrease the security level of symmetric algorithms by up to half, which means that contemporary symmetric cryptographic primitives may still provide security to the post-quantum era by doubling, if needed, the key sizes (for symmetric ciphers) or the sizes of the message digests (for cryptographic hash functions).
Post-quantum cryptography refers to cryptographic algorithms which are secure under the assumption that the attacker has a quantum computer. Although the quantum computers that (are known to) exist currently are not large enough to violate the security of contemporary cryptography, it is essential to start considering the implementation of post-quantum cryptographic algorithms. The basic idea is to develop public-key algorithms whose security relies on a difficult mathematical problem that will remain difficult even if large-scale quantum computers become a reality. Hence, the US National Institute of Standards and Technology (NIST) launched in 2017 a process to standardize one or more quantum-resistant public-key cryptographic algorithms by collecting and evaluating submissions from the cryptographic community around the world [7]. This evaluation process is still ongoing, being in its third round of evaluation when the present research was conducted (and since July 2022, during the review phase of this paper, a fourth round has been initiated). The NIST process aims to find post-quantum secure public key algorithms that can be used either for digital signatures or to provide confidentiality, which in turn also incorporate secure key exchange (KEX) techniques as well as key encapsulation mechanisms (KEMs).
NIST evaluates the security strength of post-quantum secure algorithms on the basis of five categories which are characterized in terms of the equivalent strength of a symmetric primitive. In particular, according to NIST, a separate category for each of the following security requirements is defined (from the lowest strength to the highest strength):
● Level
● Level
● Level
● Level
● Level
Currently, the NIST competition is in the fourth round, as subsequently described.
During these years, the research community has also started exploring whether known public-key post-quantum secure cryptographic algorithms can be implemented in contemporary systems to enrich current security protocols by post-quantum secure ciphers. The actual motivation is that it is essential to start deploying quantum-safe solutions even before large-scale quantum computers become available. This is nicely explained by the famous Mosca equation (see, e.g., [8]): if
This paper focuses on the embedding of post-quantum secure cryptographic algorithms into the TLS protocol. More precisely, in this study, we performed a comprehensive set of experiments towards examining all possible post-quantum cryptographic algorithms for key exchange that are being analyzed by NIST, in terms of how efficiently they can be implemented into the TLS 1.3 protocol. More precisely, we studied all the finalists of the third round of the NIST competition, which was ongoing when this research was conducted. For our experiments, we used combinations of cloud and local virtual machines per case. The implementations of the algorithms were based on the Open Quantum Safe project [15] and our experiments constituted a more extended set of experiments with respect to those presented in [10], which formed the main basis for our research. Our ultimate goal was to derive conclusions on whether the transition to post-quantum secure algorithms will have a significant impact on the user experience due to the possible increase of client–server handshake communication times, for various network types that are being investigated — and this for each possible post-quantum secure cipher. Our results confirm that, in terms of performance, there are some very promising algorithms that could be utilized in the near future.
The paper is organized as follows. The basic background, with respect to both post-quantum cryptography and the TLS protocol, is given in Section
2. BACKGROUND
2.1. Post-quantum cryptography
The post-quantum public key cryptographic algorithms are mainly classified into one of the following categories:
● Code-based cryptography includes cryptographic algorithms whose security rests with the difficult problem of decoding an erroneous codeword that has been generated through an unknown error correcting code.
● Lattice-based cryptography includes cryptographic algorithms whose security relies on the difficulty of specific mathematical problems in the field of lattices. Such problems are the shortest vector problem (SVP), being NP-hard, which is related to the finding of the shortest non-zero vector within a lattice, as well as other similar lattice-based difficult problems such as the closest vector problem (CVP) and the shortest integer solution (SIS). An important lattice-based problem is the "learning with errors" (LWE) problem [16], which has security reductions to variants of SVP.
● Multivariate cryptography includes cryptographic algorithms whose security relies on the complexity of solving systems of multivariate equations, which have been demonstrated to be either NP-hard or NP-complete. Some of the most promising multivariate-based schemes are based on hidden field equations (HFE) (for a generic survey of mathematical problems in the field of multivariate cryptography, see [17]).
● Hash-based cryptography includes digital signature cryptographic algorithms whose security is based on known properties of cryptographic hash functions, such as pre-image resistance, second-order pre-image resistance, and collision resistance.
● Supersingular elliptic curve isogeny cryptography includes cryptographic algorithms whose security relies on the isogeny protocol for ordinary elliptic curves presented in [18] but enhanced to withstand the quantum attack detailed in [19].
In addition, there exist a few algorithms that are based on the security of zero-knowledge proofs. Such post-quantum cryptographic schemes are generalizations of hash-based cryptographic schemes, enriched by nice cryptographic properties of symmetric ciphers towards constructing zero-knowledge proofs.
The NIST standardization process for post-quantum public key cryptography provided its first outcomes at the end of its in third round in July 2022. In this round, seven algorithms, being called finalists, were reviewed for consideration for standardization. Four of them are being considered for encryption, key exchange, and key encapsulation mechanisms — namely Crystals-Kyber, NTRU, Saber (which are lattice-based cryptographic algorithms), and McEliece (which is code-based) — while the remaining three are being considered for digital signatures — namely Crystals-Dilithium and Falcon (which are lattice-based cryptographic algorithms) and Rainbow (which is based on multivariate cryptography). Moreover, during the third round, there were still eight alternates, spanning all possible categories of post-quantum cryptography, for which NIST stated that they may still potentially be standardized, although that most likely will not occur at the end of the third round. NIST expects to have a fourth round of evaluation for some of the candidates on this track. Several of these alternate candidates have worse performance than the finalists but might be selected for standardization based on high confidence in their security. Other candidates have acceptable performance but require additional analysis or work to inspire sufficient confidence in their security or security rationale. In addition, some alternates were selected based on NIST's desire for a broader range of hardness assumptions in future post-quantum security standards, their suitability for targeted use cases, or their potential for further improvement.
During the research conducted for this work and the drafting of this paper, the NIST process was in its third round, and thus, as subsequently described in detail, all the aforementioned finalists for key exchange and KEM were considered for our analysis. However, on 5 July 2022, NIST announced, at the end of this round, the first four quantum-resistant cryptographic algorithms — i.e., the "winners" of this round. These are:
● For general encryption, used when we access secure websites, the CRYSTALS-Kyber algorithm was selected.
● For digital signatures, often used when there is a need to verify identities during a digital transaction or to sign a document remotely, the CRYSTALS-Dilithium, FALCON, and SPHINCS+ (the last one is from the list of the alternates) were selected.
At the same time, NIST announced candidates for a fourth round of analysis — i.e., new algorithms are also expected to be selected for public key encryption and key encapsulation mechanism, in addition to the already chosen CRYSTALS-Kyber. The fourth round of the NIST process analyzes McEliece, BIKE, HQC, and SIKE (the last three had been alternatives during the third round). One reason that NIST intends to standardize some more algorithms is to increase the diversity in security assumptions in the case there is a breakthrough in attacks on structured lattices on which Kyber is based.
2.2. The TLS protocol
The TLS protocol, aims to ensure confidentiality as well as data and entity authentication. The latest version of the protocol is
The main procedures that the TLS protocol follows can be simply described by the following two phases: the first one is the connection setup (known as the handshake protocol), which is followed by steady-state communication (known as the record protocol). During the handshake protocol, the client and server negotiate to commonly decide on a number of parameters, such as the cryptographic algorithms that are to be used, as well as the relevant secret information from which the secret symmetric keys are being computed. After the setup phase, communication begins (record protocol), which is encrypted and authenticated through symmetric cryptographic primitives. The public key encryption is present in TLS at the handshake phase, since: (i) the client authenticates the server through its digital certificate, signed by a certificate authority; and (ii) it is being used so that the client and the server will commonly securely agree on the secret parameters for the symmetric authenticated encryption that is to be used in their communication that will follow.
There are no known practical weaknesses to TLS 1.3; all earlier versions of the protocol (including TLS 1.2) have some weaknesses, which are either inherent to the protocol's design (for some old versions) or may occur in the case of misconfigurations of the protocol (see [4] for a survey on these weaknesses). All versions, however, are not post-quantum secure, due to the existence of public-key ciphers such as RSA and elliptic curve (EC) cryptography.
3. RELEVANT PREVIOUS WORK
Embedding post-quantum secure ciphers in the TLS protocol has already been studied by many researchers, due to its high importance. Our research heavily relied on the work presented in [10], which presents a framework for running relevant experiments in TLS by emulating network conditions; more precisely, the testbed developed therein allows controlling variables such as link latency and packet loss rate, and then examining the performance impact of various post-quantum ciphers, both for key establishment and for digital signatures, based on the implementations from the Open Quantum Safe project [15]. As illustrated by the work in [10], the network latency hides most of the impact from algorithms with slow performance, while, for some of the algorithms studied therein, a packet loss rate above 3–5% seems to have an impact on the performance.
In [12], an assessment, through relative experiments, of the concurrent use of quantum-resistant key exchange and authentication in TLS 1.3, as well as SSH protocols, under realistic network conditions, is carried out. It is shown that there exist combinations of algorithms that offer handshake performance close to the current standards (a minimum slowdown of about
In parallel with our work, a nice study on the performance of the TLS based on post-quantum secure algorithms is presented in [21]; this work utilizes the liboqs software library [22] that was also used in our experiments, as subsequently described. A main outcome of this work is that Saber or CRYSTALS-KYBER for key exchange together with the FALCON signature seems to be a right combination for achieving the best performance, while in general lattice-based cryptography can be compared to RSA and elliptic curve cryptography, outperforming these classical schemes at higher security levels. The work in [21], however, does not take into account network parameters.
Another relative work in the field is found in [14], which focuses explicitly on the Google-Cloudflare CECPQ2 experiment for integrating post-quantum key-exchange algorithm into TLS 1.3 for developing a solution achieving higher performance; however, since this experiment utilizes a variant of one of the algorithms in the NTRU proposal, the proposed solution is also based on NTRU. Finally, an integration of the post-quantum KEM scheme Kyber for key establishment and the post-quantum signature scheme SPHINCS+ into the embedded TLS library (mbed TLS) is presented in [11], illustrating that embedded systems can (at least) act as post-quantum secure TLS clients, for those studied algorithms.
4. THE TESTING ENVIRONMENT
This section describes the experiments that were carried out to evaluate the performance of TLS
The testing environment consisted of one Google cloud device (Intel Xeon Cascade Lake n2-custom, with
To implement simulations that resemble realistic scenarios with regard to client–server connections, Linux network namespaces were used with the aim to develop different network entities, which in turn can be interconnected through virtual Ethernet. A network emulator was used to perform experiments for several probabilities of packet loss and for several round-trip times (RTTs).
The experiments are based on the following:
1. On a fork of the pq-tls-benchmark [23] which contains code and associated data for benchmarking post-quantum cryptography in TLS
2. On liboqs, an open source C library for quantum-resistant cryptographic algorithms from the Open Quantum Safe (OQS) Project [15], which provides an open-source implementation of the post-quantum secure algorithms for the TLS
More precisely, the aforementioned fork was used for the first two types of experiments, while for the third experiment, we used liboqs [22].
Our experiments included all the post-quantum secure ciphers for key exchange that were analyzed in the third round of the NIST evaluation procedure for all possible security levels; an exemption was the McEliece cipher for the first two experiments due to the large delay that occurred. Indeed, the McEliece cipher, as stated in the NIST Status Report on the Second Round of the Post-Quantum Cryptography Standardization Process [24], has a very large public key and, thus, does not fit well with Internet protocols as they are currently specified (although it is still an appealing choice for standardization, since it achieves the smallest ciphertext among alls KEMs and, thus, is preferable for some applications). We also examined hybrid versions of these ciphers — i.e., being combined with a classic elliptic curve cipher. Such versions are provided by the OQS project, such as, if quantum-safe public-key algorithms are used in conjunction with traditional public key algorithms, the derived implementation is at least no less secure than existing traditional cryptography[15]. More information on hybrid implementation for key exchange in TLS
The ciphers (for the key exchange) examined for the first two experiments, which utilize simulation of TLS connections, are shown in Table 1. Each cipher has several versions depending on its parameters to achieve a specific security level according to the NIST requirements; as it can be seen, a classical elliptic curve (EC) algorithm for key exchange was also considered — namely, the elliptic curve Diffie–Hellman (ECDH) algorithm, with the NIST Curve P-
The key exchange algorithms that were considered for the first two experiments
Algorithm | Security level |
Kyber | |
Kyber | L |
Kyber | L |
Kyber | L |
Kyber | L |
Kyber | L |
Kyber | L |
p | Hybrid |
p | Hybrid |
p | Hybrid |
p | Hybrid |
p | Hybrid |
p | Hybrid |
NTRU | |
NTRU-HPS- | L |
NTRU-HPS- | L |
NTRU-HRSS- | L |
NTRU-HPS- | L |
p | Hybrid |
p | Hybrid |
p | Hybrid |
p | Hybrid |
Saber | |
LightSaber | L |
Saber | L |
FireSaber | L |
p | Hybrid |
p | Hybrid |
p | Hybrid |
ECDH NIST P- | |
prime | Non post-quantum |
In all cases, the most recent version, TLS 1.3, of the protocol was used, whereas the data exchanged were encrypted by AES-256 GCM (Galois/Counter Mode). The server's authentication was based on the ECDSA certificate, signed with ECDSA P-
We also executed a third experiment focusing explicitly on the post-quantum algorithms without incorporating them into a TLS implementation. In this experiment, the McEliece variants were also taken into account.
4.1. Motivation for this work and relationships with similar works
This study aimed to exhaustively check all the finalists of the third round of the NIST competition for post-quantum ciphers with respect to their performance in TLS, focusing on key exchange, under varying network parameters and different underlying computing powers. To this end, as stated above, we mainly utilized the benchmark used in [10], which is considered a nice option for our experiments. Our analysis extended the analysis in [10] as follows:
● All the finalists for key exchange, for all possible security levels, were examined in our experiment, while in [10] the analysis focuses on only three instantiates for key exchange (SIKE p
● We additionally examined how the processing power affects the performance for fixed (optimal) network parameters. We also checked, as an additional aspect, the raw performance of each algorithm on different computing devices without using the TLS protocol.
5. RESULTS
This sections presents the results from our range of experiments that took place.
5.1. First experiment: Analysis for several network parameters
The first experiment aimed to study the time needed for a complete TLS handshake for several network parameters. To this end, based on the approach in [10], we created a pair of virtual Ethernets for client–server. In the client's network, a variation of the performance timing program
We subsequently set several RTTs, depending on the distance assumed between the client and server. Our hypotheses on the RTTs were based on those in [10]; as stated therein, four RTTs suffice to illustrate several realistic scenarios, from the optimum one (i.e., the smallest distance) to the worst one (i.e., with the largest distance). These four values of RTTs were
Additionally, we set several values for the packet loss ratio, from
For the cases of ciphers at the highest security level according to the NIST's classification, Figures 2–5 illustrate the diagrams for the time needed to complete the TLS handshakes, for all possible RTTs that were examined (from the best to the worst) and for each possible post-quantum key exchange algorithm. All results from all the experiments, for all security levels, are analytically presented in Figures 13–20 in the Appendix. From these results, we can get the following outcomes:
Figure 2. Results of the time to complete the TLS handshake, for post-quantum ciphers at the highest security level L
Figure 3. Results of the time to complete the TLS handshake, for post-quantum ciphers at the highest security level L
Figure 4. Results of the time to complete the TLS handshake, for post-quantum ciphers at the highest security level L
Figure 5. Results of the time to complete the TLS handshake, for post-quantum ciphers at the highest security level L
● The NTRU, Saber, and Kyber variants at the security level L1 behave better than the classical elliptic curve key exchange and their hybrid versions. Even for the few cases that they do not behave better, they are still very close to them, since the worst case that was monitored is a slow down by
● For all security levels, the aforementioned variants seem to behave generally better than their hybrid versions, regardless of the RTT or packet loss ratio.
● A packet loss ratio at
● The increase of packet loss ratio affects the ciphers at higher security levels L3 and L5 more than the ciphers at the L1 security level.
● For large values of RTT, which correspond to large distances between the client and server, we get that this large distance predominates with respect to the overall performance of completion of the handshake.
In principle, lightsaber seems to achieve the best performance for all network settings, but both Kyber and NTRU are also very close. This comparison was further examined by the subsequent experiments, which focused explicitly on the cryptographic procedure without considering network parameters.
5.2. Second experiment: Comparative study for two different devices under an optimum network
For our second experiment, we fixed the values of RTT and packet loss ratio to zero — i.e., to assume an ideal case with no network delays at all (an optimal network). Our aim was to evaluate the performance of the post-quantum ciphers for different devices with different computing capabilities — i.e., one high_core at
The setup of this experiment is shown in Figure 6.
The results are presented in a similar manner as in the first experiments — namely, we computed the medians for the handshake completion time as well the
Figure 7. Results of the handshake time, with zero RTT and packet loss ratio, for ciphers at L1 security level (the median time in ms).
Figure 8. Results of the handshake time, with zero RTT and packet loss ratio, for ciphers at L1 security level (the
Figure 9. Results of the handshake time, with zero RTT and packet loss ratio, for ciphers at L3 security level (the median time in ms).
Figure 10. Results of the handshake time, with zero RTT and packet loss ratio, for ciphers at L3 security level (the
Figure 11. Results of the handshake time, with zero RTT and packet loss ratio, for ciphers at L5 security level (the median time in ms).
Figure 12. Results of the handshake time, with zero RTT and packet loss ratio, for ciphers at L5 security level (the
Focusing on the L
Examining, for each post-quantum cipher, how the underlying computing power affects its performance, we get that, moving from the high core to the low core machine, NTRU becomes slower by about
Similar conclusions also hold for the L
The L5 ciphers also have similar behavior and the above conclusions are much more clear; here, Firesaber is about
For all security levels, and regardless of the underlying computing power (from those two that were used in our experiments), we get that the post-quantum algorithms are faster than their corresponding hybrid versions.
5.3. Third experiment: Raw performance
Our third experiment aimed to check the performance (execution time) of the key encapsulation ciphers based on measurements on the same device. Both local devices were also used to see the effect of the underlying computing power on the performance of each cipher. For the experiments, we utilized the application speed_kem lying in the repository of liboqs. More precisely, each application was run for
Any such post-quantum cipher actually implements a key encapsulation mechanism (KEM), which consists of three algorithms: the keygen function, which generates a public encapsulation key
All the results from this experiment are shown in Table 2. All the algorithms for security levels L
Time measurements for post-quantum KEM ciphers (the McEliece variants)
Algorithm | Mean time (ms) | Mean time (ms) | Percentage difference |
(Intel Core i7- 6700k @ | (Intel Core i5-82500k @ | between the two systems | |
Classic-McEliece-348864 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Classic-McEliece-348864f (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Classic-McEliece-460896 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Classic-McEliece-460896f (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Classic-McEliece-6688128 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Classic-McEliece-6688128f (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Classic-McEliece-6960119 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Classic-McEliece-6960119f (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Classic-McEliece-8192128 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Classic-McEliece-8192128f (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps |
Time measurements for post-quantum KEM ciphers (the Kyber variants)
Algorithm | Mean time (ms) | Mean time (ms) | Percentage difference |
(Intel Core i7- 6700k @ | (Intel Core i5-82500k @ | between the two systems | |
Kyber512 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Kyber512-90s (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Kyber768 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Kyber768-90s (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Kyber1024 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Kyber1024-90s (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps |
Time measurements for post-quantum KEM ciphers (the NTRU variants)
Algorithm | Mean time (ms) | Mean time (ms) | Percentage difference |
(Intel Core i7- 6700k @ | (Intel Core i5-82500k @ | between the two systems | |
NTRU-HPS-2048-509 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
NTRU-HPS-2048-677 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
NTRU-HRSS-701 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
NTRU-HPS-4096-821 (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps |
Time measurements for post-quantum KEM ciphers (the Saber variants)
Algorithm | Mean time (ms) | Mean time (ms) | Percentage difference |
(Intel Core i7- 6700k @ | (Intel Core i5-82500k @ | between the two systems | |
LightSaber-KEM (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
Saber-KEM (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps | |||
FireSaber-KEM (L | |||
Sizes (in bytes): Public key: | |||
keygen | |||
encaps | |||
decaps |
The results in Tables 2–5 illustrate the importance of the underlying computing power, in terms of measuring the performance of a cryptographic algorithm, since gains from about
Moreover, these measurements confirm the outcomes from the first two experiments, illustrating that Saber and Kyber achieve better performance than the remaining algorithms (with the light version of the Saber, at security level L
6. DISCUSSION
Combining the above results, it becomes evident that — as expected — the sizes of the key and the ciphertext highly affect the overall performance of a cipher and, thus, a higher security level of the cipher yields degradation in performance. This is particularly obvious for the McEliece cipher, which is an observation that was also pointed out by NIST. More precisely, the McEliece cipher seems to be not an option for classical contemporary systems. Moreover, the NTRU variants seem to also have not as good behavior as Saber and Kyber in terms of performance, even though the relevant key and ciphertext sizes are comparable with those of the other post-quantum secure ciphers.
Moreover, the results also verify that the network parameters also affect the overall performance to a high extent — and, actually, it is a more decisive factor for the overall performance than the underlying cryptographic algorithms that are being used.
In any case, we can conclude that there are several promising solutions for post-quantum key exchange algorithms that can be used in network security protocols such as the TLS, even in conventional contemporary systems. Such ciphers have comparable or, in some cases, even better performance than classical elliptic curve public key algorithms; interestingly, it seems that adopting a hybrid solution does not provide much gain in terms of performance compared to a fully post-quantum secure solution.
As a general conclusion, we can state that all the Saber variants — namely lightsaber, saber, and firesaber — as well as some variants of the Kyber — namely, kyber768, kyber90s768, kyber1024, and kyber90s1024 — could possibly be considered in terms of performance for adoption even for today's computing systems, since they exhibited nice performance properties for all sets of experiments that were carried out. It seems that there is also no need, from the performance point of view, to focus on hybrid implementations, since pure post-quantum secure ciphers seem to have better behavior. This general conclusion seems to remain valid regardless of the underlying computing power.
During the review phase of this paper, NIST completed its third round, as stated above. According to the relative status report that NIST issued [27], both KYBER and Saber are suitable for use on constrained devices, as each of these can be implemented (at least without protections against side-channel attacks) using less than
The conclusions derived from the present research are fully in line with the final output of the third round of the NIST competition, since indeed the CRYSTALS-Kyber algorithm chosen by NIST illustrated in our work very good performance (either the best or almost the best) for key exchange in the TLS protocol, whereas the performance benefits of Saber — as pointed out by NIST — are also clear. Moreover, the performance achieved by the CRYSTALS-Kyber is comparable with the classical contemporary public key implementations for the TLS protocol, and this comparison is not actually affected by network parameters.
7. CONCLUSIONS AND FUTURE RESEARCH
This study focused on analyzing the performance of public-key post-quantum algorithms in light of their possible use for key exchange in the prominent TLS protocol. Based on known results and existing software that has already been developed for research purposes, we carry out a more extended set of experiments, taking into account the list of third round finalists of the NIST's standardization process. The main outcome is that there exist differences among the various finalists with respect to their performance, and the main conclusion with regard to the fastest algorithms are in line with the final choice of NIST at the end of this round — namely the choice of CRYSTALS-Kyber as a standard. Moreover, starting from now, employing post-quantum secure solutions into contemporary applications and network security protocols seems to be a viable option. However, even for those algorithms that have not been standardized —i.e. they are not being evaluated anymore in the current fourth round of the NIST evaluation — the results are of importance, taking into account that it cannot be excluded that some of these schemes might be standardized outside the NIST, especially those for which NIST pointed out that they have low "cost" and do not raise (to our current knowledge) security issues. In this regard, it is interesting to recall that Chacha20, which is a secure symmetric cipher supported by TLS
This is a highly evolving research field; one should carefully monitor the progress in the NIST evaluation procedure and the related research. Indeed, at the beginning of August 2022, it was announced in a research paper (a pre-print version is currently public [28]) that SIKE, which is one of the four algorithms that are currently evaluated by NIST in the fourth round of evaluation (being one of the alternated algorithms in the third round), was cracked by using a computer running Intel Xeon CPU in 1 h.
It should be pointed out that our work focuses only on performance in the handshake phase of the TLS, having post-quantum secure algorithms for key exchange. Although known values of the sizes of the produced ciphertexts and keys are also being presented to allow a comparative study of these factors, we do not explicitly study relevant important parameters such as the bandwidth consumed by communication or the memory required. This could also be considered in future work, taking into account the relevant results announced by NIST. Moreover, the post-quantum digital signature algorithms should also be considered in the same context [such studies have already been performed, for some such algorithms, in several works (e.g., [10]), as described in Section
Another important aspect that needs to be considered in future research is to determine the behavior of post-quantum secure TLS implementations in restricted environments in terms of computing power and memory; to this end, it is important to focus on cases of IoT applications (e.g., on mobile devices, a Raspberry Pi, etc.) The current research illustrated that the differences in performance gains — among several post-quantum ciphers — seem to increase with the computing power, but such restricted environments have not been examined. Such research efforts have recently been started (see, e.g., [11]).
When dealing with an evaluation of ciphers' performance, it is also of importance to identify which underlying processes/computations are more "heavy", so as to focus appropriately on them in future research for algorithms optimization. This aspect was not studied here, and it constitutes an open research field.
Additionally, focusing on embedding post-quantum secure algorithms in other security protocols residing in lower network architecture levels, such as the IPsec, is also an interesting research area (see, e.g., [29]). More generally, focusing on post-quantum solutions in several existing protocols and infrastructures, such as the blockchain ecosystem [30], becomes an essential issue in ensuring the appropriate safeguards for long-term data protection.
DECLARATIONS
Acknowledgements
The authors would like to thank the anonymous reviewers for their very useful comments and suggestions, as well as for drawing our attention to some very recent research papers in the field, that helped to significantly improve the paper.
Authors' contributions
Made substantial contributions to conception and design of the study: Tzinos I, Limniotis K, Kolokotronis N
Set up simulation environments, performed simulations and provided figures and tables with results: Tzinos I
Data analysis and interpretation: Tzinos I, Limniotis K, Kolokotronis N
Writing the paper: Tzinos I, Limniotis K, Kolokotronis N
Availability of data and materials
Not applicable.
Financial support and sponsorship
None.
Conflicts of interest
All authors declared that there are no conflicts of interest.
Ethical approval and consent to participate
Not applicable.
Consent for publication
Not applicable.
Copyright
© The Author(s) 2022.
APPENDIX
All the results obtained from the first experiment are given in Figures 13–20.
Figure 14. Results of the handshake for the best RTT scenario (the
Figure 16. Results of the handshake for the moderate RTT scenario (the
Figure 18. Results of the handshake for the bad RTT scenario (the
REFERENCES
2. Rescorla E. The Transport Layer Security (TLS) Protocol Version 1.3.; 2018. Available from: https://datatracker.ietf.org/doc/html/rfc8446.
3. Felt AP, Barnes R, King A, et al. Measuring HTTPS adoption on the web. In: Kirda E, Ristenpart T, editors. 26th USENIX Security Symposium, USENIX Security 2017, Vancouver, BC, Canada, August 16-18, 2017. USENIX Association; 2017. pp. 1323–38. Available from: https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/felt.
4. Limniotis K, Kolokotronis N. Cryptography threats. In: Kolokotronis N, Shiaeles S, editors. Cyber-Secur. Threat. Actors, Dyn. Mitigation. Boca Raton, FL, USA: CRC Press; 2021. pp. 123–59.
5. Shor PW. Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994. IEEE Computer Society; 1994. pp. 124–34.
6. Grover LK. A Fast Quantum Mechanical Algorithm for Database Search. In: Miller GL, editor. Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996. ACM; 1996. pp. 212–19.
7. NIST. Post-Quantum Cryptography. Available from: https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization.
8. Mosca M. Cybersecurity in an era with quantum computers: will we be ready?; 2015. https://ia.cr/2015/1075. Cryptology ePrint Archive, Report 2015/1075.
9. Bos JW, Costello C, Naehrig M, Stebila D. Post-quantum key exchange for the tls protocol from the ring learning with errors problem. In: 2015 IEEE Symposium on Security and Privacy; 2015. pp. 553–70.
10. Paquin C, Stebila D, Tamvada G. Benchmarking Post-Quantum Cryptography in TLS; 2019. https://ia.cr/2019/1447. Cryptology ePrint Archive, Report 2019/1447.
11. Bürstinghaus-Steinbach K, Krauß C, Niederhagen R, Schneider M. Post-quantum TLS on embedded systems: integrating and evaluating kyber and SPHINCS+ with mbed TLS. In: Sun H, Shieh S, Gu G, Ateniese G, editors. ASIA CCS '20: The 15th ACM Asia Conference on Computer and Communications Security, Taipei, Taiwan, October 5-9, 2020. ACM; 2020. pp. 841–52.
12. Sikeridis D, Kampanakis P, Devetsikiotis M. Assessing the overhead of post-quantum cryptography in TLS 1.3 and SSH. In: Han D, Feldmann A, editors. CoNEXT '20: The 16th International Conference on emerging Networking EXperiments and Technologies, Barcelona, Spain, December, 2020. ACM; 2020. pp. 149–56.
13. Sikeridis D, Kampanakis P, Devetsikiotis M. Post-quantum authentication in TLS 1.3: A performance study. In: 27th Annual Network and Distributed System Security Symposium, NDSS 2020, San Diego, California, USA, February 23-26, 2020. The Internet Society; 2020. Available from: https://www.ndss-symposium.org/ndss-paper/post-quantum-authentication-in-tls-1-3-a-performance-study/.
14. Bernstein DJ, Brumley BB, Chen MS, Tuveri N. OpenSSLNTRU: Faster post-quantum TLS key exchange; 2021. https://ia.cr/2021/826. Cryptology ePrint Archive, Report 2021/826.
15. Stebila D, Mosca M. Avanzi R, Heys HM, editors. Post-quantum key exchange for the Internet and the Open Quantum Safe project. Springer; 2016. Available from: https://openquantumsafe.org.
16. Regev O. On lattices, learning with errors, random linear codes, and cryptography. In: Gabow HN, Fagin R, editors. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005. ACM; 2005. pp. 84–93.
17. Ding J, Yang BY. Multivariate public key cryptography. In: Bernstein DJ, Buchmann J, Dahmen E, editors. Post-Quantum Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg; 2009. pp. 193–241.
18. Rostovtsev A, Stolbunov A. Public-key cryptosystem based on isogenies; 2006. https://ia.cr/2006/145. Cryptology ePrint Archive, Report 2006/145.
19. Childs AM, Jao D, Soukharev V. Constructing elliptic curve isogenies in quantum subexponential time. J Math Cryptol 2014;8:1-29.
20. Raavi M, Wuthier S, Chandramouli P, et al. Security comparisons and performance analyses of post-quantum signature algorithms. In: Sako K, Tippenhauer NO, editors. Applied Cryptography and Network Security - 19th International Conference, ACNS 2021, Kamakura, Japan, June 21-24, 2021, Proceedings, Part Ⅱ. vol. 12727 of Lecture Notes in Computer Science. Springer; 2021. pp. 424–47.
21. Döring R, Geitz M. Post-quantum cryptography in use: empirical analysis of the TLS handshake performance. In: 2022 IEEE/IFIP Network Operations and Management Symposium, NOMS 2022, Budapest, Hungary, April 25-29, 2022. IEEE; 2022. pp. 1–5.
22. Github. liboqs; 2019. Available from: https://github.com/open-quantum-safe/liboqs.
23. Github. pq-tls-benchmark; 2019. Available from: https://github.com/xvzcf/pq-tls-benchmark.
24. NIST. Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process; 202O. NISTIR 8309. Available from: https://csrc.nist.gov/publications/detail/nistir/8309/final.
25. Mozilla. The telemetry portal; 2022. Available from: https://telemetry.mozilla.org/.
26. Github. pq-tls-benchmark; 2020. Available from: https://github.com/kalhas/pq-tls-benchmark.
27. NIST. Status report on the third round of the nist post-quantum cryptography standardization proces; 2022. NISTIR 8413. Available from: https://csrc.nist.gov/publications/detail/nistir/8413/final.
28. Castryck W, Decru T. An efficient key recovery attack on SIDH (preliminary version); 2022. https://eprint.iacr.org/2022/975. Cryptology ePrint Archive, Paper 2022/975. Available from: https://eprint.iacr.org/2022/975.
29. Gazdag S, Grundner-Culemann S, Guggemos T, Heider T, Loebenberger D. A formal analysis of IKEv2's post-quantum extension. In: ACSAC '21: Annual Computer Security Applications Conference, Virtual Event, USA, December 6 - 10, 2021. ACM; 2021. pp. 91–105.
Cite This Article

How to Cite
Tzinos, I.; Limniotis, K.; Kolokotronis, N. Evaluating the performance of post-quantum secure algorithms in the TLS protocol. J. Surveill. Secur. Saf. 2022, 3, 101-27. http://dx.doi.org/10.20517/jsss.2022.15
Download Citation
Export Citation File:
Type of Import
Tips on Downloading Citation
Citation Manager File Format
Type of Import
Direct Import: When the Direct Import option is selected (the default state), a dialogue box will give you the option to Save or Open the downloaded citation data. Choosing Open will either launch your citation manager or give you a choice of applications with which to use the metadata. The Save option saves the file locally for later use.
Indirect Import: When the Indirect Import option is selected, the metadata is displayed and may be copied and pasted as needed.
Comments
Comments must be written in English. Spam, offensive content, impersonation, and private information will not be permitted. If any comment is reported and identified as inappropriate content by OAE staff, the comment will be removed without notice. If you have any queries or need any help, please contact us at support@oaepublish.com.