KEM-based pre-shared-key handshakes for TLS 1.3

1.1. Related work

This proposal draws inspiration from [I-D.ietf-tls-semistatic-dh], which is in turn based on the OPTLS proposal for TLS 1.3 [KW16]. However, these proposals require a non-interactive key exchange: they combine the client's public key with the server's long-term key. This imposes an extra requirement: the ephemeral and static keys MUST use the same algorithm, which this proposal does not require. Additionally, there are no post-quantum proposals for a non-interactive key exchange currently considered for standardization, while several KEMs are on the way.¶

1.2. Organization

After covering preliminaries, we introduce the abbreviated AuthKEM-PSK handshake, and its opportunistic client authentication mechanism. In the remainder of the draft, we will discuss the necessary implementation mechanics, such as code points, extensions, new protocol messages and the new key schedule.¶

2.1. Terminology

The following terms are used as they are in [RFC8446]¶

client:

The endpoint initiating the TLS connection.¶

connection:

A transport-layer connection between two endpoints.¶

endpoint:

Either the client or server of the connection.¶

handshake:

An initial negotiation between client and server that establishes the parameters of their subsequent interactions within TLS.¶

peer:

An endpoint. When discussing a particular endpoint, "peer" refers to the endpoint that is not the primary subject of discussion.¶

receiver:

An endpoint that is receiving records.¶

sender:

An endpoint that is transmitting records.¶

server:

The endpoint that responded to the initiation of the TLS connection. i.e. the peer of the client.¶

2.2. Key Encapsulation Mechanisms

As this proposal relies heavily on KEMs, which are not originally used by TLS, we will provide a brief overview of this primitive. Other cryptographic operations will be discussed later.¶

This definition matches the one from [I-D.draft-celi-wiggers-tls-authkem].¶

A Key Encapsulation Mechanism (KEM) is a cryptographic primitive that defines the methods Encapsulate and Decapsulate. In this draft, we extend these operations with context separation strings:¶

Encapsulate(pkR, context_string):

Takes a public key, and produces a shared secret and encapsulation.¶

Decapsulate(enc, skR, context_string):

Takes the encapsulation and the private key. Returns the shared secret.¶

We implement these methods through the KEMs defined in [RFC9180] to export shared secrets appropriate for using with key schedule in TLS 1.3:¶

def Encapsulate(pk, context_string):
  enc, ctx = HPKE.SetupBaseS(pk,
                             "tls13 auth-kem " + context_string)
  ss = ctx.Export("", HKDF.Length)
  return (enc, ss)

def Decapsulate(enc, sk, context_string):
  return HPKE.SetupBaseR(enc,
                         sk,
                         "tls13 auth-kem " + context_string)
             .Export("", HKDF.Length)

Keys are generated and encoded for transmission following the conventions in [RFC9180]. The values of context_string are defined in Section 4.4.2.¶

3.1. Negotiation

In an Appendix A.1, we sketch a variant based on the PSK extension.¶

A client that knows a server's long-term KEM public key MAY choose to attempt the abbreviated AuthKEM handshake. If it does so, it MUST include the stored_auth_key extension in the ClientHello message. This message MUST contain the encapsulation against the long-term KEM public key. Details of the extension are described below. The shared secret resulting from the encapsulation is mixed in to the EarlySecret computation.¶

The client MAY additionally choose to send a certificate to the server. It MUST know what ciphersuites the server accepts before it does so. If it chooses to do so, it MUST send the early_auth extension to the server. The Certificate is encrypted with the client_early_handshake_traffic_secret.¶

The server MAY accept the abbreviated AuthKEM handshake. If it does, it MUST reply with a stored_auth_key extension. If it does not accept the abbreviated AuthKEM handshake, for instance because it does not have access to the correct secret key anymore, it MUST NOT reply with a stored_auth_key extension. The server, if it accepts the abbreviated AuthKEM handshake, MAY additionally accept the Certificate message. If it does, it MUST reply with a early_auth extension.¶

If the client, who sent a stored_auth_key extension, receives a ServerHello without stored_auth_key extension, it MUST recompute EarlySecret without the encapsulated shared secret.¶

If the client sent a Certificate message, it MUST drop that message from its transcript. The client MUST then continue with a full AuthKEM handshake.¶

3.2. 0-RTT, forward secrecy and replay protection

The client MAY send 0-RTT data, as in [RFC8446] 0-RTT mode. The Certificate MUST be sent before the 0-RTT data.¶

As the EarlySecret is derived only from a key encapsulated to a long-term secret, it does not have forward secrecy. Clients MUST take this into consideration before transmitting 0-RTT data or opting in to early client auth. Certificates and 0-RTT data may also be replayed.¶

This will be discussed in full under Security Considerations.¶

4.1. Negotiation of AuthKEM algorithms

Clients and servers indicate support for AuthKEM authentication by negotiating it as if it were a signature scheme (part of the signature_algorithms extension). We thus add these new signature scheme values (even though, they are not signature schemes) for the KEMs defined in [RFC9180] Section 7.1. Note that we will be only using their internal KEM's API defined there.¶

enum {
  dhkem_p256_sha256   => TBD,
  dhkem_p384_sha384   => TBD,
  dhkem_p521_sha512   => TBD,
  dhkem_x25519_sha256 => TBD,
  dhkem_x448_sha512   => TBD,
  kem_x25519kyber768  => TBD, /*draft-westerbaan-cfrg-hpke-xyber768d00*/
}

This matches the definition in [I-D.draft-celi-wiggers-tls-authkem].¶

Please give feedback on which KEMs should be included¶

When present in the signature_algorithms extension, these values indicate AuthKEM support with the specified key exchange mode. These values MUST NOT appear in signature_algorithms_cert, as this extension specifies the signing algorithms by which certificates are signed.¶

4.2. ClientHello and ServerHello extensions

A number of AuthKEM messages contain tag-length-value encoded extensions structures. We are adding those extensions to the ExtensionType list from TLS 1.3.¶

enum {
  ...
  stored_auth_key (TBD),                 /* RFC TBD */
  early_auth (TBD),                      /* RFC TBD */
  (65535)
} ExtensionType;

The table below indicates the messages where a given extension may appear:¶

+---------------------------------------+-------------+
| Extension                             |    KEM-Auth |
+---------------------------------------+-------------+
| stored_auth_key [RFCTBD]              |      CH, SH |
|                                       |             |
| early_auth  [RFCTBD]                  |      CH, SH |
|                                       |             |
+---------------------------------------+-------------+

struct {
      select (type) {
        case client:
          opaque key_fingerprint<1..255>;
          opaque ciphertext<1..2^16-1>
        case server:
          AcceptedAuthKey '1';
      } body;
} StoredInformation

struct {} EarlyAuth

4.3. Protocol messages

The handshake protocol is used to negotiate the security parameters of a connection, as in TLS 1.3. It uses the same messages, except for the addition of a KEMEncapsulation message and does not use the CertificateVerify one.¶

Note that these definitions mirror [I-D.draft-celi-wiggers-tls-authkem].¶

enum {
    ...
    kem_encapsulation(tbd),
    ...
    (255)
  } HandshakeType;

struct {
    HandshakeType msg_type;  /* handshake type */
    uint24 length;           /* remaining bytes in message */
    select (Handshake.msg_type) {
        ...
        case kem_encapsulation:     KEMEncapsulation;
        ...
    };
} Handshake;

Protocol messages MUST be sent in the order defined in Section 3. A peer which receives a handshake message in an unexpected order MUST abort the handshake with an "unexpected_message" alert.¶

The KEMEncapsulation message is defined as follows:¶

struct {
    opaque certificate_request_context<0..2^8-1>
    opaque encapsulation<0..2^16-1>;
} KEMEncapsulation;

The encapsulation field is the result of a Encapsulate() function. The Encapsulate() function will also result in a shared secret (ssS or ssC, depending on the peer) which is used to derive the AHS or MS secrets.¶

If the KEMEncapsulation message is sent by a server, the authentication algorithm MUST be one offered in the client's signature_algorithms extension unless no valid certificate chain can be produced without unsupported algorithms.¶

If sent by a client, the authentication algorithm used in the signature MUST be one of those present in the supported_signature_algorithms field of the signature_algorithms extension in the CertificateRequest message.¶

In addition, the authentication algorithm MUST be compatible with the key(s) in the sender's end-entity certificate.¶

The receiver of a KEMEncapsulation message MUST perform the Decapsulate() operation by using the sent encapsulation and the private key of the public key advertised in the end-entity certificate sent. The Decapsulate() function will also result on a shared secret (ssS or ssC, depending on the Server or Client executing it respectively) which is used to derive the AHS or MS secrets.¶

certificate_request_context is included to allow the recipient to identify the certificate against which the encapsulation was generated. It MUST be set to the value in the Certificate message to which the encapsulation was computed.¶

4.4. Cryptographic computations

The AuthKEM handshake establishes three input secrets which are combined to create the actual working keying material, as detailed below. The key derivation process incorporates both the input secrets and the handshake transcript. Note that because the handshake transcript includes the random values from the Hello messages, any given handshake will have different traffic secrets, even if the same input secrets are used.¶

            0
            |
            v
    SSs -> HKDF-Extract = Early Secret
            |
            ...
            +--> Derive-Secret(., "c e traffic", ClientHello)
            |                  = client_early_traffic_secret
            |
            +--> Derive-Secret(., "c e hs traffic", ClientHello)
            |                  = client_early_handshake_traffic_secret
            ...
            |
            v
            Derive-Secret(., "derived", "") = dES
            ...

            Derive-Secret(., "derived", "") = dHS
            |
            v
SSc||0 * -> HKDF-Extract = Main Secret
            |
            ...

SSs, encapsulation <- Encapsulate(public_key_server,
                                  "server authentication")
               SSc <- Decapsulate(encapsulation, private_key_client,
                                  "client authentication")

               SSs <- Decapsulate(encapsulation, private_key_server
                                  "server authentication")
SSc, encapsulation <- Encapsulate(public_key_client,
                                  "client authentication")

server/client_finished_key =
    HKDF-Expand-Label(MainSecret,
                      server/client_label,
                      "", Hash.length)
server_label = "tls13 server finished"
client_label = "tls13 client finished"

server/client_verify_data =
      HMAC(server/client_finished_key,
           Transcript-Hash(Handshake Context,
                           Certificate*,
                           KEMEncapsulation*,
                           Finished**)

*  Only included if present.
** The party who last sends the finished message in terms of flights
   includes the other party's Finished message.

5.1. Server Anonymity

The PDK extension identifies the public key to which the client has encapsulated via a hash. This reveals some information about which server identity the client has. [I-D.ietf-tls-esni] may help alleviate this.¶

An alternative approach could be the use of trial decryption. If the KEM used has anonymity, the ciphertext that the client sends is not linkable to the server public key. Kyber offers post-quantum anonymity [MX22].¶

A.1. Alternative implementation based on the pre_shared_key extension

This is discussed in Issue #25.¶

[RFC8446] defines a PSK handshake that can be used with symmetric keys from e.g. session tickets. In this section, we sketch an alternative approach to AuthKEM-PSK based on the pre_shared_key extension.¶

A client needs to be set up with the following information:¶

struct {
    uint32 authkem_psk_config_version;
    uint32 config_lifetime;
    opaque KEMPublicKey;
} AuthKEMPSKConfig;

The client computes a KEM ciphertext and shared secret as follows:¶

SSs, encapsulation <- Encapsulate(public_key_server,
                                  "server authentication")

SSs is used in place of PSK in the TLS 1.3 key schedule, and binder_key is derived as follows:¶

          0
          |
          v
SSc ->  HKDF-Extract = Early Secret
          |
          +-----> Derive-Secret(., "ext binder" | "res binder", "")
          |                     = binder_key
          ...

In the pre_shared_key extension's identities, the client sends the following data:¶

struct {
  uint32 authkem_psk_config_version;
  opaque KEMCiphertext;
} AuthKEMPSKIdentity

The server computes the shared secret SSs from AuthKEMPSKIdentity.KEMCiphertext as follows:¶

SSs <- Decapsulate(encapsulation,
                   private_key_server
                   "server authentication")

The PSK binder value is computed as specified in [RFC8446], section 4.2.11.2. The server MUST verify the binder before continuing and abort the handshake if verification fails.¶

To be determined: how to handle immediate client authentication.¶

A.2. Interactions with DTLS

It is currently open if there need te be made modifications to better support integration with DTLS. Discussion is at Issue #23.¶

A.3. Interaction with signing certificates

Tracked by Issue #20.¶

In the current state of the draft, we have not yet discussed combining traditional signature-based authentication with KEM-based authentication. One might imagine that the Client has a signing certificate and the server has a KEM public key.¶

In the current draft, clients MUST use a KEM certificate algorithm if the server negotiated AuthKEM.¶