Using (post-quantum) KEMs in TLS 1.3

The new TLS 1.3 standard [1] does not yet provide any support for post-quantum algorithms. In this blog post we’ll be talking about how we could negotiate a post-quantum key exchange using a (post-quantum) Key Encapsulation Mechanism (KEM). In the NIST Standardisation effort [2], many KEMs are currently under consideration.

What is a KEM

A KEM is a set of functions that can be used to obtain a symmetric encryption key from asymmetric keys. It should provide the following functions:

• $\operatorname{KeyGen}$: Generates a public key $pk$ and a private key $sk$
• $\operatorname{Encapsulate(pk)}$ Returns symmetric key $K$ and ciphertext $ct$.
• $\operatorname{Decapsulate}(sk, ct)$: Returns $K$

This can be used, for example in the following protocol.

After exchanging these messages, $A$ and $B$ will have derived the same key, much like the classic Diffie-Hellman key exchange.

The TLS 1.3 handshake protocol

The typical TLS 1.3 handshake has the client and the server include key shares in the first messages. These key shares, typically ephemeral ECDH public keys, are used to compute a shared secret key. The server can already do that in the second message. This allows very early submission of data.

However, if we want to use KEMs, we run in the problem that the client can not send the encrypted ciphertext $ct$ as it does not have the public key of the server. This prevents us from using KEMs in this setting of TLS.

Using an extra round trip

TLS allows us to let the server pick the key shares we’re going to use, at the cost of an extra round trip. We can do this by sending a ClientHello that does not contain any key shares, but indicates support for the KEM. The server will then send HelloRetryRequest, indicating the server should try again. In the HelloRetryRequest, it will include the public key we need.

This leads to the following protocol.

Of course, this extra round trip increases latency. In fact, one of the main improvements of TLS 1.3 over TLS 1.2 was the getting rid of this extra round trip. The client can’t prepare their messages before the server replied with the HelloRetryRequest either. This is why we think it’s worth it to look into how we can get KEMs into TLS while preserving the single-round trip protocol.

References

1. Rescorla, Eric: The Transport Layer Security (TLS) Protocol Version 1.3, https://rfc-editor.org/rfc/rfc8446.txt, (2018).

2. National Institute for Standardization of Technology: Round 1 submissions - post-quantum cryptography, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions, (2017).

3. Langley, Adam: Post-quantum confidentiality for TLS, https://www.imperialviolet.org/2018/04/11/pqconftls.html, (2018).