Hybrid key exchange in TLS 1.3

1.1. Revision history

• RFC Editor's Note: Please remove this section prior to publication of a final version of this document.¶

Earlier versions of this document categorized various design decisions one could make when implementing hybrid key exchange in TLS 1.3.¶

• draft-ietf-tls-hybrid-design-06:¶

  • Bump to version -06 to avoid expiry¶

• draft-ietf-tls-hybrid-design-05:¶

  • Define four hybrid key exchange methods¶
  • Updates to reflect NIST's selection of Kyber¶
  • Clarifications and rewordings based on working group comments¶

• draft-ietf-tls-hybrid-design-04:¶

  • Some wording changes¶
  • Remove design considerations appendix¶

• draft-ietf-tls-hybrid-design-03:¶

  • Remove specific code point examples and requested codepoint range for hybrid private use¶
  • Change "Open questions" to "Discussion"¶
  • Some wording changes¶

• draft-ietf-tls-hybrid-design-02:¶

  • Bump to version -02 to avoid expiry¶

• draft-ietf-tls-hybrid-design-01:¶

  • Forbid variable-length secret keys¶
  • Use fixed-length KEM public keys/ciphertexts¶

• draft-ietf-tls-hybrid-design-00:¶

  • Allow key_exchange values from the same algorithm to be reused across multiple KeyShareEntry records in the same ClientHello.¶

• draft-stebila-tls-hybrid-design-03:¶

  • Add requirement for KEMs to provide protection against key reuse.¶
  • Clarify FIPS-compliance of shared secret concatenation method.¶

• draft-stebila-tls-hybrid-design-02:¶

  • Design considerations from draft-stebila-tls-hybrid-design-00 and draft-stebila-tls-hybrid-design-01 are moved to the appendix.¶
  • A single construction is given in the main body.¶

• draft-stebila-tls-hybrid-design-01:¶

  • Add (Comb-KDF-1) and (Comb-KDF-2) options.¶
  • Add two candidate instantiations.¶
• draft-stebila-tls-hybrid-design-00: Initial version.¶

1.2. Terminology

For the purposes of this document, it is helpful to be able to divide cryptographic algorithms into two classes:¶

• "Traditional" algorithms: Algorithms which are widely deployed today, but which may be deprecated in the future. In the context of TLS 1.3, examples of traditional key exchange algorithms include elliptic curve Diffie-Hellman using secp256r1 or x25519, or finite-field Diffie-Hellman.¶
• "Next-generation" (or "next-gen") algorithms: Algorithms which are not yet widely deployed, but which may eventually be widely deployed. An additional facet of these algorithms may be that we have less confidence in their security due to them being relatively new or less studied. This includes "post-quantum" algorithms.¶

"Hybrid" key exchange, in this context, means the use of two (or more) key exchange algorithms based on different cryptographic assumptions, e.g., one traditional algorithm and one next-gen algorithm, with the purpose of the final session key being secure as long as at least one of the component key exchange algorithms remains unbroken. When one of the algorithms is traditional and one of them is postquantum, this is a Post-Quantum Traditional Hybrid Scheme [I-D.driscoll-pqt-hybrid-terminology]; while this is the initial use case for this draft, we do not limit this draft to that case. We use the term "component" algorithms to refer to the algorithms combined in a hybrid key exchange.¶

We note that some authors prefer the phrase "composite" to refer to the use of multiple algorithms, to distinguish from "hybrid public key encryption" in which a key encapsulation mechanism and data encapsulation mechanism are combined to create public key encryption.¶

It is intended that the composite algorithms within a hybrid key exchange are to be performed, that is, negotiated and transmitted, within the TLS 1.3 handshake. Any out-of-band method of exchanging keying material is considered out-of-scope.¶

The primary motivation of this document is preparing for post-quantum algorithms. However, it is possible that public key cryptography based on alternative mathematical constructions will be desired to mitigate risks independent of the advent of a quantum computer, for example because of a cryptanalytic breakthrough. As such we opt for the more generic term "next-generation" algorithms rather than exclusively "post-quantum" algorithms.¶

Note that TLS 1.3 uses the phrase "groups" to refer to key exchange algorithms -- for example, the supported_groups extension -- since all key exchange algorithms in TLS 1.3 are Diffie-Hellman-based. As a result, some parts of this document will refer to data structures or messages with the term "group" in them despite using a key exchange algorithm that is not Diffie-Hellman-based nor a group.¶

1.3. Motivation for use of hybrid key exchange

A hybrid key exchange algorithm allows early adopters eager for post-quantum security to have the potential of post-quantum security (possibly from a less-well-studied algorithm) while still retaining at least the security currently offered by traditional algorithms. They may even need to retain traditional algorithms due to regulatory constraints, for example FIPS compliance.¶

Ideally, one would not use hybrid key exchange: one would have confidence in a single algorithm and parameterization that will stand the test of time. However, this may not be the case in the face of quantum computers and cryptanalytic advances more generally.¶

Many (though not all) post-quantum algorithms currently under consideration are relatively new; they have not been subject to the same depth of study as RSA and finite-field or elliptic curve Diffie-Hellman, and thus the security community does not necessarily have as much confidence in their fundamental security, or the concrete security level of specific parameterizations.¶

Moreover, it is possible that after next-generation algorithms are defined, and for a period of time thereafter, conservative users may not have full confidence in some algorithms.¶

Some users may want to accelerate adoption of post-quantum cryptography due to the threat of retroactive decryption: if a cryptographic assumption is broken due to the advent of a quantum computer or some other cryptanalytic breakthrough, confidentiality of information can be broken retroactively by any adversary who has passively recorded handshakes and encrypted communications. Hybrid key exchange enables potential security against retroactive decryption while not fully abandoning traditional cryptosystems.¶

As such, there may be users for whom hybrid key exchange is an appropriate step prior to an eventual transition to next-generation algorithms. Users should consider the confidence they have in each hybrid component to assess that the hybrid system meets the desired motivation.¶

1.4. Scope

This document focuses on hybrid ephemeral key exchange in TLS 1.3 [TLS13]. It intentionally does not address:¶

• Selecting which next-generation algorithms to use in TLS 1.3, or algorithm identifiers or encoding mechanisms for next-generation algorithms. This selection will be based on the recommendations by the Crypto Forum Research Group (CFRG), which is currently waiting for the results of the NIST Post-Quantum Cryptography Standardization Project [NIST].¶
• Authentication using next-generation algorithms. While quantum computers could retroactively decrypt previous sessions, session authentication cannot be retroactively broken.¶

1.5. Goals

The primary goal of a hybrid key exchange mechanism is to facilitate the establishment of a shared secret which remains secure as long as as one of the component key exchange mechanisms remains unbroken.¶

In addition to the primary cryptographic goal, there may be several additional goals in the context of TLS 1.3:¶

• Backwards compatibility: Clients and servers who are "hybrid-aware", i.e., compliant with whatever hybrid key exchange standard is developed for TLS, should remain compatible with endpoints and middle-boxes that are not hybrid-aware. The three scenarios to consider are:¶

  1. Hybrid-aware client, hybrid-aware server: These parties should establish a hybrid shared secret.¶
  2. Hybrid-aware client, non-hybrid-aware server: These parties should establish a traditional shared secret (assuming the hybrid-aware client is willing to downgrade to traditional-only).¶
  3. Non-hybrid-aware client, hybrid-aware server: These parties should establish a traditional shared secret (assuming the hybrid-aware server is willing to downgrade to traditional-only).¶

  Ideally backwards compatibility should be achieved without extra round trips and without sending duplicate information; see below.¶

• High performance: Use of hybrid key exchange should not be prohibitively expensive in terms of computational performance. In general this will depend on the performance characteristics of the specific cryptographic algorithms used, and as such is outside the scope of this document. See [PST] for preliminary results about performance characteristics.¶

• Low latency: Use of hybrid key exchange should not substantially increase the latency experienced to establish a connection. Factors affecting this may include the following.¶

  • The computational performance characteristics of the specific algorithms used. See above.¶
  • The size of messages to be transmitted. Public key and ciphertext sizes for post-quantum algorithms range from hundreds of bytes to over one hundred kilobytes, so this impact can be substantial. See [PST] for preliminary results in a laboratory setting, and [LANGLEY] for preliminary results on more realistic networks.¶
  • Additional round trips added to the protocol. See below.¶
• No extra round trips: Attempting to negotiate hybrid key exchange should not lead to extra round trips in any of the three hybrid-aware/non-hybrid-aware scenarios listed above.¶
• Minimal duplicate information: Attempting to negotiate hybrid key exchange should not mean having to send multiple public keys of the same type.¶

3.1. Negotiation

Each particular combination of algorithms in a hybrid key exchange will be represented as a NamedGroup and sent in the supported_groups extension. No internal structure or grammar is implied or required in the value of the identifier; they are simply opaque identifiers.¶

Each value representing a hybrid key exchange will correspond to an ordered pair of two or more algorithms. For example, a future document could specify that one identifier corresponds to secp256r1+Kyber512, and another corresponds to x25519+Kyber512. (We note that this is independent from future documents standardizing solely post-quantum key exchange methods, which would have to be assigned their own identifier.)¶

Specific values shall be registered by IANA in the TLS Supported Groups registry.¶

    enum {

          /* Elliptic Curve Groups (ECDHE) */
          secp256r1(0x0017), secp384r1(0x0018), secp521r1(0x0019),
          x25519(0x001D), x448(0x001E),

          /* Finite Field Groups (DHE) */
          ffdhe2048(0x0100), ffdhe3072(0x0101), ffdhe4096(0x0102),
          ffdhe6144(0x0103), ffdhe8192(0x0104),

          /* Hybrid Key Exchange Methods */
          x25519_kyber768(TBD), secp384r1_kyber768(TBD),
          x25519_kyber512(TBD), secp256r1_kyber512(TBD), ...,

          /* Reserved Code Points */
          ffdhe_private_use(0x01FC..0x01FF),
          ecdhe_private_use(0xFE00..0xFEFF),
          (0xFFFF)
    } NamedGroup;

3.2. Transmitting public keys and ciphertexts

We take the relatively simple "concatenation approach": the messages from the two or more algorithms being hybridized will be concatenated together and transmitted as a single value, to avoid having to change existing data structures. The values are directly concatenated, without any additional encoding or length fields; this assumes that the representation and length of elements is fixed once the algorithm is fixed. If concatenation were to be used with values that are not fixed-length, a length prefix or other unambiguous encoding must be used to ensure that the composition of the two values is injective and requires a mechanism different from that specified in this document.¶

Recall that in TLS 1.3 a KEM public key or KEM ciphertext is represented as a KeyShareEntry:¶

    struct {
        NamedGroup group;
        opaque key_exchange<1..2^16-1>;
    } KeyShareEntry;

These are transmitted in the extension_data fields of KeyShareClientHello and KeyShareServerHello extensions:¶

    struct {
        KeyShareEntry client_shares<0..2^16-1>;
    } KeyShareClientHello;

    struct {
        KeyShareEntry server_share;
    } KeyShareServerHello;

The client's shares are listed in descending order of client preference; the server selects one algorithm and sends its corresponding share.¶

For a hybrid key exchange, the key_exchange field of a KeyShareEntry is the concatenation of the key_exchange field for each of the constituent algorithms. The order of shares in the concatenation is the same as the order of algorithms indicated in the definition of the NamedGroup.¶

For the client's share, the key_exchange value contains the concatenation of the pk outputs of the corresponding KEMs' KeyGen algorithms, if that algorithm corresponds to a KEM; or the (EC)DH ephemeral key share, if that algorithm corresponds to an (EC)DH group. For the server's share, the key_exchange value contains concatenation of the ct outputs of the corresponding KEMs' Encaps algorithms, if that algorithm corresponds to a KEM; or the (EC)DH ephemeral key share, if that algorithm corresponds to an (EC)DH group.¶

[TLS13] requires that ``The key_exchange values for each KeyShareEntry MUST be generated independently.'' In the context of this document, since the same algorithm may appear in multiple named groups, we relax the above requirement to allow the same key_exchange value for the same algorithm to be reused in multiple KeyShareEntry records sent in within the same ClientHello. However, key_exchange values for different algorithms MUST be generated independently.¶

3.3. Shared secret calculation

Here we also take a simple "concatenation approach": the two shared secrets are concatenated together and used as the shared secret in the existing TLS 1.3 key schedule. Again, we do not add any additional structure (length fields) in the concatenation procedure: for both the traditional groups and Kyber, the shared secret output length is fixed for a specific elliptic curve or parameter set.¶

In other words, the shared secret is calculated as¶

    concatenated_shared_secret = shared_secret_1 || shared_secret_2

and inserted into the TLS 1.3 key schedule in place of the (EC)DHE shared secret, as shown in Figure 1.¶

                                    0
                                    |
                                    v
                      PSK ->  HKDF-Extract = Early Secret
                                    |
                                    +-----> Derive-Secret(...)
                                    +-----> Derive-Secret(...)
                                    +-----> Derive-Secret(...)
                                    |
                                    v
                              Derive-Secret(., "derived", "")
                                    |
                                    v
concatenated_shared_secret -> HKDF-Extract = Handshake Secret
^^^^^^^^^^^^^^^^^^^^^^^^^^          |
                                    +-----> Derive-Secret(...)
                                    +-----> Derive-Secret(...)
                                    |
                                    v
                              Derive-Secret(., "derived", "")
                                    |
                                    v
                         0 -> HKDF-Extract = Master Secret
                                    |
                                    +-----> Derive-Secret(...)
                                    +-----> Derive-Secret(...)
                                    +-----> Derive-Secret(...)
                                    +-----> Derive-Secret(...)

FIPS-compliance of shared secret concatenation. [NIST-SP-800-56C] or [NIST-SP-800-135] give NIST recommendations for key derivation methods in key exchange protocols. Some hybrid combinations may combine the shared secret from a NIST-approved algorithm (e.g., ECDH using the nistp256/secp256r1 curve) with a shared secret from a non-approved algorithm (e.g., post-quantum). [NIST-SP-800-56C] lists simple concatenation as an approved method for generation of a hybrid shared secret in which one of the constituent shared secret is from an approved method.¶

5.1. Kyber version

For kyber512 and kyber768, this document refers to the same named parameter sets defined in the Round 3 submission of Kyber to NIST. That submission defines two variants for each parameter set based on the symmetric primitives used. This document uses the FIPS 202 variant (and not the "90s" variant); the FIPS 202 variant uses SHA-3 and SHAKE [NIST-FIPS-202] as its internal symmetric primitives.¶

The Kyber team has updated their documentation twice since submitting to Round 3 (these updates are labeled as version 3.0.1 and 3.0.2), however neither modifies the FIPS 202 variant of Kyber.¶

5.2. Details of Kyber components

The listed kyber512, kyber768 components are the named parameter sets of the key exchange method Kyber [Kyber]. When it is used, the client selects an ephemeral private key, generates the corresponding public key, and transmits that (as a component) within its keyshare. When the server receives this keyshare, it extracts the Kyber public key, generates a ciphertext and shared secret. It then transmits the ciphertext (as a component) within its keyshare. When the client receives this keyshare, it extracts the Kyber ciphertext, and uses its private key to generate the shared secret. Both sides use their copy of the shared secret as a component within the hybrid shared secret.¶