Crypto Forum D. Connolly Internet-Draft SandboxAQ Intended status: Informational R. Barnes Expires: 8 January 2026 Cisco 7 July 2025 Concrete Hybrid PQ/T Key Encapsulation Mechanisms draft-irtf-cfrg-concrete-hybrid-kems-00 Abstract PQ/T Hybrid Key Encapsulation Mechanisms (KEMs) combine "post- quantum" cryptographic algorithms, which are safe from attack by a quantum computer, with "traditional" algorithms, which are not. CFRG has developed a general framework for creating hybrid KEMs. In this document, we define concrete instantiations of this framework to illustrate certain properties of the framework and simplify implementors' choices. About This Document This note is to be removed before publishing as an RFC. The latest revision of this draft can be found at https://cfrg.github.io/draft-irtf-cfrg-concrete-hybrid-kems/draft- irtf-cfrg-concrete-hybrid-kems.html. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-irtf- cfrg-concrete-hybrid-kems/. Discussion of this document takes place on the Crypto Forum Research Group mailing list (mailto:cfrg@ietf.org), which is archived at https://mailarchive.ietf.org/arch/search/?email_list=cfrg. Subscribe at https://www.ietf.org/mailman/listinfo/cfrg/. Source for this draft and an issue tracker can be found at https://github.com/cfrg/draft-irtf-cfrg-concrete-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/. Connolly & Barnes Expires 8 January 2026 [Page 1] Internet-Draft concrete-hybrid-kems July 2025 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 8 January 2026. Copyright Notice Copyright (c) 2025 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. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Conventions and Definitions . . . . . . . . . . . . . . . . . 3 3. Concrete Nominal Group and KEM Instances . . . . . . . . . . 3 3.1. Nominal Groups . . . . . . . . . . . . . . . . . . . . . 3 3.1.1. P-256 and P-384 Nominal Groups . . . . . . . . . . . 4 3.1.2. Curve25519 Nominal Group . . . . . . . . . . . . . . 5 3.2. Concrete KEM Instances . . . . . . . . . . . . . . . . . 5 3.2.1. ML-KEM-768 and ML-KEM-1024 . . . . . . . . . . . . . 5 3.3. Concrete PRG instances . . . . . . . . . . . . . . . . . 6 3.3.1. SHAKE256 . . . . . . . . . . . . . . . . . . . . . . 6 3.4. Concrete KDF instances . . . . . . . . . . . . . . . . . 6 3.4.1. SHA-3 . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Concrete Hybrid KEM Instances . . . . . . . . . . . . . . . . 7 4.1. QSF-MLKEM768-P256-SHA3256-SHAKE256 . . . . . . . . . . . 7 4.2. QSF-MLKEM768-X25519-SHA3256-SHAKE256 . . . . . . . . . . 8 4.3. QSF-MLKEM1024-P384-SHA3256-SHAKE256 . . . . . . . . . . . 8 5. Security Considerations . . . . . . . . . . . . . . . . . . . 9 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 7.1. Normative References . . . . . . . . . . . . . . . . . . 9 7.2. Informative References . . . . . . . . . . . . . . . . . 10 Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 11 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 11 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 Connolly & Barnes Expires 8 January 2026 [Page 2] Internet-Draft concrete-hybrid-kems July 2025 1. Introduction PQ/T Hybrid Key Encapsulation Mechanisms (KEMs) combine "post- quantum" cryptographic algorithms, which are safe from attack by a quantum computer, with "traditional" algorithms, which are not. Such KEMs are secure against a quantum attacker as long as the PQ algorithm is secure, and remain secure against traditional attackers even if the PQ algorithm is not secure. [HYBRID-KEMS] defines a general framework for creating hybrid KEMs. It includes multiple specific mechanisms for combining a PQ algorithm with a traditional algorithm, with different performance properties and security requirements for the underlying algorithms. In this document, we describe instances of these different specific combiners, with specific choices for the underlying algorithms. The choices described here illustrate the security analysis required to make choices that meet the requirements of the general framework, and can serve as a baseline for application designers. We also provide test vectors for these instances so that implementors can verify the correctness of their implementations. 2. Conventions and Definitions 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. We make extensive use of the terminology in [HYBRID-KEMS]. 3. Concrete Nominal Group and KEM Instances This document introduces concrete hybrid KEM instances that in turn depend on concrete KEM and nominal group instances. This section introduces the nominal groups and KEM instances used for concrete hybrid KEM instances, specified in line with the abstraction from [HYBRID-KEMS]. Section 3.1 defines the concrete nominal groups, and Section 3.2 defines the nominal KEMs. 3.1. Nominal Groups This section specifies concrete nominal groups that implement the abstraction in [HYBRID-KEMS]. It includes groups based on the NIST curves P-256 and P-384, as well as a group based on Curve25519. Connolly & Barnes Expires 8 January 2026 [Page 3] Internet-Draft concrete-hybrid-kems July 2025 3.1.1. P-256 and P-384 Nominal Groups The NIST P-256 and P-384 elliptic curves are defined in [SP800-186]. They are widely used for key agreement and digital signature. In this section, we define how they meet the Nominal Group interface described in [HYBRID-KEMS]. Group elements are elliptic curve points, represented as byte strings in the compressed representation defined by the Elliptic-Curve-Point- to-Octet-String function in [SEC1]. The Nominal Group algorithms are the same for both groups: * Exp(p, x) -> q: This function computes scalar multiplication between the input element (or point) p and the scalar x, according to the group law for the curve specified in [SP800-186]. * RandomScalar(seed) -> k: Implemented by converting seed to an integer using the Octet-String-to-Integer function in [SEC1], and then reducing the resulting integer modulo the group order. * ElementToSharedSecret(p) -> ss: The shared secret is the X coordinate of the elliptic curve point p, encoded as an Nss-byte string using the Field-Element-to-Octet-String function in [SEC1]. The group constants for the P-256 group are as follows: * Nseed: 48 * Nscalar: 32 * Nelem: 33 * Nss: 32 The group constants for the P-384 group are as follows: * Nseed: 72 * Nscalar: 48 * Nelem: 49 * Nss: 48 Connolly & Barnes Expires 8 January 2026 [Page 4] Internet-Draft concrete-hybrid-kems July 2025 3.1.2. Curve25519 Nominal Group The following functions for the Curve25519 nominal group are defined: * Exp(p, x) -> q: Implemented by X25519(x, p) from [RFC7748]. * RandomScalar(seed) -> k: Implemented by sampling and outputting 32 random bytes from a cryptographically secure pseudorandom number generator. * ElementToSharedSecret(p) -> ss: Implemented by the identity function, i.e., by outputting P. The following constants are also defined. * Nseed: 32 * Nscalar: 32 * Nelem: 32 * Nss: 32 3.2. Concrete KEM Instances This section specifies concrete KEM instances that implement the KEM abstraction from [HYBRID-KEMS]. 3.2.1. ML-KEM-768 and ML-KEM-1024 The ML-KEM-768 and ML-KEM-1024 KEMs are defined in [FIPS203]. The algorithms defined in that specification map to the KEM abstraction in [HYBRID-KEMS] as follows: * GenerateKeyPair() -> (ek, dk): Implemented as KeyGen in Section 7.1 of [FIPS203]. * DeriveKeyPair(seed) -> (ek, dk): Implemented as KeyGen_internal(seed[0:32], seed[32:64]), where KeyGen_internal is defined in Section 6 of [FIPS203]. * Encaps(ek) -> (ct, ss): Implemented as Encaps in Section 7.2 of [FIPS203]. * Decaps(dk, ct) -> ss: Implemented as Encaps in Section 7.3 of [FIPS203]. The KEM constants for ML-KEM-768 are as follows: Connolly & Barnes Expires 8 January 2026 [Page 5] Internet-Draft concrete-hybrid-kems July 2025 * Nseed: 64 * Nek: 1216 * Ndk: 32 * Nct: 1120 * Nss: 32 The KEM constants for ML-KEM-1024 are as follows: * Nseed: 64 * Nek: 1629 * Ndk: 32 * Nct: 1629 * Nss: 32 3.3. Concrete PRG instances This section specifies concrete PRG instances that implement the PRG abstraction from [HYBRID-KEMS] and meet the required security definitions. 3.3.1. SHAKE256 SHAKE256 is an extendable-output function (XOF) defined in the SHA-3 specification [FIPS202]. It can be used as a PRG for arbitrary values of Nout. When SHAKE256 is used as the PRG component in a hybrid KEM, it is implcit that Nout == KEM_T.Nseed + KEM_PQ.Nseed or Nout == Group_T.Nseed + KEM_PQ.Nseed as appropriate. 3.4. Concrete KDF instances This section specifies concrete KDF instances that implement the KDF abstraction from [HYBRID-KEMS] and meet the required security definitions. 3.4.1. SHA-3 The SHA-3 hash function is defined in [FIPS202]. It produces a 32-byte output, so it is appropriate for use in hybrid KEMs with Nss = 32. Connolly & Barnes Expires 8 January 2026 [Page 6] Internet-Draft concrete-hybrid-kems July 2025 4. Concrete Hybrid KEM Instances This section instantiates the following concrete KEMs: QSF-MLKEM768-P256-SHA3256-SHAKE256: A hybrid KEM composing ML- KEM-768 and P-256 using the QSF scheme, with SHAKE256 as the PRG and SHA3-256 as the KDF. QSF-MLKEM768-X25519-SHA3256-SHAKE256: A hybrid KEM composing ML- KEM-768 and Curve25519 using the QSF scheme, with SHAKE256 as the PRG and SHA3-256 as the KDF. This construction is identical to the X-Wing construction in [XWING-SPEC]. QSF-MLKEM1024-P384-SHA3256-SHAKE256: A hybrid KEM composing ML- KEM-1024 and P-384 using the QSF scheme, with SHAKE256 as the PRG and SHA3-256 as the KDF. Each instance specifies the PQ and traditional KEMs being combined, the combiner construction from [HYBRID-KEMS], the label to use for domain separation in the combiner function, as well as the PRG and KDF functions to use throughout. 4.1. QSF-MLKEM768-P256-SHA3256-SHAKE256 This hybrid KEM is heavily based on [XWING], using the QSF combiner from [HYBRID-KEMS]. In particular, it has the same exact design but uses P-256 instead of X25519 as the the traditional component of the algorithm. It has the following parameters. * Group_T: P-256 Section 3.1.1 * KEM_PQ: ML-KEM-768 Section 3.2.1 * PRG: SHAKE-256 [FIPS202] * KDF: SHA3-256 [FIPS202] * Label: QSF-P256-MLKEM768-SHAKE256-SHA3256 The KEM constants for the resulting hybrid KEM are as follows: * Nseed: 32 * Nek: 1217 * Ndk: 32 * Nct: 1121 Connolly & Barnes Expires 8 January 2026 [Page 7] Internet-Draft concrete-hybrid-kems July 2025 * Nss: 32 4.2. QSF-MLKEM768-X25519-SHA3256-SHAKE256 This hybrid KEM is identical to X-Wing [XWING-SPEC]. It has the following parameters. * Group_T: Curve25519 Section 3.1.2 * KEM_PQ: ML-KEM-768 Section 3.2.1 * PRG: SHAKE-256 [FIPS202] * KDF: SHA3-256 [FIPS202] * Label: \.//^\ (This label does not follow the same pattern as the other KEMs here, but was chosen for compatibility with the X-Wing specification.) The following constants for the hybrid KEM are also defined: * Nseed: 32 * Nek: 1216 * Ndk: 32 * Nct: 1120 * Nss: 32 4.3. QSF-MLKEM1024-P384-SHA3256-SHAKE256 QSF-MLKEM1024-P384-SHA3256-SHAKE256 has the following parameters: * Group_T: P-384 Section 3.1.1 * `KEM_PQ: ML-KEM-1024 Section 3.2.1 * PRG: SHAKE-256 [FIPS202] * KDF: HKDF-SHA-256 [RFC5869] * Label: QSF-P384-MLKEM1024-SHAKE256-SHA3256 The following constants for the hybrid KEM are also defined: Connolly & Barnes Expires 8 January 2026 [Page 8] Internet-Draft concrete-hybrid-kems July 2025 * Nseed: 32 * Nek: 1629 * Ndk: 32 * Nct: 1629 * Nss: 32 5. Security Considerations [[ TODO ]] 6. IANA Considerations This document has no IANA actions. 7. References 7.1. Normative References [FIPS202] "SHA-3 standard :: permutation-based hash and extendable- output functions", National Institute of Standards and Technology (U.S.), DOI 10.6028/nist.fips.202, 2015, . [FIPS203] "Module-lattice-based key-encapsulation mechanism standard", National Institute of Standards and Technology (U.S.), DOI 10.6028/nist.fips.203, August 2024, . [HYBRID-KEMS] Connolly, D., "Hybrid PQ/T Key Encapsulation Mechanisms", Work in Progress, Internet-Draft, draft-irtf-cfrg-hybrid- kems-03, 25 February 2025, . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand Key Derivation Function (HKDF)", RFC 5869, DOI 10.17487/RFC5869, May 2010, . Connolly & Barnes Expires 8 January 2026 [Page 9] Internet-Draft concrete-hybrid-kems July 2025 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, January 2016, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . [SP800-186] Chen, L., Moody, D., Regenscheid, A., Robinson, A., and K. Randall, "Recommendations for Discrete Logarithm-based Cryptography:: Elliptic Curve Domain Parameters", National Institute of Standards and Technology, DOI 10.6028/nist.sp.800-186, February 2023, . 7.2. Informative References [ANSIX9.62] ANS, "Public Key Cryptography for the Financial Services Industry: the Elliptic Curve Digital Signature Algorithm (ECDSA)", ANS X9.62-2005, November 2005. [CDM23] Cremers, C., Dax, A., and N. Medinger, "Keeping Up with the KEMs: Stronger Security Notions for KEMs and automated analysis of KEM-based protocols", 2023, . [KSMW2024] Kraemer, J., Struck, P., and M. Weishaupl, "Binding Security of Implicitly-Rejecting KEMs and Application to BIKE and HQC", n.d., . [SCHMIEG2024] Schmieg, S., "Unbindable Kemmy Schmidt: ML-KEM is neither MAL-BIND-K-CT nor MAL-BIND-K-PK", 2024, . [SEC1] "Elliptic Curve Cryptography, Standards for Efficient Cryptography Group, ver. 2", 2009, . [XWING] "X-Wing: The Hybrid KEM You’ve Been Looking For", 2024, . Connolly & Barnes Expires 8 January 2026 [Page 10] Internet-Draft concrete-hybrid-kems July 2025 [XWING-SPEC] Connolly, D., Schwabe, P., and B. Westerbaan, "X-Wing: general-purpose hybrid post-quantum KEM", Work in Progress, Internet-Draft, draft-connolly-cfrg-xwing-kem- 07, 3 May 2025, . Appendix A. Test Vectors [[ TODO ]] Acknowledgments [[ TODO ]] Authors' Addresses Deirdre Connolly SandboxAQ Email: durumcrustulum@gmail.com Richard Barnes Cisco Email: rlb@ipv.sx Connolly & Barnes Expires 8 January 2026 [Page 11]