Hybrid Post-Quantum Key Encapsulation Methods (PQ KEM) for Transport Layer Security 1.2 (TLS)

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 6 March 2022.¶

Copyright Notice

Copyright (c) 2021 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.¶

Table of Contents

2. Key Exchange Algorithms

This document introduces two new hybrid-based key exchange methods for TLS. They use ECDHE with either BIKE, Kyber or SIKE in order to compute the TLS premaster secret. The master secret derivation is augmented to include the ClientKeyExchange message. The derivation of the encryption/MAC keys and initialization vectors is independent of the key exchange algorithm and not impacted by the introduction of these hybrid key exchanges. While this specification only defines the use of a PQ KEM hybrid key exchange with BIKE, Kyber or SIKE, it is specifically designed so that it can be easily extended to include additional PQ KEM methods.¶

The table below summarizes the new hybrid key exchange schemes.¶

These schemes are intended to provide quantum-safe forward secrecy.¶

 Client                                        Server
 ------                                        ------

 ClientHello          -------->
                                          ServerHello
                                          Certificate
                                    ServerKeyExchange
                                 CertificateRequest*+
                      <--------       ServerHelloDone
 Certificate*+
 ClientKeyExchange
 CertificateVerify*+
 [ChangeCipherSpec]
 Finished             -------->
                                   [ChangeCipherSpec]
                      <--------              Finished

 Application Data     <------->      Application Data

      * message is not sent under some conditions
      + message is not sent unless client authentication
        is desired

Figure 1 shows the messages involved in the TLS key establishment protocol (aka full handshake). The addition of hybrid key exchanges has direct impact on the ClientHello, the ServerHello, the ServerKeyExchange, and the ClientKeyExchange messages. Next, we describe each hybrid key exchange scheme in greater detail in terms of the content and processing of these messages. For ease of exposition, we defer discussion of the optional extension for specifying the parameters supported by an implementation until Section 4.¶

3. Hybrid Premaster Secret

This section defines the mechanism for combining the ECDHE and [KEM] secrets into a TLS 1.2 [RFC5246] pre-master secret. In the hybrid key exchange, both the server and the client compute two shared secrets: the previously defined ECDHE shared secret Z from RFC 8422, and another shared secret K from the underlying PQ key encapsulation method.¶

Form the premaster secret for ECDHE_[KEM] hybrid key exchanges as the concatenation of the ECDHE shared secret Z with the KEM key K to form the opaque data value premaster_secret = Z || K.¶

4. TLS Extension for Supported PQ KEM Parameters

A new TLS extension for post-quantum key encapsulation methods is defined in this specification.¶

This allows negotiating the use of specific PQ KEM parameter sets during a handshake starting a new session. The extension is especially relevant for constrained clients that may only support a limited number of PQ KEM parameter sets. They follow the general approach outlined in RFC 5246; message details are specified in Section 5. The client enumerates the BIKE, Kyber and SIKE parameters it supports by including the PQ KEM extension in its ClientHello message.¶

A TLS client that proposes PQ KEM cipher suites in its ClientHello message SHOULD include this extension. Servers implementing a PQ KEM cipher suite MUST support this extension, and when a client uses this extension, servers MUST NOT negotiate the use of a PQ KEM parameter set unless they can complete the handshake while respecting the choice of parameters specified by the client. This eliminates the possibility that a negotiated hybrid handshake will be subsequently aborted due to a client's inability to deal with the server's PQ KEM key.¶

The client MUST NOT include the PQ KEM extension in the ClientHello message if it does not propose any PQ KEM cipher suites. Additionally, the client MUST NOT include parameters in the PQ KEM extension for PQ KEM cipher suites it does not propose. That is, if a client does not support BIKE, it must not include the BIKE parameters in the extension, similarly for Kyber and SIKE. A client that proposes a PQ KEM scheme may choose not to include this extension. In this case, the server is free to choose any one of the parameter sets listed in Section 5. That section also describes the structure and processing of this extension in greater detail.¶

In the case of session resumption, the server simply ignores the Supported PQ KEM Parameters extension appearing in the current ClientHello message. These extensions only play a role during handshakes negotiating a new session.¶

5. Data Structures and Computations

This section specifies the data structures and computations used by PQ KEM hybrid-key agreement mechanisms specified in Sections 2, 3, and 4. The presentation language used here is the same as that used in TLS 1.2 [RFC5246].¶

enum {
    pq_kem_parameters(0xFE01)
  } ExtensionType;

enum {
    SIKE-P434-R3 (19),
    SIKE-P503-R3 (20),
    SIKE-P610-R3 (21),
    SIKE-P751-R3 (22),
    BIKE-L1-R3(25),
    BIKE-L3-R3(26),
    BIKE-L5-R3(27),
    KYBER-512-R3 (28),
    KYBER-512-90s-R3 (29)
  } NamedPQKEM (2^16-1);

struct {
    NamedPQKEM pq_kem_parameters_list <1..2^16-1>
  } PQKEMParametersExtension;

FE 01 00 08 00 06 00 13 00 19 00 20

struct {
    opaque public_key <1,...,2^24 - 1>;
  } PQKEMPublicKey;

struct {
    NamedPQKEM      named_params;
    PQKEMPublicKey  public;
  } ServerPQKEMParams;

struct {
    ServerECDHParams      ecdh_params;
    ServerPQKEMParams     pq_kem_params;
    Signature             signed_params;
  } ServerKeyExchange;

digitally-signed struct {
    opaque              client_random[32];
    opaque              server_random[32];
    ServerDHParams      ecdh_params;
    ServerPQKEMParams   pq_kem_params;
  } Signature;

struct {
    opaque ciphertext <1,..., 2^24 - 1>;
  } PQKEMCiphertext;

struct {
    ClientECDiffieHellmanPublic    ecdh_public;
    PQKEMCiphertext                ciphertext;
  } ClientKeyExchange;

master_secret[48] = TLS-PRF(secret, label, seed)

6. Cipher Suites

The table below defines new hybrid key exchange cipher suites that use the key exchange algorithms specified in Section 2 (Section 2).¶

The key exchange method, signature algorithm, cipher, and hash algorithm for each of these cipher suites are easily determined by examining the name. Ciphers and hash algorithms are defined in RFC 5288.¶

7. Security Considerations [DRAFT]

The security considerations in TLS 1.2 [RFC5246] and RFC 8422 apply to this document as well. In addition, as described in RFC 5288 and RFC 5289, these cipher suites may only be used with TLS 1.2 or greater.¶

The description of a KEM is provided in Section 2.1. The security of the KEM is defined through the indistinguishability against a chosen-plaintext (IND-CPA) and against a chosen-ciphertext (IND-CCA) adversary. We are focused here on the IND-CPA security of the KEM. As a result, implementations MUST NOT use a KEM key more than once, as reusing keys with IND-CPA KEMs can result in chosen ciphertext attacks like the GJS attack against BIKE [GJS].¶

In the IND-CPA experiment of KEMs, an oracle generates keys (sk, pk) with KeyGen(), computes (c, K) with Encaps(pk), and draws uniformly at random a value R from the key space, and a random bit b. The adversary is an algorithm A that is given (pk, c, K) if b=1, and (pk, c, R) if b=0. Algorithm A outputs a bit b' as a guess for b, and wins if b' = b.¶

All of the cipher suites described in this document are intended to provide forward secrecy. The hybrid key exchange mechanism described in this specification achieves forward secrecy when all ephemeral keys are single-use. This specification requires single-use PQ KEM keys, so ephemeral ECDH keys SHOULD also be single-use so that forward secrecy is achieved.¶

8. IANA Considerations

This document describes three new name spaces for use with the TLS protocol:¶

To Appear¶

9. Acknowledgements

This specification is based on ideas discussed with Ian Goldberg, Michele Mosca, Douglas Stebila and William Whyte during preparations for the first ETSI-IQC Quantum Safe Cryptography Workshop in 2013. The specification was developed through collaboration on the open source s2n project with Nicholas Allen, Nir Drucker, Shay Gueron, Andrew Hopkins, Colm MacCarthaigh and Alex Weibel.¶

Appendix A. Additional Stuff

This becomes an Appendix.¶

Authors' Addresses