Post-Quantum Cryptography Series

Perhaps you have heard of quantum key distribution, or perhaps you are curious as to what quantum computers with sufficient qubits and quantum error correction will mean to the confidentiality and integrity of global communication. Well, this series is dedicated to just these topics and more!

Part I: Forward Secrecy and Shor's Algorithm

In part I of this series, we will touch on TLS 1.3 vs TLS 1.2, namely in the asymmetric key exchange and authentication algorithms used, the concept of forward secrecy, the theoretical threat of Shor's algorithm to past and present SSL/TLS-secured session data, and the challenges facing the practical implementation of Shor's algorithm on quantum processors.

Transport Layer Security (TLS)

The present confidentiality and integrity of global communications are safeguarded by the implementation of an asymmetric key exchange system on servers and clients. Specifically, the TLS (Transport Layer Security) standard defines the format of and protocol for record exchange enabling the server and client to establish a shared encryption key, i.e. the session key, and afterwards verify the success of this process.

The latest version of TLS, TLS 1.3, specified in RFC 8446 in August 2018, narrows the asymmetric key exchange algorithms used to establish a shared session key to two: Diffie-Hellman Ephemeral Key Exchange (DHE) and its computationally more-efficient elliptic-curve variant (ECDHE), both of which support forward secrecy. The TLS 1.3-supported authentication algorithms, used by the server and, in select cases the client, to sign the records transmitted between them, include RSA, elliptic-curve Digital Signature Algorithm (ECDSA), and Edwards-curve Digital Signature Algorithm (EdDSA). TLS 1.3 is supported by all major browsers including Chrome, Firefox, Safari, Edge, and Opera.

The previous TLS standard, TLS 1.2, specified in RFC 5246 in August 2008, has been supported by the major browsers for years, and comprises a larger set of asymmetric key exchange algorithms. These include RSA, Diffie-Hellman Key Exchange (both static and ephemeral), and elliptic-curve Diffie-Hellman (both static and ephemeral), where the former and static implementations of the two latter methods do not support forward secrecy. The TLS 1.2 authentication algorithms include RSA, Digital Signature Algorithm (DSA), and elliptic-curve Digital Signature Algorithm (ECDSA). For a detailed article on why TLS 1.3 is a major improvement over TLS 1.2 (the reasons are many in addition to ensuring the forward secrecy of session data), please refer to this Cloudflare blog post.

Forward secrecy is the concept that should the session data be intercepted in transit and stored, and the server cryptographic data be compromised at some point in the future, no compromised information can be used to decrypt the session data. The reason is twofold: no secret server parameters used to establish the shared key with the client are stored. The only server key pair stored is the one used by the authentication algorithm to sign the server records sent to the client. Also, the session key itself is never transmitted in messages between the server and client. Instead, the server and client separately create secret session key establishment parameters (an integer or a public-private key pair, depending on whether Diffie-Hellman or elliptic-curve Diffie-Hellman is used) and employ them to establish a shared secret, without ever revealing classically computationally tractable information about each other's secrets. For an explanation of the mathematics behind Diffie-Hellman key generation (it is interesting, and not particularly complicated), see this Wikipedia article.

Quantum Computation and Shor's Algorithm

In 1994, Peter Shor published an algorithm that when run on a quantum computer with sufficient qubits and quantum error correction (quantum computers are notoriously noisy and weak) can demonstrably break the discrete logarithm problem and the prime factorization problem, both of which are special cases of the hidden subgroup problem for finite abelian groups. The cryptographic significance, of course, is that the security of Diffie-Hellman key exchange is based on the classical computational intractability of the discrete logarithm problem, and that of RSA on the classical computational intractability of the prime factorization problem.

In layperson's terms, this means that should a practical quantum computer be built, an effort that Google, IBM, and others are resolutely working towards, any SSL- or TLS-secured data transmitted over the Internet and captured at any point over the past decades of secure communication could potentially be converted to plaintext. All that would need to be done would be to run the algorithm using inputs taken from the key establishment phase of the SSL/TLS to derive either the client or server secret and regenerate the shared session key. For the case of Diffie-Hellman, the inputs would correspond to p and g, the publicly negotiated parameters, and x (mod p) or y (mod p), the numbers exchanged between server and client. The algorithm would then derive an array of possible values for r, the server secret, or s, the client secret, such that g^r ≡ x (mod p) or g^s ≡ y (mod p). Possible session keys S would then be computed by S = y (mod p)^r mod p or S = x (mod p)^s mod p, and the union of the sets would be iterated over the session data until one was proven to be successful in decryption.

The challenges to building a quantum computer of sufficient complexity to start making Shor's algorithm practical are presently many. Quantum processors have limited coherence time, or the time before the qubits inside the processor lose their state of superposition, rendering further computation impossible. A practical implementation of Shor's algorithm, one that would enable it to break 2048-bit RSA, would likely require at least 4,000 qubits and 100 million quantum logic gates, an engineering feat whose duration experts in the field disagree on. Some claim that such machines may be available in the coming decades, while others caution that the actual machines will appear much later.