Quantum-proofing the Transport Layer Security (TLS) protocol
In a previous post, I argued that quantum computers are a threat to encryption only when the average time to decrypt is shorter than a message's lifetime. In this post, I am going to use that principle to determine how we can quantum-proof the security handshake that governs nearly all Internet traffic, known as the Transport Layer Security (TLS) protocol.
The TLS handshake
TLS is a security protocol used between a client and server at the TCP level (note: information can also be secured at the application level — with programs such as PGP, which offers end-to-end encryption — and the IP level — through IPsec). It was first developed in 1995 under the name Secure Socket Layer (SSL) until it became an open standard in 1999 and renamed to TLS 1.0. Since then, it has undergone three major updates, with TLS 1.3 being the most recent version (that still has yet to be deployed everywhere). Every HTTPS connection is secured through some version of the TLS protocol.
TLS is made up of two major parts: 1) the handshake protocol used to establish a secure connection by agreeing on primitives and creating secret keys; 2) the record protocol which uses the session keys for providing confidentiality and integrity of the session information. There are also cipher change and alert protocols, but they play play a minor role in TLS and only arise in edge cases. Let's look at how the handshake works between a client and server wishing to establish a secure connection.
Step 1: Client and server agree on TLS version and a cipher suite
To begin, the client sends a request to the server (dubbed "hello_client") that contains: the most recent TLS version they support, the encryption algorithms they support in order of preference (known as the cipher suite), the session ID, and a 256-bit nonce to prevent replay attacks. The server sends back a declaration of the key exchange method to be used, the algorithms to be used for authentication and encryption, and its own nonce.
Step 2: Server authenticates to the client
The next step is for the server to prove to the client that it is who it claims to be. To do this, the server sends the client their public key signed by a certificate authority. The server can also request that the client do the same, but this is not very common, as most clients do not have a public key signed by a certificate authority.
Step 3: Master secret key (MSK) is generated for the session
What happens next is a Diffie-Hellman key exchange to generate the pre-master secret key (pre-MSK), assuming the agreed-upon TLS version is 1.3. In previous versions, the client could reply with a pre-MSK encrypted with the server's public key using RSA, but let's assume for the time being that both parties support TLS 1.3.
For anyone unfamiliar with the original Diffie-Hellman key exchange, it works in the following way:
Server randomly selects a secret key, a, from a multiplicative group on the approved TLS 1.3 list. They exponentiate using a generator, g, for that group and their secret key. The value g^a is sent over to the client, along with the server nonce.
The client does the same thing with a randomly selected key, b, and sends g^b as well as their nonce over to the server.
Both parties calculate g^(ab), which becomes the pre-MSK.
The security assurance provided by the original formulation of the Diffie-Hellman key exchange is three-fold. First, it is hard to recover x from g^x (this is known as the hardness of the discrete-log problem). Second, it is hard to compute g^(xy) given g^x and g^y (this known as the computational Diffie-Hellman assumption). Finally, it is hard to distinguish g^(xy) from g^z for any z in the same group as x and y (this is the decisional Diffie-Hellman assumption).
This is useful, but not sufficient for TLS 1.3 standards. We also require forward secrecy, which is the requirement that a future compromise in the either party's private key does not compromise any previous session keys. This can be ensured by employing an ephemeral Diffie-Hellman (DHE) key exchange; in other words, a private key is not used more than once. Elliptic Curve Diffie Hellman (ECDHE) is also valid here so long as it is ephemeral.
But DHE does not provide authentication on its own since a new private key is used each session and neither party is able to verify if that the key they receive is from the intended party. Because of this, DHE requires a second authentication step, which can be completed using either RSA or Elliptic Curve Digital Signature Algorithm (ECDSA). Currently, the three approved DHE key exchange methods for TLS 1.3 are: DHE-RSA, ECDHE-RSA, and ECDHE-ECDSA. Pre-shared keys can also be used to authenticate, but for the sake of this exercise we ignore them because they are symmetric.
The master secret key (MSK) is then generated using HKDF (a type of key derivation function that uses hash-based message authentication codes) with the pre-MSK and both nonces as input. The MSK can then theoretically be used in any TLS 1.3-approved block or stream cipher algorithm, but in practice it will most likely be used in AES GCM.
Step 4: The entire conversation is authenticated
Finally, after the exchange is complete, the client sends a message authentication code (MAC) of the transcript and the server replies with a MAC of the transcript + client MAC. This is to ensure data integrity and prevent downgrade attacks. In previous versions, the MAC could be generated using HMAC-MD5 or HMAC-SHA256, but these were not approved for TLS 1.3. The only algorithm that has been approved thus far is AEAD.
What is the threat posed by quantum computing?
A quantum-capable adversary can choose between three different attack vectors here:
Break the key exchange algorithm and learn about the secret keys of both parties, which will let you generate the MSK for the session;
Break the block cipher algorithm outright and learn the content of the exchange; or
Break the MAC algorithm by finding a collision, creating the opportunity for a downgrade attack.
To determine which attack vector would yield the most success, let's recall the National Academies of Sciences' estimate for how long it would take a quantum computer to break certain encryption standards.
Based purely on these numbers, it seems like the symmetric encryption and hashing parts of the TLS handshake are already quite robust against a quantum computer. It is a tad unlikely that information contained within a session will remain sensitive for 10^7 or 10^12 years. Even when we assume these estimates are several orders of magnitude off, we can be confident that they will probably not be broken by a quantum computer in any reasonable amount of time. If there is any part of the handshake that is at risk, then it is wherever asymmetric encryption is used. For TLS 1.3, this means we need to ensure the key exchange is quantum-resistant.
Let's assume Eve is quantum-capable. The concern here is how long it takes for Eve to determine the pre-MSK (and subsequently the MSK for a session) by solving the discrete-log problem. This is the security assumption that a quantum computer breaks: the hardness of the discrete-log problem and its variant for elliptic curves. So what does that attack look like?
If Eve is a good eavesdropper, then she will have a copy of g^a, g^b, and the MSK-encrypted ciphertext of the client-server exchange. She will also have knowledge of g and the key derivation function used to generate the MSK because these are public. So all Eve needs to do is find a and b so she can get g^(ab). This will be completed on the order of hours based on the NAS estimates above. All that is left is to generate the session MSK and decrypt the ciphertext she recorded. Within hours of the original exchange, a quantum-capable Eve will know the contents of the exchange. If the information contained within the session is sensitive to either party for days or months after the initial exchange, then this poses a real security threat.
Changing the handshake
It is evident that the way to defend against a quantum-capable Eve is by changing to a key exchange algorithm that does not rely on the hardness of the discrete-log problem. Let's go through a few candidates that might fit the bill.
Quantum Key Exchange
What if we just made the key exchange part of the TLS handshake completely quantum? The value in doing so is that it becomes incredibly easy to detect an eavesdropper between the client and server because the mechanism for doing so is baked into the properties of quantum mechanics. Wikipedia has a good primer on how this is accomplished for the BB84 and E91 protocols. QKD on its own is still susceptible to man-in-the-middle attacks because neither the client nor the server would be able to distinguish Eve's qubit from the rest of them. So, if it is to be deployed, it would need to be paired with some form of authentication.
One of my main concerns with this approach is that the key exchange rate may be too low. Internet traffic is only going to increase more and more and QKD as of right now is the solution that offers the lowest rate of key exchange. However, a 2016 proposal from Jeff Shapiro's group at MIT has shown promise in achieving high data rates (Gbps level) for QKD using optical amplifiers, something no other protocols have been able to do before.
NIST is currently in the process of fielding and assessing submissions from security teams who believe they have developed a robust post-quantum key exchange algorithm. The second round results of this competition were announced in August 2019 and it seems like the most common type of submission is one that employs lattice-based encryption and relies on learning with errors. The learning with errors security hardness assumption is powerful because there does not yet exist a quantum algorithm that can break it in the same way Shor's algorithm breaks the discrete-log problem. Nevertheless, these algorithms will be slower than a DHE exchange because they are more computationally intensive.
Kerberos is an authentication service for establishing a shared key between the client and server that is approved by a single authority. This video explains how it works in a very methodical way. The power of Kerberos is that shared keys are used for encryption and decryption throughout the entire process, which provides information-theoretic security, but it is unclear if this solution is scalable to something as ubiquitous as the TLS handshake. It requires every client and server of the system to be a trusted member. Another issue is that key management and session approval all go through a single key distribution authority, meaning the system has a single point of failure. If that authority goes offline for whatever reason, then clients and servers connected to the system can no longer authenticate themselves to others.
The danger of a quantum computer is in its ability to efficiently solve the discrete-log problem using Shor's algorithm. In order to quantum-proof the TLS handshake, we need to ensure that no part of the process relies on the security assumption that this problem is hard to solve. This means that we need to find a substitute for the Diffie-Hellman key exchange part of the handshake. I have presented three different ways of authenticating and creating a shared session key between a client and server that would be able to secure information at the TCP level in a post-quantum digital world.