InternetDraft  KEM Combiner  November 2022 
Ounsworth  Expires 29 May 2023  [Page] 
 Workgroup:
 CFRG
 InternetDraft:
 draftounsworthcfrgkemcombiners00
 Published:
 Intended Status:
 Informational
 Expires:
Combiner function for hybrid key encapsulation mechanisms (Hybrid KEMs)
Abstract
The migration to postquantum cryptography often calls for performing multiple key encapsulations in parallel and then combining their outputs to derive a single shared secret.¶
This document defines the KEM combiner KDF( H(ss1)  H(ss2) )
which is considered to be a dual PRF in practice, even though not provably secure. This mechanism simplifies to KDF( ss1  ss2 )
when used with a KEM which internally uses a KDF to produce its shared secret. RSAKEM, ECDH, Edwards curve DH, and CRYSTALSKyber are shown to meet this criteria and therefore be safe to use with the simplified KEM combiner.¶
About This Document
This note is to be removed before publishing as an RFC.¶
Status information for this document may be found at https://datatracker.ietf.org/doc/draftounsworthcfrgkemcombiners/.¶
Discussion of this document takes place on the Limited Additional Mechanisms for PKIX and SMIME (lamps) Working Group mailing list (mailto:spasm@ietf.org), which is archived at https://mailarchive.ietf.org/arch/browse/spasm/. Subscribe at https://www.ietf.org/mailman/listinfo/spasm/.¶
Source for this draft and an issue tracker can be found at https://github.com/EntrustCorporation/draftounsworthcfrgkemcombiners.¶
Status of This Memo
This InternetDraft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
InternetDrafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as InternetDrafts. The list of current InternetDrafts is at https://datatracker.ietf.org/drafts/current/.¶
InternetDrafts 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 InternetDrafts as reference material or to cite them other than as "work in progress."¶
This InternetDraft will expire on 29 May 2023.¶
Copyright Notice
Copyright (c) 2022 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/licenseinfo) 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.¶
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 [ID.driscollpqthybridterminology].¶
1.1. Key Encapsulation Mechanisms
For the purposes of this document, we consider a Key Encapsulation Mechanism (KEM) to be any asymmetric cryptographic scheme comprised of algorithms satisfying the following interfaces [PQCAPI].¶
def kemKeyGen() > (pk, sk) def kemEncaps(pk) > (ct, ss) def kemDecaps(ct, sk) > ss¶
where pk
is public key, sk
is secret key, ct
is ciphertext, and ss
is shared secret.¶
KEMs are typically used in cases where two parties, hereby refereed to as the "encapsulater" and the "decapsulater", wish to establish a shared secret via public key cryptography, where the decapsulater has an asymmetric key pair and has previously shared the public key with the encapsulater.¶
2. Introduction
The need for a KEM combiner function arises in three different contexts within IETF security protocols:¶
 KEM / PSK hybrids where the output of a KEM is combined with a static preshared key.¶
 Postquantum / tradtional hybrid KEMs.¶
 KEMbased authenticated key exchanges (AKEs).¶
This document normalizes a mechanisms for combining the output of two KEMs.¶
2.1. KEM/PSK hybrids
As a postquantum stopgap, several IETF protocols have added extensions to allow for mixing a preshared key (PSK) into an (EC)DH based key exchange. Examples include CMS [RFC8696] and IKEv2 [RFC8784].¶
2.2. PQ/Traditional hybrid KEMs
A postquantum / traditional hybrid key encapsulation mechanism (hybrid KEM) as defined in [ID.driscollpqthybridterminology] as¶
 PQ/T Hybrid Key Encapsulation Mechanism:

A Key Encapsulation Mechanism (KEM) made up of two or more component KEM algorithms where at least one is a postquantum algorithm and at least one is a traditional algorithm.¶
Building a PQ/T hybrid KEM requires a secure function which combines the output of both component KEMs to form a single output. Several IETF protocols are adding PQ/T hybrid KEM mechanisms as part of their overall postquantum migration strategies, examples include TLS 1.3 [ID.ietftlshybriddesign], IKEv2 [ID.ietfipsecmeikev2multipleke], X.509; PKIX; CMS [ID.ounsworthpqcompositekem], OpenPGP (CITE once Aron's draft is up), JOSE / COSE (CITE once Orie's drafts are up).¶
2.3. KEMbased AKE
The need for a KEMbased authenticated key establishment arises, for example, when two communicating parties each have longterm KEM keys (for example in X.509 certificates), and wish to involve both KEM keys in deriving a mutuallyauthenticated shared secret. In particular this will arise for any protocol that needs to provide postquantum replacements for staticstatic (elliptic curve) DiffieHellman mechanisms. Examples include a KEM replacement for CMP's DHBasedMac [ID.ietflampscmpupdates], .. TODO: cite others.¶
3. KEM Combiner
A KEM combiner is a function that takes in two shared secrets and returns a combined shared secret, where all values are byte arrays.¶
ss = kemCombiner(ss1, ss2)¶
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 preshared keys (PSKs), with PQ/PSK being a quantumsafe migration strategy being made available by some protocols, see for example IKEv2 in [RFC8784].¶
In general it is desirable to use a dual PRF, a dualinput PRF which is keyed off either input, as a KEM combiner (see Appendix A.1 for a discussion of dual PRFs). We take the following construction as a dual PRF in practice, and therefore suitable for use in all IETF protocols that need to combine the output of two KEMs:¶
where KDF
represents a suitable choice of cryptographic key derivation function, H
represents a cryptographic hash function, ss1
and ss2
represent the outputs of the first and second KEMs, and 
represents concatenation. KDF
and H
are assumed to behave as random oracles.¶
See Appendix A.2 for security analysis on the safety of using this combiner with RSAKEM [RFC5990], elliptic curve DiffieHellman [SEC1], Edwards curve DiffieHellman [RFC7748], and CRYSTALSKyber [ID.cfrgschwabekyber]. All of these cryptographic algorithms are found to have a KDF or cryptographic hash as the last step before output of the shared secret, and therefore the KEM combiner construction may be simplified to the following when used with combinations of the analyzed cryptographic algorithms.¶
This simplified combiner proposed as a KEM combiner, for example in [ID.ietftlshybriddesign].¶
In the case that more than two shared secrets need to be combined, the above construction can be extended in the obvious way:¶
4. IANA Considerations
None.¶
5. Security Considerations
This work assumes that the KEM combiner defined in Section 3 is a dual PRF in practice, despite the lack of security proof. As the academic literature progresses towards provably secure dual PRFs, this document may need to be obsoleted in favour of a more robust primitive.¶
It is important to note that the analysis herein pertains to the specific cryptographic algorithms analyzed and do not necessarily generalize to other constructions, even if they are based on the same underlying primitive. Specifically it depends on whether the shared secret produced by the KEM is the output of a fixed and secure key derivation function which makes the length and value of the shared secret beyond the direct control of the initiator of the KEM.¶
6. References
6.1. Normative References
 [RFC2119]
 Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfceditor.org/info/rfc2119>.
 [RFC5990]
 Randall, J., Kaliski, B., Brainard, J., and S. Turner, "Use of the RSAKEM Key Transport Algorithm in the Cryptographic Message Syntax (CMS)", RFC 5990, DOI 10.17487/RFC5990, , <https://www.rfceditor.org/info/rfc5990>.
 [RFC7748]
 Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, , <https://www.rfceditor.org/info/rfc7748>.
 [SEC1]
 "Standards for Efficient Cryptography Group, SEC1: Elliptic Curve Cryptography", , <<https://www.secg.org/sec1v2.pdf>>.
6.2. Informative References
 [Aviram2022]
 Aviram, N., Dowling, B., Komargodski, I., Paterson, K. G., Ronen, E., and E. Yogev, "Practical (PostQuantum) Key Combiners from OneWayness and Applications to TLS.", , <https://eprint.iacr.org/2022/065>.
 [Bellare2015]
 Bellare, M. and A. Lysyanskaya, "Symmetric and Dual PRFs from Standard Assumptions: A Generic Validation of an HMAC Assumption.", , <https://eprint.iacr.org/2015/1198>.
 [ID.cfrgschwabekyber]
 Schwabe, P. and B. Westerbaan, "Kyber PostQuantum KEM", Work in Progress, InternetDraft, draftcfrgschwabekyber01, , <https://www.ietf.org/archive/id/draftcfrgschwabekyber01.txt>.
 [ID.driscollpqthybridterminology]
 D, F., "Terminology for PostQuantum Traditional Hybrid Schemes", Work in Progress, InternetDraft, draftdriscollpqthybridterminology01, , <https://www.ietf.org/archive/id/draftdriscollpqthybridterminology01.txt>.
 [ID.ietfipsecmeikev2multipleke]
 Tjhai, C., Tomlinson, M., Bartlett, G., Fluhrer, S., Van Geest, D., GarciaMorchon, O., and V. Smyslov, "Multiple Key Exchanges in IKEv2", Work in Progress, InternetDraft, draftietfipsecmeikev2multipleke10, , <https://www.ietf.org/archive/id/draftietfipsecmeikev2multipleke10.txt>.
 [ID.ietflampscmpupdates]
 Brockhaus, H., von Oheimb, D., and J. Gray, "Certificate Management Protocol (CMP) Updates", Work in Progress, InternetDraft, draftietflampscmpupdates23, , <https://www.ietf.org/archive/id/draftietflampscmpupdates23.txt>.
 [ID.ietftlshybriddesign]
 Stebila, D., Fluhrer, S., and S. Gueron, "Hybrid key exchange in TLS 1.3", Work in Progress, InternetDraft, draftietftlshybriddesign05, , <https://www.ietf.org/archive/id/draftietftlshybriddesign05.txt>.
 [ID.ounsworthpqcompositekem]
 Ounsworth, M. and J. Gray, "Composite KEM For Use In Internet PKI", Work in Progress, InternetDraft, draftounsworthpqcompositekem00, , <https://www.ietf.org/archive/id/draftounsworthpqcompositekem00.txt>.
 [PQCAPI]
 Project, N. P.Q. C., "PQC  API notes", , <https://csrc.nist.gov/CSRC/media/Projects/PostQuantumCryptography/documents/examplefiles/apinotes.pdf>.
 [RFC3447]
 Jonsson, J. and B. Kaliski, "PublicKey Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1", RFC 3447, DOI 10.17487/RFC3447, , <https://www.rfceditor.org/info/rfc3447>.
 [RFC8174]
 Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <https://www.rfceditor.org/info/rfc8174>.
 [RFC8411]
 Schaad, J. and R. Andrews, "IANA Registration for the Cryptographic Algorithm Object Identifier Range", RFC 8411, DOI 10.17487/RFC8411, , <https://www.rfceditor.org/info/rfc8411>.
 [RFC8696]
 Housley, R., "Using PreShared Key (PSK) in the Cryptographic Message Syntax (CMS)", RFC 8696, DOI 10.17487/RFC8696, , <https://www.rfceditor.org/info/rfc8696>.
 [RFC8784]
 Fluhrer, S., Kampanakis, P., McGrew, D., and V. Smyslov, "Mixing Preshared Keys in the Internet Key Exchange Protocol Version 2 (IKEv2) for Postquantum Security", RFC 8784, DOI 10.17487/RFC8784, , <https://www.rfceditor.org/info/rfc8784>.
Appendix A. Security Analysis
A.1. Dual PRF
Dual PRFs are a active area of research. A dual PRF is a function which is a PRF when keyed by either of its two inputs  guaranteeing pseudorandomness if one of the keys is compromised or even maliciously chosen by an adversary [Aviram2022]. As of publication of this document, no dual PRFs have been standardized for use. In practice we often use HMACs or HKDFs to serve the role of a dual PRF even though they have never been proved to be dual PRFs [Bellare2015], [Aviram2022].¶
In essence, this document assumes that KDF( H(input1)  H(input2))
is a dual PRF in practice, for suitable choices of key derivation function KDF
and hash function H
, despite not having formal security proofs. It has been proposed as a KEM combiner, for example in [ID.ietftlshybriddesign]. As the academic literature evolves, it may become appropriate to obsolete this document with a KEM combiner based on a provably secure dual PRF.¶
A.2. KEM primitives
In modern cryptographic design, KEM algorithms seek to have indistinguishability under adaptive chosen ciphertext attack (INDCCA2). FFor hybrid KEMs we desire the additional property that even if one input is controlled by an attacker, then combiner leaks no information about the other input.¶
There are two ways to achieve such a hybrid KEM combiner; either by designing a combiner that is robust to one of the inputs being maliciouslychosen, called a dual PRF. See Appendix A.1 for a discussion about the current state of dual PRF research. Or alternatively by only allowing the hybridization of KEMs where a malicious kemEncaps() algorithm cannot control the shared secret derived by the victim's kemDecaps() algorithm and then combining the shared secrets in a trivial way.¶
The following sections analyze commonlyused KEM algorithms to show that they have the following two properties, and are therefore suitable for use with the simplified KEM combiner presented in Section 3, Figure 2.¶
 A malicious encapsulater cannot control the length of the KEM output (shared secret) that will be derived by the decapsulater.¶
 A malicious encapsulater cannot control the value of the KEM output (shared secret) that will be derived by the decapsulater. We define a KEM output to be "controlled by an attacker" if a maliciouslywritten kemEncaps() function can cause the victim's kemDecaps() algorithm to produce a shared secret either of a length chosen by the attacker, or to take on a given value with higher probability than can be obtained via rejection sampling on the shared secret output of kemEncaps().¶
A.3. RSAKEM
RSA encryption [RFC3447] can be promoted into a KEM as per [RFC5990] which defines a key transport based on RSAKEM.¶
1. Generate a random integer z between 0 and n1 (see note), and convert z to a byte string Z of length nLen, most significant byte first: z = RandomInteger (0, n1) Z = IntegerToString (z, nLen) 2. Encrypt the random integer z using the recipient's public key (n,e), and convert the resulting integer c to a ciphertext C, a byte string of length nLen: c = z^e mod n C = IntegerToString (c, nLen) 3. Derive a keyencrypting key KEK of length kekLen bytes from the byte string Z using the underlying key derivation function: KEK = KDF (Z, kekLen) 4. Wrap the keying data K with the keyencrypting key KEK using the underlying keywrapping scheme to obtain wrapped keying data WK: WK = Wrap (KEK, K) 5. Concatenate the ciphertext C and the wrapped keying data WK to obtain the encrypted keying data EK: EK = C  WK 6. Output the encrypted keying data EK.¶
where Steps 1  3 define "RSAKEM", which is considered here. Steps 4  6 define "Key Transport based on RSAKEM" and is out of scope for this analysis as we assume that any RSAKEM construction intended for use in a hybrid KEM would use the KEK
output from Step 3 as the final shared secret.¶
Here the transported symmetric key, KEK
, is the KEM output (shared secret) ss
as defined in Section 1.1. The encapsulater must choose a key derivation function KDF
and declare it in the RSAKEM parameters. The decapsulater may refuse to perform the the decapsulation if it does not like the encapsulater's choice of KDF
, therefore it can be modeled as a random oracle producing an output of fixed length. The attacker is free to choose z
, but assuming a strong choice of KDF
, they cannot control either the length or the value KEK
beyond what can be obtained by rejection sampling, thus satisfying properties 1 and 2 and defined in {.seckemprimitives}}.¶
Therefore RSAKEM is considered to be suitable for use with the simplified KEM combiner defined in Section 3, Figure 2.¶
Security note: This analysis applies to the specific RSAKEM construction defined above. This result is not intended to generalize to all RSAbased key transport mechanisms, as they may not have the same cryptographic properties.¶
A.4. Elliptic Curve DiffieHellman (ECDH)
The elliptic curve DiffieHellman key exchange [SEC1] can be promoted into a KEM in a straightforward way by assuming an ephemeralstatic (ES) mode where def kemEncaps(pk) > (ct, ss)
includes generation of an ephemeral key pair, the public key being included as part of the ciphertext ct
and the private key being discarded upon completion of the encapsulation.¶
According to [SEC1] section 6.1.3:¶
1. Use one of the DiffieHellman primitives specified in Section 3.3 to derive a shared secret field element z ∈ Fq from U's secret key d_U established during the key deployment procedure and V's public key Q_V obtained during the key deployment procedure. If the Diffie Hellman primitive outputs “invalid”, output “invalid” and stop. Decide whether to use the “standard” elliptic curve DiffieHellman primitive or the elliptic curve cofactor DiffieHellman primitive according to the convention established during the setup procedure. 2. Convert z ∈ Fq to an octet string Z using the conversion routine specified in Section 2.3.5. 3. Use the key derivation function KDF established during the setup procedure to generate keying data K of length keydatalen octets from Z and [SharedInfo]. If the key derivation function outputs “invalid”, output “invalid” and stop. 4. Output K.¶
Other key exchange methods defined in [SEC1] follow a similar construction.¶
The attacker is free to choose a private key d_U
which yields a shared secret Z
, but cannot force Z
to take on a chosen value without solving the elliptic curve discrete logarithm problem or performing rejection sampling. Assuming a strong choice of KDF
, the attacker cannot control either the length or the value of KEK
beyond what can be obtained by rejection sampling, thus satisfying properties 1 and 2 and defined in Appendix A.2.¶
Therefore elliptic curve DiffieHellman is considered to be suitable for use with the simplified KEM combiner defined in Section 3, Figure 2.¶
A.5. Edwards Curve DiffieHellman (X25519 / X448)
The elliptic curve DiffieHellman key exchange [SEC1] can be promoted into a KEM in a straightforward way by assuming an ephemeralstatic (ES) mode where def kemEncaps(pk) > (ct, ss)
includes generation of an ephemeral key pair, the public key being included as part of the ciphertext ct
and the private key being discarded upon completion of the encapsulation.¶
According to [RFC7748] section 6.1, the X25519 key exchange is defined as:¶
Alice generates 32 random bytes in a[0] to a[31] and transmits K_A = X25519(a, 9) to Bob, where 9 is the ucoordinate of the base point and is encoded as a byte with value 9, followed by 31 zero bytes. Bob similarly generates 32 random bytes in b[0] to b[31], computes K_B = X25519(b, 9), and transmits it to Alice. Using their generated values and the received input, Alice computes X25519(a, K_B) and Bob computes X25519(b, K_A). Both now share K = X25519(a, X25519(b, 9)) = X25519(b, X25519(a, 9)) as a shared secret. Both MAY check, without leaking extra information about the value of K, whether K is the allzero value and abort if so (see below). Alice and Bob can then use a keyderivation function that includes K, K_A, and K_B to derive a symmetric key.¶
The X448 key exchange follows a similar construction.¶
The attacker is free to choose a private key b
which yields a shared secret K
, but cannot force K
to take on a chosen value without solving the elliptic curve discrete logarithm problem or performing rejection sampling. Assuming a strong choice of KDF
, the attacker cannot control either the length or the value of the derived symmetric key beyond what can be obtained by rejection sampling, thus satisfying properties 1 and 2 and defined in Appendix A.2.¶
Therefore Edwards curve DiffieHellman, X25519 and X448, are considered to be suitable for use with the simplified KEM combiner defined in Section 3, Figure 2.¶
A.6. CRYSTALSKyber
The CRYSTALSKyber kemEncaps() is defined as follows [ID.cfrgschwabekyber]:¶
1.Compute 1. m = H(seed) 2. (Kbar, cpaSeed) = G(m  H(pk)) 3. cpaCipherText = InnerEnc(m, publicKey, cpaSeed) 2.Return 1. cipherText = cpaCipherText 2. sharedSecret = KDF(KBar  H(cpaCipherText))¶
with definitions as per [ID.cfrgschwabekyber].¶
Here the hash functions G
, H
and the key derivation function KDF
are in theory chosen by the encapsulater, but in practice are fixed by the Kyber specification to be H: SHA3256
, G: SHA3512
, and KDF: SHAKE256
, which can be modeled as random oracles. The attacker is free to choose m
, but not the decapsulater's public key pk
, nor do they have control of cpaCipherText
so long as InnerEnc
remains INDCPA secure. Therefore the attacker cannot control the value or length of K
beyond what can be obtained by rejection sampling.¶
Therefore CRYSTALSKyber is considered to be suitable for use with the simplified KEM combiner defined in Section 3, Figure 2.¶
Appendix C. Contributors and Acknowledgements
This document incorporates contributions and comments from a large group of experts. The Editors 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.¶
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].¶
C.1. Making contributions
To be removed before publication.¶
Additional contributions to this draft are welcome. Please see the working copy of this draft at, as well as open issues at:¶
https://github.com/EntrustCorporation/draftounsworthcfrgkemcombiners¶