LAMPS M. Ounsworth
Internet-Draft J. Gray
Intended status: Standards Track Entrust
Expires: 12 January 2023 11 July 2022
Composite KEM For Use In Internet PKI
draft-ounsworth-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 cryptanalysis, 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. For digital signatures, this is
referred to as "dual", and for encryption key establishment this as
referred to as "hybrid". This document, and its companions, defines
a specific instantiation of the dual and 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.
EDNOTE: the terms "dual" and "hybrid" are currently in flux. We
anticipate an Informational draft to normalize terminology, and will
update this draft accordingly.
This document defines a Composite key encapsulation mechanism (KEM)
procedure, for use with Composite keys which consist of combinations
of Encryption or KEM algorithms for each composite component
algorithm. This document also introduces the idea of assigning an
Object Identifier (OID) to a shared secret combiner so that stronger
combiners can be implemented in the future without needing to re-
issue this specification.
This document is intended to be coupled with the composite keys
structure define in [I-D.ounsworth-pq-composite-keys] and the CMS
KEM-TRANS mechanism in [I-D.perret-prat-lamps-cms-pq-kem].
Ounsworth & Gray Expires 12 January 2023 [Page 1]
Internet-Draft PQ Composite Keys July 2022
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/.
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 12 January 2023.
Copyright Notice
Copyright (c) 2022 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
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. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4
2. Composite KEM Structures . . . . . . . . . . . . . . . . . . 5
2.1. Key Encapsulation Mechanisms (KEMs) . . . . . . . . . . . 5
2.2. Composite Keys . . . . . . . . . . . . . . . . . . . . . 7
2.2.1. Key Usage Bits . . . . . . . . . . . . . . . . . . . 7
2.3. CompositeCiphertextValue . . . . . . . . . . . . . . . . 7
2.4. Encoding Rules . . . . . . . . . . . . . . . . . . . . . 7
3. KEM Algorithm Identifiers . . . . . . . . . . . . . . . . . . 8
3.1. id-alg-composite-kem . . . . . . . . . . . . . . . . . . 8
3.2. Other Explicit Algorithms . . . . . . . . . . . . . . . . 9
4. Combiner Algorithm Identifiers . . . . . . . . . . . . . . . 10
4.1. NULL . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2. id-composite-kdf-combiner . . . . . . . . . . . . . . . . 11
5. Composite Encapsulation process . . . . . . . . . . . . . . . 12
Ounsworth & Gray Expires 12 January 2023 [Page 2]
Internet-Draft PQ Composite Keys July 2022
6. Composite Key Decapsulation . . . . . . . . . . . . . . . . . 14
7. In Practice . . . . . . . . . . . . . . . . . . . . . . . . . 15
7.1. Backwards Compatibility . . . . . . . . . . . . . . . . . 15
7.1.1. K-of-N modes . . . . . . . . . . . . . . . . . . . . 16
7.1.2. Parallel PKIs . . . . . . . . . . . . . . . . . . . . 17
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17
9. Security Considerations . . . . . . . . . . . . . . . . . . . 17
9.1. Policy for Deprecated and Acceptable Algorithms . . . . . 17
9.2. OR Modes . . . . . . . . . . . . . . . . . . . . . . . . 18
9.3. Cryptographic review of combiner . . . . . . . . . . . . 18
9.3.1. Need for a KDF within the combiner . . . . . . . . . 18
9.3.2. APOP Attack on concatenated keys . . . . . . . . . . 18
9.3.3. Aviram2022 . . . . . . . . . . . . . . . . . . . . . 19
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 19
10.1. Normative References . . . . . . . . . . . . . . . . . . 19
10.2. Informative References . . . . . . . . . . . . . . . . . 21
Appendix A. Examples . . . . . . . . . . . . . . . . . . . . . . 22
Appendix B. ASN.1 Module . . . . . . . . . . . . . . . . . . . . 22
Appendix C. Intellectual Property Considerations . . . . . . . . 23
Appendix D. Contributors and Acknowledgements . . . . . . . . . 23
D.1. Making contributions . . . . . . . . . . . . . . . . . . 24
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24
1. 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 12 January 2023 [Page 3]
Internet-Draft PQ Composite Keys July 2022
* 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 Section 7.1.
This document is intended for general applicability anywhere that key
establishment or enveloped content encryption is used within PKIX or
CMS structures.
1.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.
The following terms are used in this document:
ALGORITHM: An information object class for identifying the type of
cryptographic key being encapsulated.
BER: Basic Encoding Rules (BER) as defined in [X.690].
CLIENT: Any software that is making use of a key at runtime. This
includes a signer, verifier, encrypter, decrypter.
COMBINER: A combiner specifies how multiple shared secrets are
combined into a single shared secret. It is expected that combiners
will need to evolve with discovery of cryptanalytic attacks, so this
document takes the approach of assigning Object Identifiers (OIDs) to
combiners so that stronger combiners can be implemented in the
future.
COMPONENT ALGORITHM: A single basic algorithm which is contained
within a composite algorithm.
COMPOSITE ALGORITHM: An algorithm which is a sequence of two or more
component algorithms.
DER: Distinguished Encoding Rules as defined in [X.690].
Ounsworth & Gray Expires 12 January 2023 [Page 4]
Internet-Draft PQ Composite Keys July 2022
KEM: A key encapsulation mechanism as defined in Section 2.1.
POST-QUANTUM ALGORITHM: Any cryptographic algorithm which is believed
to be resistant to classical and quantum cryptanalysis, such as the
algorithms being considered for standardization by NIST.
PUBLIC / PRIVATE KEY: The public and private portion of an asymmetric
cryptographic key, making no assumptions about which algorithm.
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.
2. Composite KEM Structures
2.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 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:
Ounsworth & Gray Expires 12 January 2023 [Page 5]
Internet-Draft PQ Composite Keys July 2022
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.
EDNOTE: it would be really nice for security proofs if definition of
KEM included that the bits of the shared secret output need to be
uniformly distributed (ie IND-CCA), because for example it would then
be safe to XOR or truncate them. While the NIST PQC candidates all
seem to do this, we could not find a definition of "KEM" that
includes it as a requirement.
A weaker security notion is indistinguishability under chosen
plaintext attack (IND-CPA), which means that the shared secret values
should be indistinguishable from random strings given a copy of the
public key. IND-CPA roughly corresponds to security against a
passive attacker, and sometimes corresponds to one-time key exchange.
The composite KEM mechanisms meets these security properties if and
only if the component primitives meet them.
TODO: needs more formal analysis that the methods of transforming
KeyTrans and KeyAgree meet this.
EDNOTE: Discussed use of ASN.1 to combine the shared secrets. ASN.1
is nice because it embeds the length values for us. Decided instead
to run each component shared secret through the supplied KDF which
will normalize all the lengths.
Ounsworth & Gray Expires 12 January 2023 [Page 6]
Internet-Draft PQ Composite Keys July 2022
2.2. Composite Keys
A composite key is a single key object that performs an atomic
cryptographic operation as defined in
[I-D.ounsworth-pq-composite-keys].
2.2.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 RFC 5280), the
following key usage MUST be used.
keyEncipherment
Additional key usages SHOULD not be used. The main intent for this
keyEncipherment is to encapsulate (encrypt) another key. This is the
main purpose of a KEM algorithm, and composite-KEM does not deviate
from this intent.
EDNOTE: The main argument for using keyEncipherment verses
keyAgreement is that multiple parties are required to contribute to a
key agreement verses a single party in keyEncipherment.
EDNOTE: It is recognized that KEMS will be added into other PKIX and
X509 standards and LAMPS needs to make sure they all make the same
choice about the key usage of a KEM key.
2.3. 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 BIT STRING
2.4. 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.
Ounsworth & Gray Expires 12 January 2023 [Page 7]
Internet-Draft PQ Composite Keys July 2022
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. KEM Algorithm Identifiers
The following algorithm Identifiers and their associated parameters
are used with composite KEM.
3.1. id-alg-composite-kem
The id-alg-composite-kem object identifier is 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.
id-alg-composite-kem OBJECT IDENTIFIER ::= {
joint-iso-itu-t(2) country(16) us(840) organization(1)
entrust(114027) Algorithm(80) Composite(4) KEM (5) }
EDNOTE: this is a temporary OID for the purposes of prototyping. We
are requesting IANA to assign a permanent OID, see Section 6.
Which yields an information object:
TODO - LAMPS needs to define a KEM-ALGORITHM - extension to RFC 5912
- Bring to IETF. We just made up the prefix "kema" (for "KEM
algorithm") is that the right prefix?
kema-CompositeKEM KEM-ALGORITHM ::= {
IDENTIFIER id-alg-composite-kem
VALUE CompositeCiphertextValue
PARAMS composite-kem-params
PUBLIC-KEYS { pk-Composite }
SMIME-CAPS { IDENTIFIED BY id-alg-composite } }
}
For Composite KEM, we define a composite KEM Algorithm ID as:
The following algorithm parameters MUST be included:
Ounsworth & Gray Expires 12 January 2023 [Page 8]
Internet-Draft PQ Composite Keys July 2022
composite-kem-params ::= SEQUENCE {
combiner AlgorithmIdentifier
}
EDNOTE: this ASN.1 could be simplified to composite-kem-params ::=
AlgorithmIdentifier to save a couple bytes on the wire, but we're
presenting it this way for now for readability.
EDNOTE: does the (generic) params need to also carry a list of
AlgorithmIdentifiers that were used in the encryption? With
signatures we need this to prevent the verifier from coming up with
false validity by using the wrong verification algorithm(s). With
encryption I think it's less important because either your private
key works or it doesn't, no harm done by trying to decrypt with the
wrong alg.
If no, or a NULL, combiner is specified, then {#sect-null-combiner}
applies.
See Ednote below for a discussion on some possible combiner modes
3.2. Other Explicit Algorithms
This variant provides a rigid way of specifying supported
combinations of algorithms.
The motivation for this variant is to make it easier to reference and
enforce specific combinations of algorithms. The authors envision
this being useful for client-server negotiated protocols, protocol
designers who wish to place constraints on allowable algorithm
combinations in the protocol specification, as well as audited
environments that wish to prove that only certain combinations will
be supported by clients.
Explicit algorithms must define a new signature algorithm which
consists of:
* A new algorithm identifier OID for the explicit algorithm.
* The algorithm identifier OID and PUBLIC-KEY type of each component
algorithm.
* Algorithm parameters either declared ABSENT, or defined with a
type and encoding.
TODO: lay out the details.
Ounsworth & Gray Expires 12 January 2023 [Page 9]
Internet-Draft PQ Composite Keys July 2022
4. Combiner Algorithm Identifiers
This section defines concrete shared secret combiners that may be
used with composite KEM.
~~~ BEGIN EDNOTE ~~~
EDNOTE: We need to add a KDF-based combiner here. Suggestions are:
Option 0)
SS = SS1 || SS2 || .. || SSn with fixed length KEM algs.
Option 1)
SS = KDF( SS1 || SS2 || .. || SSn ) with fixed length KEM algs.
Option 1b)
SS = KDF( pad(SS1, len_kdf) || pad(SS2, len_kdf) )
Option 2)
SS = KDF( KDF(SS1) || KDF(SS2) || .. || KDF(SSn) )
Option 2b)
SS = KDF(SS1) XOR KDF(SS2) XOR .. XOR KDF(SSn)
Option 3)
The combiner suggested in [Aviram2022].
At present we are opting for Option 2.
QUESTION: Should the choice of combiner be assigned an OID and made
agile? If not, then we perhaps we need a version field within the
composite kem structure to allow for future agility. Answer: for -00
of this document we have decided YES, but we can revisit this.
~~~ END EDNOTE ~~~
4.1. NULL
If no, or NULL, parameters are supplied, then the default combiner
mode SHOULD be simple concatenation.
SS = SS1 || SS2 || .. || SSn
Ounsworth & Gray Expires 12 January 2023 [Page 10]
Internet-Draft PQ Composite Keys July 2022
This mode is often appropriate, and complies with NIST SP-56Cr2, when
the protocol making use of this composite KEM will use the shared
secret output to derive a cryptographic key via a KDF, making it
uncessessary to use a combiner within composite KEM.
Security consideration: protocols that allow the NULL combiner MUST
ensure either that none of the component shared secrets are directly
controllable by an attacker (which allows for attacks similar to
those discussed in Section 9.3.2), or that appropriate mitigations
have been put into place.
4.2. id-composite-kdf-combiner
This section defines a KDF-based shared secret combiner.
id-composite-kdf-combiner OBJECT IDENTIFIER ::= { TBD }
It MUST carry parameters
alg-composite-kdf-combiner-params ::= SEQUENCE {
kdf AlgorithmIdentifier
}
to specify the KDF to be used.
EDNOTE: this ASN.1 could be simplified to alg-composite-kdf-combiner-
params ::= AlgorithmIdentifier to save a couple bytes on the wire,
but we're presenting it this way for now for readability.
The behaviour of this combiner is: SS = KDF( KDF(SS1) || KDF(SS2) ||
.. || KDF(SSn) ) where || denotes contatenation.
Formally:
Input:
SS1, SS2, .., SSn Shared secrets to combine
Output:
SS Combined shared secret.
1. SS = KDF( KDF(SS1) || KDF(SS2) || .. || KDF(SSn) )
The intent of this combiner is to frustrate known cryptanalytic
attacks by normalizing the component shared secrets to a common fixed
length (dictated by the output length of the supplied KDF), as well
as attacks that exploit known weaknesses in the underlying hash
function since, short of a full pre-image attack, an attacker who is
able to control SSi will still not be able to control KDF(SSi).
Ounsworth & Gray Expires 12 January 2023 [Page 11]
Internet-Draft PQ Composite Keys July 2022
EDNOTE: this combiner needs cryptographic review.
EDNOTE: Do we need domain separation in case other protocols use the
same shared secrets in the same construction? Something like KDF(
ASCII("compositeKEM") || KDF(SS1) || KDF(SS2) || .. || KDF(SSn) ) ?
5. Composite Encapsulation process
Composite key encapsulations takes a CompositePublicKey as its input.
The CompositePublicKey MUST contain composite keys (Pi .. Pn) which
represent an algorithm which is a KEM (Key Encapsulation Method), or
an algorithm that contains encryption or decryption primitive. For
example (RSA).
This operation outputs a shared-secret and cipher text.
COMBINER is a function used to combine multiple shared secrets as
defined in Section 4.
This process employs the transformations from KeyTransport or
keyAgreement to KEM as described in Section 2.1.
Ounsworth & Gray Expires 12 January 2023 [Page 12]
Internet-Draft PQ Composite Keys July 2022
Input:
PK1, PK2 .. PKn Encryption public keys. See note below on
composite inputs.
A1, A2, ... An Component keyTransport, keyAgreement, or
KEM algorithms. See note below on composite
inputs.
COMBINER A combiner function.
SIZE The length of shared secret to generate
when transforming a keyTransport into a KEM.
Output: SS, CT
1. for i := 1 to n
if Ai is of type KEM:
SSi, CTi := encaps(PKi)
else, if Ai is of type keyTransport:
SSi := random_bits(SIZE)
CTi := encrypt(SSi, PKi)
else, if Ai is of type keyAgreement:
PKe, SKe := keyGen()
SSi := keyAgree(PKi, SKe)
CTi := PKe
2. SS = COMBINER(SS1, SS2, .., SSn)
CT = CT1, CT2, .., CTn
Note on composite inputs: the method of providing the list of
component keys and algorithms is flexible and beyond the scope of
this pseudo-code, for example they may be carried in
CompositePublicKey structure. It is also possible to perform a
composite KEM that combines ciphertexts for distinct recipient keys
stored, for example, in separate X.509 certificates. Variations in
the process to accommodate particular private key storage mechanisms,
for example when distinct keys stored in separate software or
hardware keystores, are considered to be conformant to this document
so long as it produces the same output as the process sketched above.
Since recursive composite public keys are disallowed in [I-
D.ounsworth-pq-composite-keys], no component ciphertext may itself be
composite; ie the encopsulation process MUST fail if any of the
public keys P1, P2, .., Pn or algorithm identifiers A1, A2, .., An
are composite with the OID id-alg-composite.
Ounsworth & Gray Expires 12 January 2023 [Page 13]
Internet-Draft PQ Composite Keys July 2022
6. Composite Key Decapsulation
Composite key decapsulations takes a CompositePrivateKey as its input
and the sequence of Cipher texts (ct1 .. ctn) computed by the
composite key encapsulation method. The CompositePrivateKey MUST
contain composite keys (Pi .. Pn) which represent an algorithm which
is a KEM (Key Encapsulation Method), or an algorithm that contains
encryption or decryption primitive. These keys MUST consist of the
same component keys in the same order as the Composite Key
Encapsulation process that generated them.
This operation outputs a shared-secret.
COMBINER is a function used to combine multiple shared secrets as
defined in Section 4.
This process employs the transformations from KeyTransport or
keyAgreement to KEM as described in Section 2.1.
Input: CompositePrivateKey = SK1, SK2 .. SKn
SK1, SK2 .. SKn Decryption private keys. See note below on
composite inputs.
A1, A2, ... An Component keyTransport, keyAgreement, or
KEM algorithms. See note below on composite
inputs.
CT1, CT2, .., CTn Ciphertexts. see note below on composite inputs.
COMBINER A combiner function.
Output: SS
1. for i := 1 to n
if Ai is of type KEM:
SSi := decaps(Cti, SKi)
else, if Ai is of type keyEncipherment:
SSi := decrypt(Cti, SKi)
else, if Ai is of type keyAgreement:
PKe := decode(CTi)
SSi := keyAgree(PKe, SKi)
2. Output SS = COMBINER(SS1, SS2, .., SSn)
Ounsworth & Gray Expires 12 January 2023 [Page 14]
Internet-Draft PQ Composite Keys July 2022
Note on composite inputs: the method of providing the list of
component keys and algorithms is flexible and beyond the scope of
this pseudo-code, for example they may be carried in
CompositePublicKey structure. It is also possible to perform a
composite KEM that combines ciphertexts for distinct recipient keys
stored, for example, in separate X.509 certificates. Variations in
the process to accommodate particular private key storage mechanisms,
for example when distinct keys stored in separate software or
hardware keystores, are considered to be conformant to this document
so long as it produces the same output as the process sketched above.
7. In Practice
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.
7.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 12 January 2023 [Page 15]
Internet-Draft PQ Composite Keys July 2022
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.
7.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 the Section 5 but 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 12 January 2023 [Page 16]
Internet-Draft PQ Composite Keys July 2022
7.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.
8. IANA Considerations
The ASN.1 module OID is TBD.
9. Security Considerations
9.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.
Ounsworth & Gray Expires 12 January 2023 [Page 17]
Internet-Draft PQ Composite Keys July 2022
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.
9.2. OR Modes
TODO -- we'll need security consideration analysis of whatever OR
modes we choose.
9.3. Cryptographic review of combiner
EDNOTE: LAMPS should probably request CFRG review of this draft to
ensure that the combiner is resistant to all known cryptographic
attacks.
9.3.1. Need for a KDF within the combiner
It is expected that the majority of uses of the KEM defined in this
document will be within a construct such as
[I-D.perret-prat-lamps-cms-pq-kem] which supplies the KEM output to a
KDF in order to derive a wrapping key. In these cases it is
redundant for the combiner within the composite KEM to also use a
KDF. However, it is possible for protocol designers to want to use a
KEM output -- or a truncation of it -- directly as a symmetric key;
for this purpose we have included a KDF in the composite KEM
construction.
In protocols where the KEM output will be supplied to a KDF, it
should be safe to use a NULL KDF within the composite KEM -- ie the
KDF where KDF(m) = m -- but we leave the details of any such security
analysis to the protocol designers who wish to implement it.
9.3.2. APOP Attack on concatenated keys
See the attack analysis described in summary in [Aviram2021].
The pre-conditions for the described attack are quite strong: namely
that the attacker has full control of both the content and length of
the first shared secret in the combiner, and that the attacker can
perform collision attacks against the underlying KDF.
We believe that, in general, neither of these pre-conditions are met
within PKIX protocols. First, any key transport, key agreement, or
KEM primitive approved for use within PKIX sets a fixed length for
the shared secret that it produces so that the attacker cannot change
the shared secret length between subsequent runs of the same
Ounsworth & Gray Expires 12 January 2023 [Page 18]
Internet-Draft PQ Composite Keys July 2022
protocol. This justification aligns with the justification used for
[I-D.ietf-tls-hybrid-design]. Second, any non-deprecated KDF will
not allow collision attacks.
In addition, the combiner construction defined in this document aims
to provide additional collision resistance on top of that provided by
the underlying KDF.
9.3.3. Aviram2022
See the attack analysis described in summary in [Aviram2022].
This paper is largely critiquing the use of HKDF (HMAC) as a dual-PRF
combiner for two secrets. This is not exactly what we are doing
here.
[Aviram2022] gives the following definition: "If we would like to
combine two keys, either of which might be influenced by an attacker,
we need a dual-PRF as the keycombiner: That is, a function which is a
PRF when keyed by either input.
We believe the construction offered in this document meets this
definition of a dual-PRF so long as the chosen KDF is itself a PRF.
This holds even if the chosen KDF is HKDF with the same key (salt)
used in each KDF() operation.
10. References
10.1. Normative References
[I-D.ounsworth-pq-composite-keys]
Ounsworth, M. and M. Pala, "Composite Public and Private
Keys For Use In Internet PKI", Work in Progress, Internet-
Draft, draft-ounsworth-pq-composite-keys-01, 14 February
2022, <https://www.ietf.org/archive/id/draft-ounsworth-pq-
composite-keys-01.txt>.
[I-D.perret-prat-lamps-cms-pq-kem]
Perret, L., Prat, J., and M. Ounsworth, "Use of Post-
Quantum KEM in the Cryptographic Message Syntax (CMS)",
Work in Progress, Internet-Draft, draft-perret-prat-lamps-
cms-pq-kem-00, 22 November 2021,
<https://www.ietf.org/archive/id/draft-perret-prat-lamps-
cms-pq-kem-00.txt>.
Ounsworth & Gray Expires 12 January 2023 [Page 19]
Internet-Draft PQ Composite Keys July 2022
[RFC1421] Linn, J., "Privacy Enhancement for Internet Electronic
Mail: Part I: Message Encryption and Authentication
Procedures", RFC 1421, DOI 10.17487/RFC1421, February
1993, <https://www.rfc-editor.org/info/rfc1421>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC2986] Nystrom, M. and B. Kaliski, "PKCS #10: Certification
Request Syntax Specification Version 1.7", RFC 2986,
DOI 10.17487/RFC2986, November 2000,
<https://www.rfc-editor.org/info/rfc2986>.
[RFC4210] Adams, C., Farrell, S., Kause, T., and T. Mononen,
"Internet X.509 Public Key Infrastructure Certificate
Management Protocol (CMP)", RFC 4210,
DOI 10.17487/RFC4210, September 2005,
<https://www.rfc-editor.org/info/rfc4210>.
[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,
<https://www.rfc-editor.org/info/rfc5280>.
[RFC5652] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70,
RFC 5652, DOI 10.17487/RFC5652, September 2009,
<https://www.rfc-editor.org/info/rfc5652>.
[RFC5912] Hoffman, P. and J. Schaad, "New ASN.1 Modules for the
Public Key Infrastructure Using X.509 (PKIX)", RFC 5912,
DOI 10.17487/RFC5912, June 2010,
<https://www.rfc-editor.org/info/rfc5912>.
[RFC5914] Housley, R., Ashmore, S., and C. Wallace, "Trust Anchor
Format", RFC 5914, DOI 10.17487/RFC5914, June 2010,
<https://www.rfc-editor.org/info/rfc5914>.
[RFC5958] Turner, S., "Asymmetric Key Packages", RFC 5958,
DOI 10.17487/RFC5958, August 2010,
<https://www.rfc-editor.org/info/rfc5958>.
[RFC7468] Josefsson, S. and S. Leonard, "Textual Encodings of PKIX,
PKCS, and CMS Structures", RFC 7468, DOI 10.17487/RFC7468,
April 2015, <https://www.rfc-editor.org/info/rfc7468>.
Ounsworth & Gray Expires 12 January 2023 [Page 20]
Internet-Draft PQ Composite Keys July 2022
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[RFC8411] Schaad, J. and R. Andrews, "IANA Registration for the
Cryptographic Algorithm Object Identifier Range",
RFC 8411, DOI 10.17487/RFC8411, August 2018,
<https://www.rfc-editor.org/info/rfc8411>.
[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.
10.2. Informative References
[Aviram2021]
"Concatenating Secrets May Be Dangerous", 2022,
<https://github.com/nimia/kdf_public>.
[Aviram2022]
"Practical (Post-Quantum) Key Combiners from One-Wayness
and Applications to TLS.", n.d.,
<https://eprint.iacr.org/2022/065>.
[Bindel2017]
Bindel, N., Herath, U., McKague, M., and D. Stebila,
"Transitioning to a quantum-resistant public key
infrastructure", 2017, <https://link.springer.com/
chapter/10.1007/978-3-319-59879-6_22>.
[I-D.becker-guthrie-noncomposite-hybrid-auth]
Becker, A., Guthrie, R., and M. J. Jenkins, "Non-Composite
Hybrid Authentication in PKIX and Applications to Internet
Protocols", Work in Progress, Internet-Draft, draft-
becker-guthrie-noncomposite-hybrid-auth-00, 22 March 2022,
<https://www.ietf.org/archive/id/draft-becker-guthrie-
noncomposite-hybrid-auth-00.txt>.
[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,
<https://www.ietf.org/archive/id/draft-ietf-tls-hybrid-
design-04.txt>.
Ounsworth & Gray Expires 12 January 2023 [Page 21]
Internet-Draft PQ Composite Keys July 2022
[I-D.ounsworth-pq-composite-sigs]
Ounsworth, M. and M. Pala, "Composite Signatures For Use
In Internet PKI", Work in Progress, Internet-Draft, draft-
ounsworth-pq-composite-sigs-07, 8 June 2022,
<https://www.ietf.org/archive/id/draft-ounsworth-pq-
composite-sigs-07.txt>.
[RFC3279] Bassham, L., Polk, W., and R. Housley, "Algorithms and
Identifiers for the Internet X.509 Public Key
Infrastructure Certificate and Certificate Revocation List
(CRL) Profile", RFC 3279, DOI 10.17487/RFC3279, April
2002, <https://www.rfc-editor.org/info/rfc3279>.
[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,
<https://www.rfc-editor.org/info/rfc5990>.
Appendix A. Examples
TBD
Appendix B. ASN.1 Module
TBD -- UPDATE
<CODE STARTS>
Composite-Keys-2022
{ TBD }
DEFINITIONS IMPLICIT TAGS ::= BEGIN
EXPORTS ALL;
IMPORTS
-- any?
--
-- Object Identifiers
--
-- To be replaced by IANA
id-alg-composite-kem OBJECT IDENTIFIER ::= {
joint-iso-itu-t(2) country(16) us(840) organization(1)
entrust(114027) Algorithm(80) Composite(4) KEM (5) }
Ounsworth & Gray Expires 12 January 2023 [Page 22]
Internet-Draft PQ Composite Keys July 2022
id-composite-kdf-combiner OBJECT IDENTIFIER ::= { TBD }
--
-- Composite structures
--
CompositeCiphertextValue ::= SEQUENCE SIZE (2..MAX) OF BIT STRING
kema-CompositeKEM KEM-ALGORITHM ::= {
IDENTIFIER id-alg-composite-kem
VALUE CompositeCiphertextValue
PARAMS composite-kem-params
PUBLIC-KEYS { pk-Composite }
SMIME-CAPS { IDENTIFIED BY id-alg-composite } }
}
TODO: this assumes that KEM-ALGORITHM is defined, which it currently is not.
composite-kem-params ::= SEQUENCE {
combiner AlgorithmIdentifier
}
alg-composite-kdf-combiner-params ::= SEQUENCE {
kdf AlgorithmIdentifier
}
END
<CODE ENDS>
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:
Ounsworth & Gray Expires 12 January 2023 [Page 23]
Internet-Draft PQ Composite Keys July 2022
Serge Mister (Entrust), Ali Noman (Entrust), Scott Fluhrer (Cisco),
Jan Klaussner (D-Trust), Max Pala (CableLabs), and Douglas Stebila
(University of Waterloo).
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
Email: john.gray@entrust.com
Ounsworth & Gray Expires 12 January 2023 [Page 24]