CFRG M. Ounsworth Internet-Draft Entrust Intended status: Informational A. Wussler Expires: 7 September 2023 Proton 6 March 2023 Combiner function for hybrid key encapsulation mechanisms (Hybrid KEMs) draft-ounsworth-cfrg-kem-combiners-01 Abstract The migration to post-quantum cryptography often calls for performing multiple key encapsulations in parallel and then combining their outputs to derive a single shared secret. This document defines a flexible multi-share KEM combiner to join an arbitrary number of key shares, that is a multi-PRF compatible with NIST SP 800-56Cr2 [SP800-56C]. 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/draft-ounsworth-cfrg-kem-combiners/. 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/draft-ounsworth-cfrg-kem- combiners. 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/. Ounsworth & Wussler Expires 7 September 2023 [Page 1] Internet-Draft KEM Combiner March 2023 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 7 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 . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Key Encapsulation Mechanisms . . . . . . . . . . . . . . 3 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1. KEM/PSK hybrids . . . . . . . . . . . . . . . . . . . . . 3 2.2. PQ/Traditional hybrid KEMs . . . . . . . . . . . . . . . 4 2.3. KEM-based AKE . . . . . . . . . . . . . . . . . . . . . . 4 3. KEM Combiner construction . . . . . . . . . . . . . . . . . . 4 3.1. Protocol binding . . . . . . . . . . . . . . . . . . . . 5 4. Practical instantiations . . . . . . . . . . . . . . . . . . 6 4.1. Hash-and-counter based construction . . . . . . . . . . . 7 4.2. KMAC based construction . . . . . . . . . . . . . . . . . 7 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 6. Security Considerations . . . . . . . . . . . . . . . . . . . 7 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 7.1. Normative References . . . . . . . . . . . . . . . . . . 8 7.2. Informative References . . . . . . . . . . . . . . . . . 8 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 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. Ounsworth & Wussler Expires 7 September 2023 [Page 2] Internet-Draft KEM Combiner March 2023 This document is consistent with all terminology defined in [I-D.driscoll-pqt-hybrid-terminology]. 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 the ciphertext representing an encapsulated key, 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: 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 mechanisms for combining the output of two or more KEMs. 2.1. KEM/PSK hybrids As a post-quantum stop-gap, several IETF protocols have added extensions to allow for mixing a pre-shared key (PSK) into an (EC)DH based key exchange. Examples include CMS [RFC8696] and IKEv2 [RFC8784]. Ounsworth & Wussler Expires 7 September 2023 [Page 3] Internet-Draft KEM Combiner March 2023 2.2. PQ/Traditional hybrid KEMs A post-quantum / traditional hybrid key encapsulation mechanism (hybrid KEM) as defined in [I-D.driscoll-pqt-hybrid-terminology] 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 post-quantum 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 post-quantum migration strategies, examples include TLS 1.3 [I-D.ietf-tls-hybrid-design], IKEv2 [I-D.ietf-ipsecme-ikev2-multiple-ke], X.509; PKIX; CMS [I-D.ounsworth-pq-composite-kem], OpenPGP [I-D.wussler-openpgp-pqc], JOSE / COSE (CITE once Orie's drafts are up). 2.3. KEM-based AKE The need for a KEM-based authenticated key establishment arises, for example, when two communicating parties each have long-term KEM keys (for example in X.509 certificates), and wish to involve both KEM keys in deriving a mutually-authenticated shared secret. In particular this will arise for any protocol that needs to provide post-quantum replacements for static-static (Elliptic Curve) Diffie- Hellman mechanisms. Examples include a KEM replacement for CMP's DHBasedMac [I-D.ietf-lamps-cmp-updates], .. TODO: cite others. 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, where all values are byte arrays. 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, a function that can be keyed by any input. The following simple yet generic construction can be used in all IETF protocols that need to combine the output of two or more KEMs: Ounsworth & Wussler Expires 7 September 2023 [Page 4] Internet-Draft KEM Combiner March 2023 KDF(counter || K_1 || ... || K_n || fixedInfo, outputBits) Figure 1: general KEM combiner construction where: * KDF represents a suitable choice of cryptographic key derivation function, * K_i represent the constant-length input keys, * fixedInfo is some protocol-specific KDF binding, * counter parameter is instantiation-specific and is discussed in Section 4. * outputBits determines the length of the key, * || represents concatenation. In section Section 4 are listed several possible practical instantiations, in compliance with NIST SP-800 56Cr2 [SP800-56C]. Each K_i MUST be constant in length, therefore the secret shares SS_i can be used directly only if they are guaranteed to be constant length. For all other cases, it is REQUIRED to hash them first: K_i = H(SS_i) Any protocols making use of this construction MUST either hash all inputs SS_i, or justify that any un-hashed inputs will always be fixed length. 3.1. Protocol binding The fixedInfo string is a fixed-length string containing some context-specific information. It MUST NOT depend on the secret shares. The intention is to prevent cross-protocol attacks by making this key derivation unique to its protocol context. The fixedInfo string MUST have a definite structure depending on the protocol where all parts are fixed length. This prevents a variable length structure from creating collisions between two different instances. In cases some variable length input is necessary, such as the representation of a public key or an OID, then hashing or padding can be used. The parameter fixedInfo MAY contain any of the following information: Ounsworth & Wussler Expires 7 September 2023 [Page 5] Internet-Draft KEM Combiner March 2023 * Public information about the communication parties, such as their identifiers. * The public keys or certificates contributed by each party to the key-agreement transaction. * Other public and/or private information shared between communication parties before or during the transaction, such as nonces or pre-shared secrets. * An indication of the protocol or application employing the key- derivation method. * Protocol-related information, such as a label or session identifier. * An indication of the key-agreement scheme and/or key-derivation method used. * An indication of the domain parameters associated with the asymmetric key pairs employed for key establishment. * An indication of other parameter or primitive choices. * An indication of how the derived keying material should be parsed, including an indication of which algorithm(s) will use the (parsed) keying material. This is a non-comprehensive list, further information can be found in paragraph 5.8.2 of NIST SP800-56Ar3 [SP800-56A]. 4. Practical instantiations The KDF MUST be instantiated with one of the following Keccak-based option. Each instance defines a function to be used as KDF, a hash H function to optionally derive the K_i, and 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. Ounsworth & Wussler Expires 7 September 2023 [Page 6] Internet-Draft KEM Combiner March 2023 4.1. Hash-and-counter based construction Options 1 and 2 instantiate the KDF using SHA3, specified in NIST FIPS 202 [FIPS202]. To generate an outputBits long secret share SS: * the counter MUST be initialized with the string 0x00000001. * The hash is performed over the string defined in Section 3, and repeated ceil(outputBits/hashSize) times. For each iteration the counter MUST be increased by 0x01. * The strings are concatenated ordered by counter. * The leftmost outputBits are returned as SS. An implementation MUST NOT overflow and reuse the counter and an error MUST be returned when producing more than 2^32 consecutive hashes. 4.2. KMAC based construction Options 3 and 4 are KMAC-based, as specified in NIST SP 800-185 [SP800-185]. The context S MUST be the utf-8 string "KDF", the key K MUST be a context-specific string of at least hashSize bits, and counter MUST be the fixed string 0x00000001. The key K MAY be used as an additional option to perform context separation, in scenarios where fixedInfo is not sufficient. To derive a shared secret SS of desired length, KMAC is called a single time with the input string X defined in Section 3 and length L being outputBits. 5. IANA Considerations None. 6. Security Considerations The proposed instantiations in Section 4 are practical multi-PRFs and this specification limits to the use of Keccak-based constructions. The sponge construction was proven to be indifferentiable from a random oracle [SPONGE]. 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 Ounsworth & Wussler Expires 7 September 2023 [Page 7] Internet-Draft KEM Combiner March 2023 bit string, an adversary has to correctly guess all key shares K_i entirely. 7. References 7.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . 7.2. Informative References [FIPS202] "SHA-3 Standard: Permutation-Based Hash and Extendable- Output Functions", Federal information Processing Standards Publication (FIPS) 202 , 2015, . [I-D.driscoll-pqt-hybrid-terminology] D, F., "Terminology for Post-Quantum Traditional Hybrid Schemes", Work in Progress, Internet-Draft, draft- driscoll-pqt-hybrid-terminology-01, 20 October 2022, . [I-D.ietf-ipsecme-ikev2-multiple-ke] Tjhai, C., Tomlinson, M., Bartlett, G., Fluhrer, S., Van Geest, D., Garcia-Morchon, O., and V. Smyslov, "Multiple Key Exchanges in IKEv2", Work in Progress, Internet-Draft, draft-ietf-ipsecme-ikev2-multiple-ke-12, 1 December 2022, . [I-D.ietf-lamps-cmp-updates] Brockhaus, H., von Oheimb, D., and J. Gray, "Certificate Management Protocol (CMP) Updates", Work in Progress, Internet-Draft, draft-ietf-lamps-cmp-updates-23, 29 June 2022, . [I-D.ietf-tls-hybrid-design] Stebila, D., Fluhrer, S., and S. Gueron, "Hybrid key exchange in TLS 1.3", Work in Progress, Internet-Draft, draft-ietf-tls-hybrid-design-06, 27 February 2023, . Ounsworth & Wussler Expires 7 September 2023 [Page 8] Internet-Draft KEM Combiner March 2023 [I-D.ounsworth-pq-composite-kem] Ounsworth, M. and J. Gray, "Composite KEM For Use In Internet PKI", Work in Progress, Internet-Draft, draft- ounsworth-pq-composite-kem-00, 11 July 2022, . [I-D.wussler-openpgp-pqc] Kousidis, S., Strenzke, F., and A. Wussler, "Post-Quantum Cryptography in OpenPGP", Work in Progress, Internet- Draft, draft-wussler-openpgp-pqc-00, 21 December 2022, . [PQCAPI] Project, N. P.-Q. C., "PQC - API notes", November 2022, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . [RFC8411] Schaad, J. and R. Andrews, "IANA Registration for the Cryptographic Algorithm Object Identifier Range", RFC 8411, DOI 10.17487/RFC8411, August 2018, . [RFC8696] Housley, R., "Using Pre-Shared Key (PSK) in the Cryptographic Message Syntax (CMS)", RFC 8696, DOI 10.17487/RFC8696, December 2019, . [RFC8784] Fluhrer, S., Kampanakis, P., McGrew, D., and V. Smyslov, "Mixing Preshared Keys in the Internet Key Exchange Protocol Version 2 (IKEv2) for Post-quantum Security", RFC 8784, DOI 10.17487/RFC8784, June 2020, . [SP800-185] Kelsey, J., Chan, S., and R. Perln, "SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash, and ParallelHash", NIST Special Publication 800-185 , 2016, . Ounsworth & Wussler Expires 7 September 2023 [Page 9] Internet-Draft KEM Combiner March 2023 [SP800-56A] Barker, E., Chen, L., Roginsky, A., Vassilev, A., and R. Davis, "Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography", NIST Special Publication 800-56A , April 2018, . [SP800-56C] Barker, E., Chen, L., and R. Davis, "Recommendation for Key-Derivation Methods in Key-Establishment Schemes", NIST Special Publication 800-56C , August 2020, . [SPONGE] Bertoni, G., Daemen, J., Peters, M., and G. Assche, "Cryptographic sponge functions", January 2011, . 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, Andreas Huelsing, and Stavros Kousidis. 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 Mike Ounsworth Entrust Limited 2500 Solandt Road – Suite 100 Ottawa, Ontario K2K 3G5 Canada Email: mike.ounsworth@entrust.com Ounsworth & Wussler Expires 7 September 2023 [Page 10] Internet-Draft KEM Combiner March 2023 Aron Wussler Proton AG Switzerland Email: aron@wussler.it Ounsworth & Wussler Expires 7 September 2023 [Page 11]