Quantum Computing in TLS

Abstract

The rapid development of quantum computing is challenging the Transport Layer Security (TLS) protocol, the basic security layer for internet communications. Quantum computers will be able to crack traditional encryption algorithms, which could compromise communications protected by TLS.

This paper examines the impact of quantum computing on TLS and presents possible solutions to achieve quantum-secure communications.

Quantum computers can efficiently crack RSA encryption using the Shor algorithm and speed up ECC key search using the Grover algorithm. This means that quantum computers will be able to decipher the encryption of TLS connections and access the data being transmitted.

Several research projects are working on the development of quantum-safe encryption algorithms. Some promising solutions are post-quantum cryptography (PQC), quantum key distribution (QKD) and homomorphic encryption.

PQC algorithms are resistant to attacks from quantum computers. QKD guarantees key confidentiality, even against quantum computers. Homomorphic encryption allows encrypted data to be processed without first decrypting it.

The development and deployment of quantum-secure solutions is critical to preserve the security of future Internet communications. We are looking at this in terms of Transport Layer Security.[1]

Introduction

TLS, or Transport Layer Security, is a cryptographic protocol that enables secure communication over networks such as the internet.

Basically, it encrypts data between two communicating parties, preventing data from being intercepted or manipulated. TLS is an enhanced version of the Secure Sockets Layer (SSL) protocol and is widely used for secure communication between web browsers and servers, email, instant messaging and VoIP services.

TLS protocols offer a range of security mechanisms, including two-factor authentication and data integrity preservation. TLS thus plays a key role in digital security and the protection of user data in the online space.

TLS can be said to be secure on current classical computers, but modifications need to be made to deal with the increasingly publicised Quantum threat, as TLS also uses classical algorithms that are not prepared for Quantum attacks. To maintain secure communication channels in the quantum age, a proactive transition to post-quantum cryptography (PQC) is essential.

However, a complete shift to PQC requires establishing trust and ensuring robust implementation. Therefore, a hybrid approach is recommended as a temporary solution. This method involves running both traditional and PQC algorithms concurrently during key exchange and signature generation. This creates both classical and post-quantum versions of the exchanged keys/signatures. By combining these outputs, the communication becomes resistant to attacks, both present and those enabled by future quantum computers.

This hybrid approach offers a practical and secure solution until the cryptographic community fully embraces PQC algorithms. By proactively transitioning to a hybrid model, we can ensure the continued security of TLS and safeguard online communication in the quantum era. [2]

Post-Quntum computing in TLS

Many efforts to upgrade TLS for protection against quantum computers are tied to NIST’s work on establishing post-quantum cryptography standards. This is mainly because protecting TLS from quantum threats is a key motivator for developing new cryptographic methods that are safe from quantum attacks.

Right now, most of the proposed upgrades for TLS involve using new digital signatures and key hiding methods that were part of the NIST project started in 2016. From the initial 82 proposals, 15 were selected for further evaluation. This shows the importance of NIST’s standards in creating TLS solutions that are secure against the future threat of quantum computers.

Authentication in TLS

TLS authentication operates by having the client verify the server’s SSL certificate with the issuing certificate authority. This process ensures that the server is indeed who it claims to be, confirming that the client is engaging with the legitimate owner of the domain.

We distinguish between two types of post-quantum authentication in TLS:

• Purely Post-Quantum Solutions: These rely solely on post-quantum cryptography for authentication.
• Hybrid Post-Quantum Solutions: These combine traditional and post-quantum cryptography for a smoother transition.

Purely Post-Quantum Solutions

The study focuses on replacing classical TLS signature schemes with post-quantum algorithms, classified according to the hardness assumptions of post-quantum signatures.

Examination of hash-based signatures such as XMSS, Picnic, and SPHINCS+ highlights the limitations of XMSS due to its stateful nature and the stateless nature of Picnic, despite being excluded from the NIST competition. SPHINCS+, as the sole stateless hash-based signature scheme intended for NIST standardization, is limited in TLS usage due to its large signature size and slow operation.

Rounding out the analysis are lattice-based signatures like Dilithium, Falcon, and qTesla, evaluated for their applicability and performance in TLS, with Dilithium and Falcon undergoing NIST standardization. These schemes significantly differ from classical algorithms in size and computational efficiency, with Falcon particularly standing out due to its large size and specialized hardware requirements. Despite participating in the NIST competition, qTesla did not progress further due to concerns over security/efficiency balance.

Multivariate-based signatures like GeMSS, Rainbow, and MQDSS are also examined for their TLS handshake application, though these schemes were later found to be compromised. While offering competitive or better performance compared to hash-based and lattice-based algorithms, uncertainty surrounds them due to security concerns.

Hybrid Post-Quantum Solutions

Hybrid post-quantum authentication leverages the simultaneous utilization of classical and post-quantum signature schemes, thereby amalgamating traditional cryptographic methods against quantum threats.

Open Quantum Safe (OQS) project extended OpenSSL to facilitate this, treating classical and post-quantum keys and signatures as one within TLS. Implemented for TLS 1.3, it combines RSA/ECDSA with Dilithium/Falcon/SPHINCS+ algorithms.

Testing indicates that hybrid authentication roughly takes 1.2−2 times longer than purely post-quantum methods, varying with the efficiency ratio between classical and post-quantum signatures. For instance, a TLS handshake combining RSA + Dilithium and ECDHE + Kyber takes 30 ms compared to 18 ms for a purely post-quantum handshake using Dilithium and Kyber. [3]

Key-Exchange in TLS

TLS key exchange facilitates the use of a cryptographic protocol between two entities by enabling the exchange of cryptographic keys. For instance, an TLS handshake generates a symmetric session key that is used before sending an encrypted message.

While there’s only one general purely post-quantum key exchange method, hybrid post-quantum key exchange offers several approaches.

Purely Post-Quantum Key Exchange

The exploration of Purely Post-Quantum Key Exchange within TLS primarily revolves around utilizing Key Encapsulation Mechanisms (KEMs) as alternatives to classical Diffie-Hellman (DH) key exchange, with extensive literature spanning both TLS 1.2 and TLS 1.3 protocols.

These KEM-based approaches involve steps where the client generates an ephemeral KEM key pair, shares the public key with the server, and then engages in an encapsulation and decapsulation process to establish a shared secret, aligning closely with the traditional DH flow.

The primary challenge in this realm is to identify cryptographic solutions that strike a balance between quantum security and performance metrics such as speed and size, as evidenced by the comprehensive analysis of various KEMs’ characteristics, including lattice-based, code-based, and isogeny-based schemes, each with distinct security assumptions and performance profiles. Notably, KEMs like Kyber have demonstrated comparable performance to classical key exchange protocols like ECDHE, while others like FrodoKEM exhibit higher computational overhead albeit with potentially higher security assurances, leading to ongoing considerations regarding their practical viability within TLS.

Hybrid Post-Quantum Key Exchange

One possible method runs classical and post-quantum algorithms in parallel, combining their key elements. This approach has been extended from TLS 1.2 to TLS 1.3 and demonstrates a practical balance between enhanced security and performance, with negligible impacts under ideal conditions.

The second method, the separation approach, transports classical and post-quantum keys distinctly within TLS, modifying existing structures for clearer differentiation. This has been applied to both TLS 1.2 and 1.3, allowing for a more organized integration of hybrid keys.

The third, a robust hybrid method, employs multiple post-quantum algorithms alongside classical ones, aiming to further minimize vulnerabilities. While conceptually offering the highest security, its practical performance implications, particularly as the number of algorithms increases, remain less explored.

kép

Despite some performance considerations, particularly in challenging network environments, these strategies offer a promising path towards future-proofing cryptographic practices. [4], [5], [6]

OpenSSL

OpenSSL, an open-source implementation of the Transport Layer Security (TLS) protocol, is working with the Open Quantum Safe project to incorporate post-quantum cryptography into versions TLS 1.2 and 1.3. This collaboration has produced a version of OpenSSL that integrates quantum-resistant key exchange and signature algorithms, specifically including FrodoKEM, SIKE for key exchange, and Picnic, qTESLA for signatures.

These enhancements are intended for prototyping and research purposes, aiming to evaluate the effectiveness of quantum-resistant cryptographic methods. [7]

References

[1]       Microsoft – Post-Quantum TLS, https://www.microsoft.com/en-us/research/project/post-quantum-tls/
[2]       Cloudflare – ,,What is TLS (Transport Layer Security)?”,  https://www.cloudflare.com/learning/ssl/transport-layer-security-tls/
[3]       D. L. Weller. 2020. Incorporating Post-Quantum Cryptography in a Microservice Environment. https://rp.os3.nl/2019-2020/p13/report.pdf.
[4]       Dimitrios Sikeridis, Panos Kampanakis† , Michael Devetsikiotis –  Post-Quantum Authentication in TLS 1.3: A Performance Study  , Jan 2020, USA, https://eprint.iacr.org/2020/071.pdf
[5]       Nouri Alnahawi, Johannes Müller, Jan Oupický, Alexander Wiesmaier–  SoK: Post-Quantum TLS Handshake  , 2023, Germany – Luxembourg, https://eprint.iacr.org/2023/1873.pdf
[6]       Xiphera – How does Post-Quantum Cryptography affect the TLS protocol? , https://xiphera.com/how-does-post-quantum-cryptography-affect-the-tls-protocol/
[7]       OpenSSL – OpenSSL project roadmap (OpenSSL 3.3) , https://www.openssl.org/roadmap.html