Post-Quantum Cryptography Series

Part I: Forward Secrecy and Shor’s Algorithm

In part I of this series, we will touch on TLS1.3 vs TLS1.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, TLS1.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 TLS1.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). TLS1.3 is soon to be supported by all major browsers– Chrome, Firefox, Safari, and Opera have all begun to support TLS1.3 in their latest desktop and native versions, with Edge and Internet Explorer intending to add support in new releases.

The previous TLS standard, TLS1.2, specified in RFC 5246 in August 2008, has been supported by the major browsers for nearly ten 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)– the former and static implementations of the two latter methods not supporting forward secrecy. The TLS1.2 authentication algorithms include RSA, Digital Signature Algorithm (DSA), and elliptic-curve Digital Signature Algorithm (ECDSA). For a detailed article on why TLS1.3 is a major improvement over TLS1.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-Helman 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 (pdf) that when run on a quantum computer with sufficient qubits and quantum error correction (quantum computers in 2019 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 Berkeley, California-based Rigetti Computing among others are resolutely working towards, any SSL- or TLS-secured data transmitted over the Internet and captured at any point over the past two-and-a-half decades of secure communication, could be at the touch of a key, 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. In 2019, quantum processors have a coherence time of only 100 microseconds, or the time before the qubits inside the processor lose their state of superposition, rendering further computation impossible. The number of qubits contained inside of such processors is around 128. For a closer look into the current state of current quantum computers, please refer to this article.

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 claiming that such machines may be available in twenty to thirty years, while others cautioning that major steps towards the construction of such machines should be made within our lifetime, and that the actual machines will appear much later.