LAMPS M. Ounsworth Internet-Draft J. Gray Intended status: Standards Track Entrust Expires: 24 February 2024 23 August 2023 Composite KEM For Use In Internet PKI draft-ietf-lamps-pq-composite-kem-00 Abstract The migration to post-quantum cryptography is unique in the history of modern digital cryptography in that neither the old outgoing nor the new incoming algorithms are fully trusted to protect data for the required data lifetimes. The outgoing algorithms, such as RSA and elliptic curve, may fall to quantum cryptalanysis, while the incoming post-quantum algorithms face uncertainty about both the underlying mathematics as well as hardware and software implementations that have not had sufficient maturing time to rule out classical cryptanalytic attacks and implementation bugs. Cautious implementers may wish to layer cryptographic algorithms such that an attacker would need to break all of them in order to compromise the data being protected using either a Post-Quantum / Traditional Hybrid, Post-Quantum / Post-Quantum Hybrid, or combinations thereof. This document, and its companions, defines a specific instantiation of hybrid paradigm called "composite" where multiple cryptographic algorithms are combined to form a single key, signature, or key encapsulation mechanism (KEM) such that they can be treated as a single atomic object at the protocol level. This document defines the structure CompositeCiphertextValue which is a sequence of the respective ciphertexts for each component algorithm. Explicit pairings of algorithms are defined which should meet most Internet needs. For the purpose of combining KEMs, the combiner function from [I-D.ounsworth-cfrg-kem-combiners] is used. This document is intended to be coupled with the composite keys structure define in [I-D.ounsworth-pq-composite-keys] and the CMS KEMRecipientInfo mechanism in [I-D.housley-lamps-cms-kemri]. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Ounsworth & Gray Expires 24 February 2024 [Page 1] Internet-Draft PQ Composite Keys August 2023 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 24 February 2024. 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. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Changes in version -02 . . . . . . . . . . . . . . . . . . . 3 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1. Algorithm Selection Criteria . . . . . . . . . . . . . . 4 2.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 3. Composite KEM Structures . . . . . . . . . . . . . . . . . . 5 3.1. Key Encapsulation Mechanisms (KEMs) . . . . . . . . . . . 5 3.2. kema-CompositeKEM . . . . . . . . . . . . . . . . . . . . 7 3.3. Composite Keys . . . . . . . . . . . . . . . . . . . . . 7 3.3.1. Key Usage Bits . . . . . . . . . . . . . . . . . . . 8 3.4. CompositeCiphertextValue . . . . . . . . . . . . . . . . 8 3.5. CompositKemParameters . . . . . . . . . . . . . . . . . . 8 3.6. Encoding Rules . . . . . . . . . . . . . . . . . . . . . 8 3.7. KEM Combiner . . . . . . . . . . . . . . . . . . . . . . 9 4. Algorithm Identifiers . . . . . . . . . . . . . . . . . . . . 11 4.1. Notes on id-Kyber768-RSA-KMAC256 . . . . . . . . . . . . 13 5. ASN.1 Module . . . . . . . . . . . . . . . . . . . . . . . . 14 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 7. Security Considerations . . . . . . . . . . . . . . . . . . . 18 7.1. Policy for Deprecated and Acceptable Algorithms . . . . . 18 7.2. OR Modes . . . . . . . . . . . . . . . . . . . . . . . . 18 Ounsworth & Gray Expires 24 February 2024 [Page 2] Internet-Draft PQ Composite Keys August 2023 7.3. KEM Combiner . . . . . . . . . . . . . . . . . . . . . . 18 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 18 8.1. Normative References . . . . . . . . . . . . . . . . . . 18 8.2. Informative References . . . . . . . . . . . . . . . . . 20 Appendix A. Samples . . . . . . . . . . . . . . . . . . . . . . 22 Appendix B. Implementation Considerations . . . . . . . . . . . 22 B.1. Backwards Compatibility . . . . . . . . . . . . . . . . . 22 B.1.1. K-of-N modes . . . . . . . . . . . . . . . . . . . . 23 B.1.2. Parallel PKIs . . . . . . . . . . . . . . . . . . . . 24 Appendix C. Intellectual Property Considerations . . . . . . . . 24 Appendix D. Contributors and Acknowledgements . . . . . . . . . 24 D.1. Making contributions . . . . . . . . . . . . . . . . . . 25 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 25 1. Changes in version -02 * Removed all references to generic composite. * Added selection criteria note about requesting new explicit combinations. 2. Introduction During the transition to post-quantum cryptography, there will be uncertainty as to the strength of cryptographic algorithms; we will no longer fully trust traditional cryptography such as RSA, Diffie- Hellman, DSA and their elliptic curve variants, while we may also not fully trust their post-quantum replacements until they have had sufficient scrutiny and time to discover and fix implementation bugs. Unlike previous cryptographic algorithm migrations, the choice of when to migrate and which algorithms to migrate to, is not so clear. Even after the migration period, it may be advantageous for an entity's cryptographic identity to be composed of multiple public-key algorithms. The deployment of composite public keys and composite encryption using post-quantum algorithms will face two challenges * Algorithm strength uncertainty: During the transition period, some post-quantum signature and encryption algorithms will not be fully trusted, while also the trust in legacy public key algorithms will start to erode. A relying party may learn some time after deployment that a public key algorithm has become untrustworthy, but in the interim, they may not know which algorithm an adversary has compromised. Ounsworth & Gray Expires 24 February 2024 [Page 3] Internet-Draft PQ Composite Keys August 2023 * Migration: During the transition period, systems will require mechanisms that allow for staged migrations from fully classical to fully post-quantum-aware cryptography. This document provides a mechanism to address algorithm strength uncertainty by building on [I-D.ounsworth-pq-composite-keys] by providing the format and process for combining multiple cryptographic algorithms into a single key encapsulation operation. Backwards compatibility is not directly covered in this document, but is the subject of Appendix B.1. This document is intended for general applicability anywhere that key establishment or enveloped content encryption is used within PKIX or CMS structures. 2.1. Algorithm Selection Criteria The composite algorithm combinations defined in this document were chosen according to the following guidelines: 1. A single RSA combination is provided (but RSA modulus size not mandated), matched with NIST PQC Level 3 algorithms. 2. Elliptic curve algorithms are provided with combinations on each of the NIST [RFC6090], Brainpool [RFC5639], and Edwards [RFC7748] curves. NIST PQC Levels 1 - 3 algorithms are matched with 256-bit curves, while NIST levels 4 - 5 are matched with 384-bit elliptic curves. This provides a balance between matching classical security levels of post-quantum and traditional algorithms, and also selecting elliptic curves which already have wide adoption. 3. NIST level 1 candidates (Falcon512 and Kyber512) are provided, matched with 256-bit elliptic curves, intended for constrained use cases. The authors wish to note that although all the composite structures defined in this and the companion documents [I-D.ounsworth-pq-composite-keys] and [I-D.ounsworth-pq-composite-sigs] pecifications are defined in such a way as to easily allow 3 or more component algorithms, it was decided to only specify explicit pairs. This also does not preclude future specification of explicit combinations with three or more components. Ounsworth & Gray Expires 24 February 2024 [Page 4] Internet-Draft PQ Composite Keys August 2023 To maximize interoperability, use of the specific algorithm combinations specified in this document is encouraged. If other combinations are needed, a separate specification should be submitted to the IETF LAMPS working group. To ease implementation, these specifications are encouraged to follow the construction pattern of the algorithms specified in this document. 2.2. 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 from [I-D.driscoll-pqt-hybrid-terminology]. In addition, the following terms are used in this document: BER: Basic Encoding Rules (BER) as defined in [X.690]. CLIENT: Any software that is making use of a cryptographic key. This includes a signer, verifier, encrypter, decrypter. COMBINER: A combiner specifies how multiple shared secrets are combined into a single shared secret. DER: Distinguished Encoding Rules as defined in [X.690]. KEM: A key encapsulation mechanism as defined in Section 3.1. PKI: Public Key Infrastructure, as defined in [RFC5280]. SHARED SECRET: A value established between two communicating parties for use as cryptographic key material, but which cannot be learned by an active or passive adversary. This document is concerned with shared secrets established via public key cryptagraphic operations. 3. Composite KEM Structures 3.1. Key Encapsulation Mechanisms (KEMs) We borrow here the definition of a key encapsulation mechanism (KEM) from [I-D.ietf-tls-hybrid-design], in which a KEM is a cryptographic primitive that consists of three algorithms: * KeyGen() -> (pk, sk): A probabilistic key generation algorithm, which generates a public key pk and a secret key sk. Ounsworth & Gray Expires 24 February 2024 [Page 5] Internet-Draft PQ Composite Keys August 2023 * Encaps(pk) -> (ct, ss): A probabilistic encapsulation algorithm, which takes as input a public key pk and outputs a ciphertext ct and shared secret ss. * Decaps(sk, ct) -> ss: A decapsulation algorithm, which takes as input a secret key sk and ciphertext ct and outputs a shared secret ss, or in some cases a distinguished error value. This document is not concerned with the KeyGen() algorithm of a KEM, but it is included above for completeness. The KEM interface defined above differs from both traditional key transport mechanism (for example for use with KeyTransRecipientInfo defined in [RFC5652]), and key agreement (for example for use with KeyAgreeRecipientInfo defined in [RFC5652]). The KEM interface was chosen as the interface for a composite key exchange because it allows for arbitrary combinations of component algorithm types since both key transport and key agreement mechanisms can be promoted into KEMs in the following ways: A key transport mechanism can be transformed into a KEM.Encaps(pk) by generating a random shared secret ss and performing KeyTrans.Encrypt(pk, ss) -> ct; and into a KEM.Decaps(sk, ct) by KeyTrans.Decrypt(sk, ct) -> ss. This follows the pattern of RSA-KEM [RFC5990]. A key agreement mechanism can be transformed into a KEM.Encaps(pk) by generating an ephemeral key pair (pk_e, sk_e), and performing KeyAgree(pk, sk_e) -> (ss, pk_e); and into a KEM.Decaps(sk, ct) by completing the key agreement as KeyAgree(pk_e, sk) -> ss. A composite KEM allows two or more underlying key transport, key agreement, or KEM algorithms to be combined into a single cryptographic operations by performing each operation, transformed to a KEM as outline above, and using a specified combiner function to combine the two or more component shared secrets into a single shared secret. The main security property for KEMs is indistinguishability under adaptive chosen ciphertext attack (IND-CCA2), which means that shared secret values should be indistinguishable from random strings even given the ability to have other arbitrary ciphertexts decapsulated. By using the KEM combiner defined in [I-D.ounsworth-cfrg-kem-combiners], the composite KEMs defined in this document inherit the IND-CCA2 security from the general combiner. Ounsworth & Gray Expires 24 February 2024 [Page 6] Internet-Draft PQ Composite Keys August 2023 TODO: needs more formal analysis that the methods of transforming KeyTrans and KeyAgree meet this. 3.2. kema-CompositeKEM The ASN.1 algorithm object for a composite KEM is: kema-CompositeKEM KEM-ALGORITHM ::= { IDENTIFIER TYPE OBJECT IDENTIFIER VALUE CompositeCiphertextValue PARAMS TYPE CompositeKemParams ARE required PUBLIC-KEYS { pk-Composite } SMIME-CAPS { IDENTIFIED BY id-alg-composite } } The following is an explanation how KEM-ALGORITHM elements are used to create Composite KEMs: +=====================+=======================================+ | SIGNATURE-ALGORITHM | Definition | | element | | +=====================+=======================================+ | IDENTIFIER | The Object ID used to identify the | | | composite Signature Algorithm | +---------------------+---------------------------------------+ | VALUE | The Sequence of BIT STRINGS for each | | | component signature value | +---------------------+---------------------------------------+ | PARAMS | Parameters of type CompositeKemParams | | | may be provided when required | +---------------------+---------------------------------------+ | PUBLIC-KEYS | The composite key required to produce | | | the composite signature | +---------------------+---------------------------------------+ | SMIME_CAPS | Not needed for composite | +---------------------+---------------------------------------+ Table 1 3.3. Composite Keys A composite KEM MAY be associated with a composite public key as defined in [I-D.ounsworth-pq-composite-keys], but MAY also be associated with multiple public keys from different sources, for example multiple X.509 certificates, or multiple cryptographic modules. In the latter case, composite KEMs MAY be used as the mechanism for carrying multiple ciphertexts in a non-composite hybrid encryption equivalent of those described for digital signatures in [I-D.becker-guthrie-noncomposite-hybrid-auth]. Ounsworth & Gray Expires 24 February 2024 [Page 7] Internet-Draft PQ Composite Keys August 2023 3.3.1. Key Usage Bits When using composite KEM keys in a structure which defines a key usage (such as in an X509Certificate as defined in [RFC5280]), the following key usage MUST be used. keyEncipherment Additional key usages SHOULD not be used. 3.4. CompositeCiphertextValue The compositeCipherTextValue is a concatenation of the ciphertexts of the underlying component algorithms. It is represented in ASN.1 as follows: CompositeCiphertextValue ::= SEQUENCE SIZE (2..MAX) OF OCTET STRING 3.5. CompositKemParameters Composite KEM parameters are defined as follows and MAY be included when a composite KEM algorithm is used with an AlgorithmIdentifier: CompositeKemParams ::= SEQUENCE SIZE (2..MAX) OF AlgorithmIdentifier{ KEM-ALGORITHM, {KEMAlgSet} } The KEM's CompositeKemParams sequence MUST contain the same component algorithms listed in the same order as in the associated CompositePublicKey. For explicit composite algorithms, it is required in cases where one or both of the components themselves have parameters that need to be carried, however the authors have chosen to always carry it in order to simplify parsers. Implementation SHOULD NOT rely directly on the algorithmIDs contained in the CompositeKemParams and SHOULD verify that they match the algorithms expected from the overall composite AlgorithmIdentifier. 3.6. Encoding Rules Many protocol specifications will require that composite KEM data structures be represented by an octet string or bit string. When an octet string is required, the DER encoding of the composite data structure SHALL be used directly. Ounsworth & Gray Expires 24 February 2024 [Page 8] Internet-Draft PQ Composite Keys August 2023 EDNOTE: will this definition include an ASN.1 tag and length byte inside the OCTET STRING object? If so, that's probably an extra unnecessary layer. When a bit string is required, the octets of the DER encoded composite data structure SHALL be used as the bits of the bit string, with the most significant bit of the first octet becoming the first bit, and so on, ending with the least significant bit of the last octet becoming the last bit of the bit string. In the interests of simplicity and avoiding compatibility issues, implementations that parse these structures MAY accept both BER and DER. 3.7. KEM Combiner TODO: as per https://www.enisa.europa.eu/publications/post-quantum- cryptography-integration-study section 4.2, might need to specify behaviour in light of KEMs with a non-zero failure probility. This document follows the construction of [I-D.ounsworth-cfrg-kem-combiners], which is repeated here for clarity: KDF(counter || k_1 || ... || k_n || fixedInfo, outputBits) where k_i = H(ss_i || ct_i) where: * KDF and H, and outputBits represent a hash functions suitable to the chosen KEMs, * fixedInfo any additional context string provided by the protocol, * counter is fixed to the 32-bit value 0x00000001, * || represents concatenation. Each registered composite KEM algorithm must specify the exact KEM combiner construction that is to be used. For convenience we define the following KMAC-basid intantiations of KEM combiner: Ounsworth & Gray Expires 24 February 2024 [Page 9] Internet-Draft PQ Composite Keys August 2023 +==============+=========+==========+============+ | KEM Combiner | KDF | H | outputBits | +==============+=========+==========+============+ | KMAC128/256 | KMAC128 | SHA3-256 | 256 | +--------------+---------+----------+------------+ | KMAC256/384 | KMAC256 | SHA3-512 | 384 | +--------------+---------+----------+------------+ | KMAC256/512 | KMAC256 | SHA3-512 | 512 | +--------------+---------+----------+------------+ Table 2: KEM Combiners KMAC is defined in NIST SP 800-185 [SP800-185]. The KMAC(K, X, L, S) parameters are instantiated as follows: * K: the ASCI value of the name of the Kem Type OID. * X: the value "0x00000001 || k_1 || ... || k_n || fixedInfo", where k_i = H(ss_i || ct_i), as defined above. * L: integer representation of outputBits. * S: empty string. ~~~ BEGIN EDNOTE ~~~ these choices are somewhat arbitrary but aiming to match security level of the input KEMs. Feedback welcome. * Kyber512: KMAC128/256 * Kyber768: KMAC256/384 * Kyber1024 KMAC256/512 ~~~ END EDNOTE ~~~ For example, the KEM combiner instantiation of the first entry of Table 3 would be: ss = KMAC128("id-Kyber512-ECDH-P256-KMAC128", 0x00000001 || SHA3-256(ss_1 || ct_1) || SHA3-256(ss_2 || ct_2) || fixedInfo, 256, "") Ounsworth & Gray Expires 24 February 2024 [Page 10] Internet-Draft PQ Composite Keys August 2023 4. Algorithm Identifiers This table summarizes the list of explicit composite Signature algorithms by the key and signature OID and the two component algorithms which make up the explicit composite algorithm. These are denoted by First Signature Alg, and Second Signature Alg. The OID referenced are TBD and MUST be used only for prototyping and replaced with the final IANA-assigned OIDS. The following prefix is used for each: replace with the String "2.16.840.1.114027.80.5.2" Therefore .1 is equal to 2.16.840.1.114027.80.5.2.1 The "KEM Combiner" column refers to the definitions in Section 3.7. Ounsworth & Gray Expires 24 February 2024 [Page 11] Internet-Draft PQ Composite Keys August 2023 +=======================+============+=========+===============+===========+ |KEM Type OID |OID |First |Second |KEM | | | |Algorithm|Algorithm |Combiner | +=======================+============+=========+===============+===========+ |id-Kyber512-ECDH- |.1 |Kyber512 |ECDH-P256 |KMAC128/256| |P256-KMAC128 | | | | | +-----------------------+------------+---------+---------------+-----------+ |id-Kyber512-ECDH- |.2 |Kyber512 |ECDH- |KMAC128/256| |brainpoolP256r1-KMAC128| | |brainpoolp256r1| | +-----------------------+------------+---------+---------------+-----------+ |id- |.3 |Kyber512 |X25519 |KMAC128/256| |Kyber512-X25519-KMAC128| | | | | +-----------------------+------------+---------+---------------+-----------+ |id-Kyber768-RSA-KMAC256|.4 |Kyber768 |RSA-KEM |KMAC256/384| +-----------------------+------------+---------+---------------+-----------+ |id-Kyber768-ECDH- |.5 |Kyber768 |ECDH-P256 |KMAC256/384| |P256-KMAC256 | | | | | +-----------------------+------------+---------+---------------+-----------+ |id-Kyber768-ECDH- |.6 |Kyber768 |ECDH- |KMAC256/384| |brainpoolP256r1-KMAC256| | |brainpoolp256r1| | +-----------------------+------------+---------+---------------+-----------+ |id- |.7 |Kyber768 |X25519 |KMAC256/384| |Kyber768-X25519-KMAC256| | | | | +-----------------------+------------+---------+---------------+-----------+ |id-Kyber1024-ECDH- |.8 |Kyber1024|ECDH-P384 |KMAC256/512| |P384-KMAC256 | | | | | +-----------------------+------------+---------+---------------+-----------+ |id-Kyber1024-ECDH- |.9 |Kyber1024|ECDH- |KMAC256/512| |brainpoolP384r1-KMAC256| | |brainpoolP384r1| | +-----------------------+------------+---------+---------------+-----------+ |id- |.10|Kyber1024|X448 |KMAC256/512| |Kyber1024-X448-KMAC256 | | | | | +-----------------------+------------+---------+---------------+-----------+ Table 3: Composite KEM key types The table above contains everything needed to implement the listed explicit composite algorithms, with the exception of some special notes found below in this section. See the ASN.1 module in section Section 5 for the explicit definitions of the above Composite signature algorithms. Full specifications for the referenced algorithms can be found as follows: * _ECDH_: There does not appear to be a single IETF definition of ECDH, so we refer to the following: Ounsworth & Gray Expires 24 February 2024 [Page 12] Internet-Draft PQ Composite Keys August 2023 - _ECDH NIST_: SHALL be Elliptic Curve Cryptography Cofactor Diffie-Hellman (ECC CDH) as defined in section 5.7.1.2 of [SP.800-56Ar3]. - _ECDH BSI / brainpool_: SHALL be Elliptic Curve Key Agreement algorithm (ECKA) as defined in section 4.3.1 of [BSI-ECC] * _Kyber_: [I-D.ietf-lamps-kyber-certificates] * _RSA-KEM_: [RFC5990] * _X25519 / X448_: [RFC8410] EDNOTE: I believe that [SP.800-56Ar3] and [BSI-ECC] give equivalent and interoperable algorithms, so maybe this is extranuous detail to include? 4.1. Notes on id-Kyber768-RSA-KMAC256 Use of RSA-KEM [RFC5990] deserves a special explanation. GenericHybridParameters is defined in [RFC5990], repeated here for clarity: GenericHybridParameters ::= { kem KeyEncapsulationMechanism, dem DataEncapsulationMechanism } The GenericHybridParameters.kem MUST be id-kem-rsa as defined in [RFC5990]: id-kem-rsa OID ::= { is18033-2 key-encapsulation-mechanism(2) rsa(4) } The associated parameters for id-kem-rsa have type RsaKemParameters: RsaKemParameters ::= { keyDerivationFunction KeyDerivationFunction, keyLength KeyLength } For use with id-Kyber768-RSA-KMAC256, the keyDerivationFunction SHALL be id-sha3-384 and keyLength SHALL be 384. Ounsworth & Gray Expires 24 February 2024 [Page 13] Internet-Draft PQ Composite Keys August 2023 EDNOTE: I'm borrowing id-sha3-384 from draft-turner-lamps-adding- sha3-to-pkix-00, which looks ilke was abandoned. Do we have PKIX OIDs for SHA3? EDNOTE: Since the crypto is fixed, we could omit the parameters entirely and expect implementations to re-constitute the params structures as necessary in order to call into lower-level crypto libraries. TODO: there must be a way to put all this the ASN.1 Module rather than just specifying it as text? 5. ASN.1 Module Composite-KEM-2023 {iso(1) identified-organization(3) dod(6) internet(1) security(5) mechanisms(5) pkix(7) id-mod(0) id-mod-composite-kems(TBD)} DEFINITIONS IMPLICIT TAGS ::= BEGIN EXPORTS ALL; IMPORTS AlgorithmIdentifier{} FROM AlgorithmInformation-2009 -- RFC 5912 [X509ASN1] { iso(1) identified-organization(3) dod(6) internet(1) security(5) mechanisms(5) pkix(7) id-mod(0) id-mod-algorithmInformation-02(58) } KEM-ALGORITHM, KEMAlgSet FROM KEMAlgorithmInformation-2023 { iso(1) identified-organization(3) dod(6) internet(1) security(5) mechanisms(5) pkix(7) id-mod(0) id-mod-kemAlgorithmInformation-2023(99) } id-rsa-kem, GenericHybridParameters FROM CMS-RSA-KEM { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-9(9) smime(16) modules(0) cms-rsa-kem(21) } id-RSASSA-PSS, RSASSA-PSS-Params FROM PKCS-1 { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) modules(0) pkcs-1(1) Ounsworth & Gray Expires 24 February 2024 [Page 14] Internet-Draft PQ Composite Keys August 2023 } id-Kyber512-ECDH-P256-KMAC128, pk-Kyber512-ECDH-P256-KMAC128, id-Kyber512-ECDH-brainpoolP256r1-KMAC128, pk-Kyber512-ECDH-brainpoolP256r1-KMAC128, id-Kyber512-X25519-KMAC128, pk-Kyber512-X25519-KMAC128, id-Kyber768-RSA-KMAC256, pk-Kyber768-RSA-KMAC256, id-Kyber768-ECDH-P256-KMAC256, pk-Kyber768-ECDH-P256-KMAC256, id-Kyber768-ECDH-brainpoolP256r1-KMAC256, pk-Kyber768-ECDH-brainpoolP256r1-KMAC256, id-Kyber768-X25519-KMAC256, pk-Kyber768-X25519-KMAC256, id-Kyber1024-ECDH-P384-KMAC256, pk-Kyber1024-ECDH-P384-KMAC256, id-Kyber1024-ECDH-brainpoolP384r1-KMAC256, pk-Kyber1024-ECDH-brainpoolP384r1-KMAC256, id-Kyber1024-X448-KMAC256, pk-Kyber1024-X448-KMAC256 FROM CompositeKeys-2023 {iso(1) identified-organization(3) dod(6) internet(1) security(5) mechanisms(5) pkix(7) id-mod(0) id-mod-composite-keys(98)}; -- -- Composite structures -- CompositeCiphertextValue ::= SEQUENCE SIZE (2..MAX) OF OCTET STRING CompositeKemParams ::= SEQUENCE SIZE (2..MAX) OF AlgorithmIdentifier{ KEM-ALGORITHM, {KEMAlgSet} } ExplicitCompositeKemParams{KEM-ALGORITHM:FirstKemAlg, KEM-ALGORITHM:SecondKemAlg} ::= SEQUENCE { kemAlgorithm1 AlgorithmIdentifier { KEM-ALGORITHM, {FirstKemAlg}}, kemAlgorithm2 AlgorithmIdentifier { KEM-ALGORITHM, {SecondKemAlg}} } kema-explicitCompositeKEM{OBJECT IDENTIFIER:id, PUBLIC-KEY:publicKeyObject, CompositeKemParams} KEM-ALGORITHM ::= { Ounsworth & Gray Expires 24 February 2024 [Page 15] Internet-Draft PQ Composite Keys August 2023 IDENTIFIER id VALUE CompositeCiphertextValue PARAMS TYPE CompositeKemParams ARE required PUBLIC-KEYS {publicKeyObject} } -- Explicit Composite KEMs kema-Kyber512-ECDH-P256-KMAC128 KEM-ALGORITHM ::= kema-explicitCompositeKEM{id-Kyber512-ECDH-P256-KMAC128, pk-Kyber512-ECDH-P256-KMAC128, ExplicitCompositeKemParams{{kema-Kyber512TBD}, {kema-ecdh-p256}} } --TODO: `kema-ecdh-p256` does not actually exist yet. kema-Kyber512-ECDH-brainpoolP256r1-KMAC128 KEM-ALGORITHM ::= kema-explicitCompositeKEM{id-Kyber512-ECDH-brainpoolP256r1-KMAC128, pk-Kyber512-ECDH-brainpoolP256r1-KMAC128, ExplicitCompositeKemParams{{kema-Kyber512TBD}, {kema-ecdh-brainpoolp256r1}} } --TODO: `kema-ecdh-brainpoolp256r1` does not actually exist yet. kema-Kyber512-X25519-KMAC128 KEM-ALGORITHM ::= kema-explicitCompositeKEM{id-Kyber512-X25519-KMAC128, pk-Kyber512-X25519-KMAC128, ExplicitCompositeKemParams{{kema-Kyber512TBD}, {kema-x25519}} } --TODO: `kema-x25519` does not actually exist yet. kema-Kyber768-RSA-KMAC256 KEM-ALGORITHM ::= kema-explicitCompositeKEM{id-Kyber768-RSA-KMAC256, pk-Kyber768-RSA-KMAC256, ExplicitCompositeKemParams{{kema-Kyber512TBD}, {kema-kem-rsa}} } kema-Kyber768-ECDH-P256-KMAC256 KEM-ALGORITHM ::= kema-explicitCompositeKEM{id-Kyber768-ECDH-P256-KMAC256, pk-Kyber768-ECDH-P256-KMAC256, ExplicitCompositeKemParams{{kema-Kyber768TBD}, {kema-ecdh-p256}} } --TODO: `kema-ecdh-p256` does not actually exist yet. Ounsworth & Gray Expires 24 February 2024 [Page 16] Internet-Draft PQ Composite Keys August 2023 kema-Kyber768-ECDH-brainpoolP256r1-KMAC256 KEM-ALGORITHM ::= kema-explicitCompositeKEM{id-Kyber768-ECDH-brainpoolP256r1-KMAC256, pk-Kyber768-ECDH-brainpoolP256r1-KMAC256, ExplicitCompositeKemParams{{kema-Kyber768TBD}, {kema-ecdh-brainpoolp256r1}} } --TODO: `kema-ecdh-brainpoolp256r1` does not actually exist yet. kema-Kyber768-X25519-KMAC256 KEM-ALGORITHM ::= kema-explicitCompositeKEM{id-Kyber768-X25519-KMAC256, pk-Kyber768-X25519-KMAC256, ExplicitCompositeKemParams{{kema-Kyber768TBD}, {kema-x25519}} } --TODO: `kema-x25519` does not actually exist yet. kema-Kyber1024-ECDH-P384-KMAC256 KEM-ALGORITHM ::= kema-explicitCompositeKEM{id-Kyber1024-ECDH-P384-KMAC256, pk-Kyber1024-ECDH-P384-KMAC256, ExplicitCompositeKemParams{{kema-Kyber1024TBD}, {kema-ecdh-p384}} } --TODO: `kema-ecdh-p384` does not actually exist yet. kema-Kyber1024-ECDH-brainpoolP384r1-KMAC256 KEM-ALGORITHM ::= kema-explicitCompositeKEM{id-Kyber1024-ECDH-brainpoolP384r1-KMAC256, pk-Kyber1024-ECDH-brainpoolP384r1-KMAC256, ExplicitCompositeKemParams{{kema-Kyber1024TBD}, {kema-ecdh-brainpoolp384r1}}} --TODO: `kema-ecdh-brainpoolp384r1` does not actually exist yet. kema-Kyber1024-X448-KMAC256 KEM-ALGORITHM ::= kema-explicitCompositeKEM{id-Kyber1024-X448-KMAC256, pk-Kyber1024-X448-KMAC256, ExplicitCompositeKemParams{{kema-Kyber1024TBD}, {kema-x448}} } --TODO: `kema-x448` does not actually exist yet. END 6. IANA Considerations The following need to be assigned by IANA: * The OID for the ASN.1 module Composite-KEM-2023 Ounsworth & Gray Expires 24 February 2024 [Page 17] Internet-Draft PQ Composite Keys August 2023 TODO 7. Security Considerations 7.1. Policy for Deprecated and Acceptable Algorithms Traditionally, a public key, certificate, or signature contains a single cryptographic algorithm. If and when an algorithm becomes deprecated (for example, RSA-512, or SHA1), it is obvious that structures using that algorithm are implicitly revoked. In the composite model this is less obvious since implementers may decide that certain cryptographic algorithms have complementary security properties and are acceptable in combination even though one or both algorithms are deprecated for individual use. As such, a single composite public key, certificate, signature, or ciphertext may contain a mixture of deprecated and non-deprecated algorithms. Specifying behaviour in these cases is beyond the scope of this document, but should be considered by Implementers and potentially in additional standards. EDNOTE: Max is working on a CRL mechanism to accomplish this. 7.2. OR Modes TODO -- we'll need security consideration analysis of whatever OR modes we choose. 7.3. KEM Combiner This document uses directly the KEM Combiner defined in [I-D.ounsworth-cfrg-kem-combiners] and therefore inherits all of its security considerations, which the authors believe have all been addressed in the concrete choices for explicit composites. 8. References 8.1. Normative References [BSI-ECC] Federal Office for Information Security (BSI), "Technical Guideline BSI TR-03111: Elliptic Curve Cryptography. Version 2.10", 1 June 2018. [I-D.housley-lamps-cms-kemri] Housley, R., Gray, J., and T. Okubo, "Using Key Encapsulation Mechanism (KEM) Algorithms in the Cryptographic Message Syntax (CMS)", Work in Progress, Ounsworth & Gray Expires 24 February 2024 [Page 18] Internet-Draft PQ Composite Keys August 2023 Internet-Draft, draft-housley-lamps-cms-kemri-02, 20 February 2023, . [I-D.ietf-lamps-kyber-certificates] Turner, S., Kampanakis, P., Massimo, J., and B. Westerbaan, "Internet X.509 Public Key Infrastructure - Algorithm Identifiers for Kyber", Work in Progress, Internet-Draft, draft-ietf-lamps-kyber-certificates-00, 26 September 2022, . [I-D.ounsworth-pq-composite-keys] Ounsworth, M., Gray, J., Pala, M., and J. Klaußner, "Composite Public and Private Keys For Use In Internet PKI", Work in Progress, Internet-Draft, draft-ounsworth- pq-composite-keys-04, 13 March 2023, . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R., and W. Polk, "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008, . [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, "Elliptic Curve Cryptography Subject Public Key Information", RFC 5480, DOI 10.17487/RFC5480, March 2009, . [RFC5652] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70, RFC 5652, DOI 10.17487/RFC5652, September 2009, . [RFC5990] Randall, J., Kaliski, B., Brainard, J., and S. Turner, "Use of the RSA-KEM Key Transport Algorithm in the Cryptographic Message Syntax (CMS)", RFC 5990, DOI 10.17487/RFC5990, September 2010, . Ounsworth & Gray Expires 24 February 2024 [Page 19] Internet-Draft PQ Composite Keys August 2023 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10.17487/RFC8017, November 2016, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . [RFC8410] Josefsson, S. and J. Schaad, "Algorithm Identifiers for Ed25519, Ed448, X25519, and X448 for Use in the Internet X.509 Public Key Infrastructure", RFC 8410, DOI 10.17487/RFC8410, August 2018, . [RFC8411] Schaad, J. and R. Andrews, "IANA Registration for the Cryptographic Algorithm Object Identifier Range", RFC 8411, DOI 10.17487/RFC8411, August 2018, . [SHA3] National Institute of Standards and Technology (NIST), "SHA-3 Standard: Permutation-Based Hash and Extendable- Output Functions, FIPS PUB 202, DOI 10.6028/ NIST.FIPS.202", August 2015, . [SP.800-56Ar3] National Institute of Standards and Technology (NIST), "Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography", April 2018, . [SP800-185] National Institute of Standards and Technology (NIST), "SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash", December 2016, . [X.690] ITU-T, "Information technology - ASN.1 encoding Rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)", ISO/IEC 8825-1:2015, November 2015. 8.2. Informative References Ounsworth & Gray Expires 24 February 2024 [Page 20] Internet-Draft PQ Composite Keys August 2023 [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-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-04, 11 January 2022, . [I-D.ounsworth-cfrg-kem-combiners] Ounsworth, M., Wussler, A., and S. Kousidis, "Combiner function for hybrid key encapsulation mechanisms (Hybrid KEMs)", Work in Progress, Internet-Draft, draft-ounsworth- cfrg-kem-combiners-03, 13 March 2023, . [I-D.ounsworth-pq-composite-sigs] Ounsworth, M., Gray, J., and M. Pala, "Composite Signatures For Use In Internet PKI", Work in Progress, Internet-Draft, draft-ounsworth-pq-composite-sigs-08, 13 March 2023, . [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation", RFC 5639, DOI 10.17487/RFC5639, March 2010, . [RFC6090] McGrew, D., Igoe, K., and M. Salter, "Fundamental Elliptic Curve Cryptography Algorithms", RFC 6090, DOI 10.17487/RFC6090, February 2011, . [RFC7296] Kaufman, C., Hoffman, P., Nir, Y., Eronen, P., and T. Kivinen, "Internet Key Exchange Protocol Version 2 (IKEv2)", STD 79, RFC 7296, DOI 10.17487/RFC7296, October 2014, . [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, January 2016, . Ounsworth & Gray Expires 24 February 2024 [Page 21] Internet-Draft PQ Composite Keys August 2023 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, . [RFC8551] Schaad, J., Ramsdell, B., and S. Turner, "Secure/ Multipurpose Internet Mail Extensions (S/MIME) Version 4.0 Message Specification", RFC 8551, DOI 10.17487/RFC8551, April 2019, . Appendix A. Samples TBD Appendix B. Implementation Considerations This section addresses practical issues of how this draft affects other protocols and standards. EDNOTE 10: Possible topics to address: * The size of these certs and cert chains. * In particular, implications for (large) composite keys / signatures / certs on the handshake stages of TLS and IKEv2. * If a cert in the chain is a composite cert then does the whole chain need to be of composite Certs? * We could also explain that the root CA cert does not have to be of the same algorithms. The root cert SHOULD NOT be transferred in the authentication exchange to save transport overhead and thus it can be different than the intermediate and leaf certs. * We could talk about overhead (size and processing). * We could also discuss backwards compatibility. * We could include a subsection about implementation considerations. B.1. Backwards Compatibility As noted in the introduction, the post-quantum cryptographic migration will face challenges in both ensuring cryptographic strength against adversaries of unknown capabilities, as well as providing ease of migration. The composite mechanisms defined in this document primarily address cryptographic strength, however this section contains notes on how backwards compatibility may be obtained. Ounsworth & Gray Expires 24 February 2024 [Page 22] Internet-Draft PQ Composite Keys August 2023 The term "ease of migration" is used here to mean that existing systems can be gracefully transitioned to the new technology without requiring large service disruptions or expensive upgrades. The term "backwards compatibility" is used here to mean something more specific; that existing systems as they are deployed today can interoperate with the upgraded systems of the future. These migration and interoperability concerns need to be thought about in the context of various types of protocols that make use of X.509 and PKIX with relation to key establishment and content encryption, from online negotiated protocols such as TLS 1.3 [RFC8446] and IKEv2 [RFC7296], to non-negotiated asynchronous protocols such as S/MIME signed email [RFC8551], as well as myriad other standardized and proprietary protocols and applications that leverage CMS [RFC5652] encrypted structures. B.1.1. K-of-N modes ~~~ BEGIN EDNOTE ~~~ In the context of encryption, K-of-N modes could mean one of two things: Type 1: sender uses a subset This would mean the sender (encrypter) uses a subset of K the N component keys within the receiver's public key. The obvious way to combine them is with skipping the unused keys / algorithms and emitting a NULL ciphertext in their place. This mechanism is straight-forward and allows ease of migration where a sender encounters a composite encryption public key where it does not support all component algorithms. It also supports performance optimization where, for example, a receiver can be issued a key with many component keys and a sender can choose the highest-performance subset that are still considered safe. Type 2: receiver uses a subset This would mean that the sender (encrypter) uses all N of the component keys within the receiver's public key in such a way that the receiver (decrypter) only needs to use K private keys to decrypt the message. This implies the need for some kind of Shamir's-like secret splitting scheme. This is a reasonably complex mechanism and it's currently unclear if there are any use-cases that require such a mechanism. ~~~ END EDNOTE ~~~ Ounsworth & Gray Expires 24 February 2024 [Page 23] Internet-Draft PQ Composite Keys August 2023 B.1.2. Parallel PKIs We present the term "Parallel PKI" to refer to the setup where a PKI end entity possesses two or more distinct public keys or certificates for the same identity (name), but containing keys for different cryptographic algorithms. One could imagine a set of parallel PKIs where an existing PKI using legacy algorithms (RSA, ECC) is left operational during the post-quantum migration but is shadowed by one or more parallel PKIs using pure post quantum algorithms or composite algorithms (legacy and post-quantum). Equipped with a set of parallel public keys in this way, a client would have the flexibility to choose which public key(s) or certificate(s) to use in a given signature operation. For negotiated protocols, the client could choose which public key(s) or certificate(s) to use based on the negotiated algorithms. For non-negotiated protocols, the details for obtaining backwards compatibility will vary by protocol, but for example in CMS [RFC5652]. EDNOTE: I copied and pruned this text from [I-D.ounsworth-pq-composite-sigs]. It probably needs to be fleshed out more as we better understand the implementation concerns around composite encryption. Appendix C. Intellectual Property Considerations The following IPR Disclosure relates to this draft: https://datatracker.ietf.org/ipr/3588/ EDNOTE: I don't think this applies to this draft. Appendix D. 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 year in pursuit of this document: Serge Mister (Entrust), Ali Noman (Entrust), Scott Fluhrer (Cisco), Jan Klaussner (D-Trust), Max Pala (CableLabs), and Douglas Stebila (University of Waterloo). Ounsworth & Gray Expires 24 February 2024 [Page 24] Internet-Draft PQ Composite Keys August 2023 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]. D.1. Making contributions 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/draft-composite-kem/ Authors' Addresses Mike Ounsworth Entrust Limited 2500 Solandt Road -- Suite 100 Ottawa, Ontario K2K 3G5 Canada Email: mike.ounsworth@entrust.com John Gray Entrust Limited 2500 Solandt Road -- Suite 100 Ottawa, Ontario K2K 3G5 Canada Email: john.gray@entrust.com Ounsworth & Gray Expires 24 February 2024 [Page 25]