Composite KEM For Use In Internet PKI

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.¶
4. A single SPHINCS+ combination is provided for use cases that wish to put hash-based signatures into hybrid combination.¶
5. A generic composite algorithm is provided for implementers who wish to use combinations not listed here, without the overhead of defining new OIDs. Caution should be exercised to avoid issues with compatibility and complex cryptographic policy mechanisms.¶

The authors wish to note that although all the composite structures defined in this and the companion composite signatures [I-D.ounsworth-pq-composite-sigs] and composite signatures [I-D.ounsworth-pq-composite-sigs] specifications are defined in such a way as to easily allow 3 or more component algorithms, it was decided to only specify explicit pairs. The generic composite algorithm allows for an arbitrary number of components. This also does not preclude future specification of explicit combinations with three or more components.¶

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.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.¶
• 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.¶

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:¶

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].¶

  keyEncipherment

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.¶

Generic composite algorithms must carry the list of component KEM algorithms so that the reciever knows which algorithms to use. 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.¶

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:¶

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, "")

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.¶

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?¶

4.2. Notes on Generic Composite

The id-alg-composite-kem-KMAC128 and id-alg-composite-kem-KMAC256 object identifiers are used for identifying a generic composite KEM algorithm. This allows arbitrary combinations of component key transport, key agreement and KEM algorithms without needing the combination to be pre-registered or standardized. Thes generic KEM composite algorithms use KMAC128 and KMAC256-based KEM combiners and so are intended for use with component KEM algorithms that target the 128 bit or 256 bit security levels respectively.¶

When the id-alg-composite-kem-KMAC128 or id-alg-composite-kem-KMAC256 object identifiers are used with an AlgorithmIdentifier, the AlgorithmIdentifier.parameters MUST be of type CompositeKemParams containing an AlgorithmIdentifier for each component algorithm in the same order as the ciphertexts appear in the corresponding CompositeCiphertextValue`.¶

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 both explicit and generic composites.¶

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.¶

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.¶

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/¶