| Internet Engineering Task Force | M. Campagna |
| Internet-Draft | E. Crockett |
| Intended status: Experimental | AWS |
| Expires: September 7, 2020 | March 6, 2020 |
Hybrid Post-Quantum Key Encapsulation Methods (PQ KEM) for Transport Layer Security 1.2 (TLS)
draft-campagna-tls-bike-sike-hybrid-03
Hybrid key exchange refers to executing two independent key exchanges and feeding the two resulting shared secrets into a Pseudo Random Function (PRF), with the goal of deriving a secret which is as secure as the stronger of the two key exchanges. This document describes new hybrid key exchange schemes for the Transport Layer Security 1.2 (TLS) protocol. The key exchange schemes are based on combining Elliptic Curve Diffie-Hellman (ECDH) with a post-quantum key encapsulation method (PQ KEM) using the existing TLS PRF. In particular, this document specifies the use of the Bit Flipping Key Exchange (BIKE) and Supersingular Isogeny Key Exchange (SIKE) schemes in combination with ECDHE as a hybrid key agreement in a TLS 1.2 handshake.
This draft is experimental. It is intended to define hybrid key exchanges in sufficient detail to allow independent experimentations to interoperate. While the NIST standardization process is still a few years away from being complete, we know that many TLS users have highly sensitive workloads that would benefit from the speculative additional protections provided by quantum-safe key exchanges. These key exchanges are likely to change through the standardization process. Early experiments serve to understand the real-world performance characteristics of these quantum-safe schemes as well as provide speculative additional confidentiality assurances against a future adversary with a large-scale quantum computer.
Comments are solicited and can be sent to all authors at mcampagna@amazon.com.
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 September 7, 2020.
Copyright (c) 2020 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.
Quantum-safe (or post-quantum) key exchanges are being developed in order to provide secure key establishment against an adversary with access to a quantum computer. Under such a threat model, the current key exchange mechanisms would be vulnerable. BIKE and SIKE are two post-quantum candidates which were submitted to the NIST Call for Proposals for Post-Quantum Cryptographic Schemes. While these schemes are still being analyzed as part of that process, there is already a need to protect the confidentiality of today's TLS connections against a future adversary with a quantum computer. Hybrid key exchanges are designed to provide two parallel key exchanges: one which is classical (e.g., ECDHE) and the other which is quantum-safe (e.g., BIKE or SIKE). The hybrid schemes we propose are no less secure against classical computers than ECDH, and no less secure against quantum computers than BIKE or SIKE. This strategy is emerging as a method to speculatively provide additional security to existing protocols.
This document describes additions to TLS to support PQ Hybrid Key Exchanges, applicable to TLS Version 1.2 [RFC5246]. These additions are designed to support most of the second-round candidates in the NIST Call for Proposals, but this document only defines ciphersuites for a small subset of possible hybrid key agreement methods. In particular, it defines the use of the ECDHE together with BIKE or SIKE, as a hybrid key agreement method.
The remainder of this document is organized as follows. Section 2 provides an overview of PQ KEM-based key exchange algorithms for TLS. Section 3 describes how PQ KEM can be combined with ECDHE to form a premaster secret. In Section 4, we present a TLS extension that allow a client to negotiate the use of specific PQ schemes and parameters. Section 5 specifies various data structures needed for a BIKE- or SIKE-based hybrid key exchange handshake, their encoding in TLS messages, and the processing of those messages. Section 6 defines two new PQ KEM hybrid-based cipher suites and identifies a small subset of these as recommended for all implementations of this specification. Section 7 discusses some security considerations. Section 8 describes IANA considerations for the name spaces created by this document. Section 9 gives acknowledgments.
Implementation of this specification requires familiarity with TLS [RFC5246], BIKE, and SIKE.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119.
This document introduces two new hybrid-based key exchange methods for TLS. They use ECDHE with either BIKE 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 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.
| Hybrid Key Exchange Scheme Name | Description |
|---|---|
| ECDHE_BIKE | ECDHE and a BIKE KEM. |
| ECDHE_SIKE | ECDHE and a SIKE KEM. |
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: Message flow in a hybrid TLS handshake
These schemes are intended to provide quantum-safe forward secrecy. 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.
A key encapsulation mechanism (KEM) is a set of three algorithms Section 7. BIKE and SIKE are two examples of a KEM.
and a defined key space, where
The security of a KEM is discussed in
This section describes the nearly identical hybrid key exchanges ECDHE_BIKE and ECDHE_SIKE. For the remainder of this section [KEM] refers to either BIKE or SIKE. The server sends its ephemeral ECDH public key and an ephemeral [KEM] public key generated using the corresponding curve and [KEM] parameters in the ServerKeyExchange message. This specification requires that these parameters MUST be signed using a signature algorithm corresponding to the public key in the server's certificate.
The client generates an ECDHE key pair on the same curve as the server's ephemeral ECDH key, and computes a ciphertext value based on the [KEM] public key provided by the server, and sends them in the ClientKeyExchange message. The client computes and holds the PQ KEM-encapsulated key (K) as a contribution to the premaster secret.
Both client and server perform an ECDH operation and use the resultant shared secret (Z) as part of the premaster secret. The server computes the PQ KEM decapsulation routine to compute the encapsulated key (K), or to produce an error message in case the decapsulation fails.
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.
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 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, and if the client does not support SIKE, it must not include SIKE parameters in the extension. 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.
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].
This section specifies the Supported PQ KEM Parameters extension that can be included with the ClientHello message as described in RFC 5246.
The extensions SHOULD be sent along with any ClientHello message that proposes the associated PQ KEM cipher suites.
These extensions allow a client to enumerate the PQ KEM parameters sets it supports for any supported PQ KEM.
enum {
pq_kem_parameters(0xFE01)
} ExtensionType;
The general structure of TLS extensions is described in RFC 5246, and this specification adds a new type to ExtensionType.
A client that proposes PQ KEM hybrid key exchange cipher suites in its ClientHello message appends these extensions (along with any others), enumerating the parameters it supports. Clients SHOULD send the PQ KEM parameter sets it supports if it supports PQ KEM hybrid key exchange cipher suites.
A server that receives a ClientHello containing this extension MUST use the client's enumerated capabilities to guide its selection of an appropriate cipher suite. One of the proposed PQ KEM cipher suites must be negotiated only if the server can successfully complete the handshake while using the PQ KEM parameters supported by the client (cf. Section 5.1.6.)
If a server does not understand the Supported PQ KEM Parameters extension, or is unable to complete the PQ KEM handshake while restricting itself to the enumerated parameters, it MUST NOT negotiate the use of the corresponding PQ KEM cipher suite. Depending on what other cipher suites are proposed by the client and supported by the server, this may result in a fatal handshake failure alert due to the lack of common cipher suites.
enum {
BIKE1-L1-R1 (1),
BIKE1-L3-R1 (2),
BIKE1-L5-R1 (3),
BIKE2-L1-R1 (4),
BIKE2-L3-R1 (5),
BIKE2-L5-R1 (6),
BIKE3-L1-R1 (7),
BIKE3-L3-R1 (8),
BIKE3-L5-R1 (9),
SIKE-P503-R1 (10),
SIKE-P751-R1 (11),
SIKE-p964-R1 (12),
BIKE1-CCA-L1-R2 (13),
BIKE1-CCA-L3-R2 (14),
BIKE1-CCA-L5-R2 (15),
BIKE2-CCA-L1-R2 (16),
BIKE2-CCA-L3-R2 (17),
BIKE2-CCA-L5-R2 (18),
SIKE-P434-R2 (19),
SIKE-P503-R2 (20),
SIKE-P610-R2 (21),
SIKE-P751-R2 (22)
} NamedPQKEM (2^16-1);
This section defines the contents of the Supported PQ KEM Parameters extension. In the language of RFC 5246, the extension_data is the PQKEMParametersExtension type defined below. BIKE1-L1-R1, etc: Indicates support of the corresponding BIKE parameters defined in BIKE Round 1, the round 1 candidate to the NIST Post-Quantum Cryptography Standardization Process. (NIST PQC)
BIKE1-CCA-L1-R2, etc: Indicates support of the corresponding BIKE CCA parameters defined in BIKE Round 2, the latest revision of the round 2 CCA candidate submitted to NIST PQC available at the time of this draft specification.
SIKE1-P503-R1, etc: Indicates support of the corresponding SIKE parameters defined in SIKE Round 1, the round 1 candidate to NIST PQC.
SIKE1-P434-R2, etc: Indicates support of the corresponding SIKE parameters defined in SIKE Round 2, the round 2 candidate to NIST PQC.
struct {
NamedPQKEM pq_kem_parameters_list <1..2^16-1>
} PQKEMParametersExtension;
pq_kem_parameters_list are ordered according to the client's preferences (favorite choice first).
FE 01 00 08 00 06 00 13 00 01 00 04
As an example, a client that only supports BIKE1-L1-R1 ( value 1 = 0x0001), BIKE2-L1-R1 ( value 4 = 0x0004) and SIKE-P434-R2 ( value 19 = 0x0013) and prefers to use SIKE-P434-R2 would include a TLS extension consisting of the following octets:
This message is sent when using an ECDHE_[KEM] hybrid key exchange algorithms.
This message is used to convey the server's ephemeral ECDH and [KEM] public keys to the client.
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;
public_key: This is a byte string representation of the [KEM] public key following the conversion defined by the [KEM] implementation.
For ECDHE_[KEM]: [RFC5246] and RFC 8422, respectively, for details on their use in TLS 1.2.
NOTE: This specification only defines hybrid ciphersuites with RSA and ECDSA signatures. See
The server selects elliptic curve domain parameters and an ephemeral ECDH public key corresponding to these parameters according to RFC 8422. The server SHOULD generate a fresh ephemeral ECDH key for each key exchange so that the hybrid key exchange scheme provides forward secrecy. The server selects a PQ KEM parameter set, and uses KeyGen() for the corresponding parameters of BIKE Round 1, BIKE Round 2, SIKE Round 1, or SIKE Round 2 to generate an ephemeral public key pair. The server MUST generate a fresh BIKE or SIKE key for each key exchange. A server that receives a Supported PQ KEM Parameters extension MUST use the client's enumerated capabilities to guide its selection of an appropriate cipher suite. The server 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 (cf. Section 5.1.6). If the client does not include the PQ KEM Parameters extension, the server is free to choose any one of the parameters listed in Section 5.1.6.
If a server is unable to complete the PQ KEM handshake while restricting itself to the enumerated parameters, it MUST NOT negotiate the use of the corresponding PQ KEM cipher suite. Depending on what other cipher suites are proposed by the client and supported by the server, this may result in a fatal handshake failure alert due to the lack of common cipher suites.
After selecting a ciphersuite and appropriate parameters, the server conveys this information to the client in the ServerKeyExchange message using the format defined above.
The client verifies the signature and retrieves the server's elliptic curve domain parameters and ephemeral ECDH public key and the [KEM] parameter set and public key from the ServerKeyExchange message.
A possible reason for a fatal handshake failure is that the client's capabilities for handling elliptic curves and point formats are exceeded (see RFC 8422), the PQ KEM parameters are not supported (see Section 5.1), or the signature does not verify.
This message is sent in all key exchange algorithms. In the key exchanges defined in this document, it contains the client's ephemeral ECDH public key and the [KEM] ciphertext value.
This message is used to convey ephemeral data relating to the key exchange belonging to the client (such as its ephemeral ECDH public key and the [KEM] ciphertext value).
struct {
opaque ciphertext <1,..., 2^24 - 1>;
} PQKEMCiphertext;
struct {
ClientECDiffieHellmanPublic ecdh_public;
PQKEMCiphertext ciphertext;
} ClientKeyExchange;
The TLS ClientKeyExchange message is extended as follows.
The client selects an ephemeral ECDH public key corresponding to the parameters it received from the server according to RFC 8422. The client SHOULD generate a fresh ephemeral ECDH key for each key exchange so that the hybrid key exchange scheme provides forward secrecy. Using the Encaps(pk) function corresponding to the PQ KEM and named parameters in ServerKeyExchange message, the client computes a [KEM] ciphertext. It conveys this information to the server in the ClientKeyExchange message using the format defined above.
The server retrieves the client's ephemeral ECDH public key and the [KEM] ciphertext from the ClientKeyExchange message and checks that it is on the same elliptic curve as the server's ECDHE key, and that the [KEM] ciphertexts conform to the domain parameters selected by the server. The server uses the Decaps(pk) function corresponding to the PQ KEM and named parameters in ServerKeyExchange message to compute the KEM shared secret.
In the case of BIKE there is a decapsulation failure rate no greater than 10^(-7). In the case of a decapsulation failure, an implementation MUST abort the handshake.
This section defines a new hybrid master secret derivation. It is defined under the assumption that we use the concatenated premaster secret defined in Section 3.1. Recall in this case the premaster_secret = Z || K, where Z it the ECDHE shared secret, and K is the KEM shared secret.
master_secret[48] = TLS-PRF(secret, label, seed)
We define the master secret as follows:
The table below defines new hybrid key exchange cipher suites that use the key exchange algorithms specified in Section 2.
| Ciphersuite |
|---|
| TLS_ECDHE_BIKE_ECDSA_WITH_AES_128_GCM_SHA256 = { 0xFF, 0x01 } |
| TLS_ECDHE_BIKE_ECDSA_WITH_AES_256_GCM_SHA384 = { 0xFF, 0x02 } |
| TLS_ECDHE_BIKE_RSA_WITH_AES_128_GCM_SHA256 = { 0xFF, 0x03 } |
| TLS_ECDHE_BIKE_RSA_WITH_AES_256_GCM_SHA384 = { 0xFF, 0x04 } |
| TLS_ECDHE_SIKE_ECDSA_WITH_AES_128_GCM_SHA256 = { 0xFF, 0x05 } |
| TLS_ECDHE_SIKE_ECDSA_WITH_AES_256_GCM_SHA384 = { 0xFF, 0x06 } |
| TLS_ECDHE_SIKE_RSA_WITH_AES_128_GCM_SHA256 = { 0xFF, 0x07 } |
| TLS_ECDHE_SIKE_RSA_WITH_AES_256_GCM_SHA384 = { 0xFF, 0x08 } |
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.
It is recommended that any implementation of this specification include both of the following ciphersuites:
using the parameters BIKE1-CCA-L1-R2 and SIKE-P434-R2.
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 ciphersuites 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.
This document describes three new name spaces for use with the TLS protocol:
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.
This becomes an Appendix.