Combiner function for hybrid key encapsulation mechanisms (Hybrid KEMs)

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 14 September 2023.¶

Copyright Notice

Copyright (c) 2023 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.¶

Table of Contents

1. Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

This document is consistent with all terminology defined in [I-D.driscoll-pqt-hybrid-terminology].¶

def kemKeyGen() -> (pk, sk)
def kemEncaps(pk) -> (ct, ss)
def kemDecaps(ct, sk) -> ss

2. Introduction

The need for a KEM combiner function arises in three different contexts within IETF security protocols:¶

1. KEM / PSK hybrids where the output of a KEM is combined with a static pre-shared key.¶
2. Post-quantum / traditional hybrid KEMs where output of a post-quantum KEM is combined with the output of a classical key transport or key exchange algorithm.¶
3. KEM-based authenticated key exchanges (AKEs) where the output of two or more KEMs performed in different directions are combined.¶

This document normalizes a mechanism for combining the output of two or more KEMs.¶

3. KEM Combiner construction

A KEM combiner is a function that takes in two or more shared secrets ss_i and returns a combined shared secret ss.¶

ss = kemCombiner(ss_1, ss_2, ..., ss_n)

This document assumes that shared secrets are the output of a KEM, but without loss of generality they MAY also be any other source of cryptographic key material, such as pre-shared keys (PSKs), with PQ/PSK being a quantum-safe migration strategy being made available by some protocols, see for example IKEv2 in [RFC8784].¶

In general it is desirable to use a multi-PRF as a KEM combiner, meaning that the combiner has the properties of a PRF when keyed by any of its single inputs. The following simple yet generic construction can be used in all IETF protocols that need to combine the output of two or more KEMs:¶

KDF(counter || k_1 || ... || k_n || fixedInfo, outputBits)

where:¶

• KDF represents a suitable choice of a cryptographic key derivation function,¶
• k_i represent the constant-length input keys and is discussed in Section 3.1,¶
• fixedInfo is some protocol-specific KDF binding,¶
• counter parameter is instantiation-specific and is discussed in Section 4.¶
• outputBits determines the length of the output keying material,¶
• || represents concatenation.¶

In Section 4 several possible practical instantiations are listed that are in compliance with NIST SP-800 56Cr2 [SP800-56C]. The shared secret ss MAY be used directly as a symmetric key, for example as a MAC key or as a Key Encryption Key (KEK).¶

k_i = H(ss_i || ct_i)

k_i = ss_i || ct_i

k_i = H(ss_i || ct_i)

4. Practical instantiations

The KDF must be instantiated with cryptographically-secure choices for KDF and H. The following are RECOMMENDED Keccak-based instatiations, but other choices MAY be made for example to allow for future cryptographic agility. A protocol using a different instantiation MUST justify that it will behave as a multi-PRF given fixed length inputs.¶

Each instance defines a function to be used as KDF, a hash H function to derive the k_i, and optionally a counter.¶

1. KDF = SHA3-256 and H = SHA3-256, with hashSize = 256 bit.¶
2. KDF = SHA3-512 and H = SHA3-512, with hashSize = 512 bit.¶
3. KDF = KMAC128 and H = SHA3-256, with hashSize = 128 bit.¶
4. KDF = KMAC256 and H = SHA3-512, with hashSize = 256 bit.¶

5. IANA Considerations

None.¶

6. Security Considerations

The proposed instantiations in Section 4 are practical multi-PRFs since this specification limits to the use of Keccak-based constructions. The sponge construction was proven to be indifferentiable from a random oracle [BDPA08]. More precisely, for a given capacity c the indifferentiability proof shows that assuming there are no weaknesses found in the Keccak permutation, an attacker has to make an expected number of 2^(c/2) calls to the permutation to tell Keccak from a random oracle. For a random oracle, a difference in only a single bit gives an unrelated, uniformly random output. Hence, to be able to distinguish a key k, derived from shared keys k_i from a random bit string, an adversary has to correctly guess all key shares k_i entirely.¶

The proposed construction in Section 3 with the instantiations in Section 4 preserves IND-CCA2 of any of its ingredient KEMs, i.e. the newly formed combined KEM is IND-CCA2 secure as long as at least one of the ingredient KEMs is. Indeed, the above stated indifferentiability from a random oracle qualifies Keccak as a split-key pseudorandom function as defined in [GHP18]. That is, Keccak behaves like a random function if at least one input shared secret ss_i is picked uniformly at random. Our construction can thus be seen as an instantiation of the IND-CCA2 preserving Example 3 in Figure 1 of [GHP18], up to some reordering of input shared secrets ss_i and ciphertexts ct_i and their potential compression H(ss_i || ct_i) by a cryptographic hash function.¶

Acknowledgements

This document incorporates contributions and comments from a large group of experts. The authors would especially like to acknowledge the expertise and tireless dedication of the following people, who attended many long meetings and generated millions of bytes of electronic mail and VOIP traffic over the past years in pursuit of this document:¶

Douglas Stebila, Nimrod Aviram, and Andreas Huelsing.¶

We are grateful to all, including any contributors who may have been inadvertently omitted from this list.¶

This document borrows text from similar documents, including those referenced below. Thanks go to the authors of those documents. "Copying always makes things easier and less error prone" - [RFC8411].¶

Authors' Addresses