Internet DRAFT - draft-pala-klaussner-composite-kofn
draft-pala-klaussner-composite-kofn
LAMPS M. Pala
Internet-Draft CableLabs
Intended status: Standards Track J. Klaussner
Expires: 6 June 2024 D-Trust GmbH
M. Ounsworth
J. Gray
Entrust
4 December 2023
k-of-n Composite Signatures for Multi-Algorithm PKI
draft-pala-klaussner-composite-kofn-01
Abstract
With the need to evolve the cryptography used in today applications,
devices, and networks, there are many scenarios where the use of a
single-algorithm is not sufficient. For example, there might be the
need for migrating between two existing algorithms because of a
weakening of earlier generations (e.g., from classic or traditional
to post-quantum or quantum-safe). Another example might involve the
need to test, instead, the capabilities of devices via test drivers
and/or non-standard algorithms. Another very common case is the need
to combine certified cryptography (e.g., FIPS) with newer algorithms
that are not yet certified or that are not planned for certification.
This work extends the options provided by Explicit Composite, defined
in [I-D.ounsworth-pq-composite-sigs], by providing a mechanism to
manage backward and forward compatibility via k-of-n signature
validation procedures.
This document provides the definition of a new type of the kofn-
CompositePublicKey and kofn-CompositeSignature which are aligned with
the definitions of the respective structures for Explicit Composite
[I-D.ounsworth-pq-composite-sigs].
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/.
Pala, et al. Expires 6 June 2024 [Page 1]
Internet-Draft k-of-n Composite Signatures December 2023
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 6 June 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. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1. Alternative Algorithms Support (k-of-n) . . . . . . . . . 5
2.2. Differences between K-of-N Composite and Explicit
Composite . . . . . . . . . . . . . . . . . . . . . . . . 5
3. K-of-N Composite Keys . . . . . . . . . . . . . . . . . . . . 6
3.1. Private Keys . . . . . . . . . . . . . . . . . . . . . . 6
3.2. Public Keys . . . . . . . . . . . . . . . . . . . . . . . 8
3.3. Key Generation . . . . . . . . . . . . . . . . . . . . . 8
4. K-of-N Composite Signatures . . . . . . . . . . . . . . . . . 8
5. Signature Data Structures . . . . . . . . . . . . . . . . . . 9
5.1. Cryptographic Primitives . . . . . . . . . . . . . . . . 9
5.2. The kofn-Sign() primitive . . . . . . . . . . . . . . . . 10
5.3. The kofn-Verify() primitive . . . . . . . . . . . . . . . 12
6. Algorithm Management . . . . . . . . . . . . . . . . . . . . 15
6.1. Validation Policy and Revocation Information . . . . . . 15
6.2. The DeprecatedKeyTypes extension . . . . . . . . . . . . 16
6.3. The RequiredKeyTypes extension . . . . . . . . . . . . . 17
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17
8. Security Considerations . . . . . . . . . . . . . . . . . . . 17
9. Contributors and Acknowledgements . . . . . . . . . . . . . . 18
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 18
10.1. Normative References . . . . . . . . . . . . . . . . . . 18
10.2. Informative References . . . . . . . . . . . . . . . . . 19
Appendix A. ASN.1 Module . . . . . . . . . . . . . . . . . . . . 20
Pala, et al. Expires 6 June 2024 [Page 2]
Internet-Draft k-of-n Composite Signatures December 2023
Appendix B. Intellectual Property Considerations . . . . . . . . 23
B.1. Making contributions . . . . . . . . . . . . . . . . . . 23
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23
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
BCP14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here. These words may also appear in this
document in lower case as plain English words, absent their normative
meanings.
This document is consistent with the terminology defined in
[I-D.driscoll-pqt-hybrid-terminology]. In addition, the following
terminology is used throughout this document:
ALGORITHM: A standardized cryptographic primitive, as well as any
ASN.1 structures needed for encoding data and metadata needed to use
the algorithm. This document is primarily concerned with algorithms
for producing digital signatures.
BER: Basic Encoding Rules (BER) as defined in [X.690].
COMPONENT ALGORITHM: A single basic algorithm which is contained
within a composite algorithm.
COMPONENT KEY: One component of the Composite Key. For example, an
RSA, a ML-DSA or a FN-DSA key.
COMPOSITE ALGORITHM: An algorithm which is a sequence of two or more
component algorithms, as defined in Section 3.
CLIENT: Any software that is making use of a cryptographic key. This
includes a signer, verifier, encrypter, decrypter.
DER: Distinguished Encoding Rules as defined in [X.690].
PKI: Public Key Infrastructure, as defined in [RFC5280].
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.
Pala, et al. Expires 6 June 2024 [Page 3]
Internet-Draft k-of-n Composite Signatures December 2023
K-of-N: A k-of-n signature is a signature that is valid if and only
if at least k of the n component signatures are supported.
N: The number of component signatures in a K-of-N signature. The
maximum value of N is kofn-CompositeComponentsMax (16).
K: The number of component signatures that must be supported (and
correctly validated) in order for the k-of-n signature to be valid.
The maximum value of K is kofn-CompositeThresholdMax (15).
SIGNATURE: A digital cryptographic signature, making no assumptions
about which algorithm.
STRIPPING ATTACK: An attack in which the attacker is able to
downgrade the cryptographic object to an attacker-chosen subset of
original set of component algorithms in such a way that it is not
detectable by the receiver. For example, substituting a composite
public key or signature for a version with fewer components.
2. Introduction
When the trust in the cryptographic algorithms is not static (e.g.,
not enough crypto-analysis has happened yet or a new threat is
envisioned to be deployable in the next future), there might be the
need to combine multiple algorithms together to provide different
security properties.
Similar considerations apply to the deployment of certified
algorithms together with experimental or non-standard ones.
Even after a migration period, it may be advantageous for an entity
cryptographic identity to be composed of multiple public-key
algorithms where different security and non-security properties might
be provided through the use of hybrid solutions (multi-algorithms).
In other words, this work provides a flexible mechanism for crypto-
agility and migration paths deployments especially suited for
critical infrastructures, device networks, and environments where the
use of multiple algorithms is required but no change in the protocol
is desired.
For further considerations on the challenges related to crypto-
agility, please refer to [I-D.ounsworth-pq-composite-keys].
Pala, et al. Expires 6 June 2024 [Page 4]
Internet-Draft k-of-n Composite Signatures December 2023
2.1. Alternative Algorithms Support (k-of-n)
Although Composite cryptography and Hybrid solutions can be used in
many common use-cases to protect against algorithmic failures over
time, there are other use-cases that mandate for supporting crypto-
interoperability to continue to be able to operate old devices (e.g.,
not upgradable) when deploying newer devices and crypto algorithms.
This is particularly true in environments where deployed devices
might be distributed in the field such as infrastructure's network
elements (e.g., network routers, amplifiers, monitoring devices,
cable modems, public access points, etc.) and access to resources
outside the managed network is highly restricted (i.e., control
interface traffic, not user-generated traffic). The use of multi-
algorithms provides a mechanism for enabling forward and/or backward
compatibility across devices with mixed upgrade capabilities.
This work introduces the concept of K-of-N threshold signatures which
joins the family of hybrid options such as the Explicit Composite
signatures and KEMs.
2.2. Differences between K-of-N Composite and Explicit Composite
K-of-N Composite keys and signatures work very similarly to Explicit
Composite signatures.
When generating a K-of-N Composite key, the process used is the same
as the one used for the Explicit Composite case with the addition of
required parameters that provide the details for the algorithms and
the individual component's details.
When generating a signature, the process used for K-of-N Composite
signatures is exactly the same as the one used in the Explicit
Composite case.
When validating a signature, the K-of-N Composite signatures'
validation process MAY differ from the Explicit Composite case when
parameters are present in the K-of-N Composite public key. In fact,
as discussed in more details in a later Section, K-of-N Composite
keys use parameters to specify the number of component algorithms
that are required to be known by the crypto layer (and must validate
correctly) and/or which components are considered required and which
ones can be skipped.
Pala, et al. Expires 6 June 2024 [Page 5]
Internet-Draft k-of-n Composite Signatures December 2023
In other words, the K-of-N approach differs from the Explicit
Composite crypto in that it allows relying parties to perform the
validation of a subset of signatures if and only if the K-of-N
parameter is present in the PublicKey (i.e., with the K value) and up
to X algorithms are unknown to the device. It is obvious that X must
be less then or equal to K - N .
One of the important aspect that is worth mentioning is that the
K-of-N approach only allows to skip validations of signatures if the
specific component algorithm is not supported and it does NOT allow
to skip the validation of a known algorithm if the signature is not
correctly verified.
In this work, we define N the number of component key in the K-of-N
Composite key, and K the minimum number of component algorithms that
must be supported by the cypto layer (and successfully verified) for
the K-of-N Composite signature to be considered valid. The maximum
allowed value for N is MaxComponents (16) and the maximum allowed
value for K is MaxThreshold (15). When K is used, it MUST be less
than N to allow for N - K algorithms to be skipped (if unknown).
3. K-of-N Composite Keys
K-of-N Composite Crypto algorithm is identified by the id-kofn-
CompositeCrypto OID defined as follows:
id-kofn-CompositeCrypto OBJECT IDENTIFIER ::= {
iso(1) identified-organization(3) dod(6)
internet(1) private(4) enterprise(1) OpenCA(18227)
Algorithms(2) PublicKey(1) Experimental(999)
kofn-CompositeCrypto(2) }
3.1. Private Keys
This section provides an encoding for K-of-N Composite private keys
intended for PKIX protocols and other applications that require an
interoperable format for transmitting private keys, such as PKCS #8
[RFC5958], PKCS #12 [RFC7292], CMP [RFC4210], or CRMF [RFC4211].
Although it is possible to use different types of storage for the
individual components of a K-of-N Composite key (e.g., certified key
modules and non-certified key modules), this document does not cover
this use-case.
The K-of-N Composite private key data use the same structure as in
CompositePrivateKey where each component key is a OneAsymmetricKey
[RFC5958] object:
Pala, et al. Expires 6 June 2024 [Page 6]
Internet-Draft k-of-n Composite Signatures December 2023
MaxComponents INTEGER ::= 16
-- Maximum number of allowed components in a Key
MaxThreshold INTEGER ::= 15
-- Maximum value for required algoritmic threshold
CompositeThreshold ::= INTEGER (1..MaxThreshold)
-- Allowed value ranges for the K-of-N threshold (K)
kofn-CompositePrivateKey ::= SEQUENCE SIZE (2..MaxComponents)
OF OneAsymmetricKey
The parameters field is of type kofn-CompositeParams and is defined
as follows:
kofn-CompositeParams ::= SEQUECE {
hashAlgorithm AlgorithmIdentifier,
-- Identifier for the hash algorithm used to pre-hash the message
threshold CompositeThreshold OPTIONAL,
-- Number of required supported algorithms (must be less than N)
}
The use of any Composite or hybrid algorithm (e.g., the pk-kofn-
CompositePublicKey or any of the Explicit Composite algorithms
defined in [I-D.ounsworth-pq-composite-sigs]) is NOT allowed as a
component of a kofn-CompositePrivateKey.
The order of the component keys MUST be the same as the order defined
for the corresponding public key components.
When a kofn-CompositePrivateKey is conveyed inside a OneAsymmetricKey
structure (version 1 of which is also known as PrivateKeyInfo)
[RFC5958], the privateKeyAlgorithm field SHALL be set to id-kofn-
CompositeCrypto value, the privateKey field SHALL contain the kofn-
CompositePrivateKey data. Associated public key material MAY be
present in the the publicKey field.
In some usecases the private keys that comprise a composite key may
not be represented in a single structure or even be contained in a
single cryptographic module; for example if one component is within
the FIPS boundary of a cryptographic module and the other is not; see
{sec-fips} for more discussion. The establishment of correspondence
between public keys in a kofn-CompositePublicKey and kofn-
CompositePrivateKey not represented in a single composite structure
is beyond the scope of this document.
Pala, et al. Expires 6 June 2024 [Page 7]
Internet-Draft k-of-n Composite Signatures December 2023
3.2. Public Keys
K-of-N Composite Public Keys are identified by the id-kofn-
CompositeCrypto OID and the associated definition of K-of-N Composite
public key (pk-kofn-CompositePublicKey) is provided as follows:
kofn-CompositePublicKeyParams ::= SEQUENCE {
params kofn-CompositeParams,
componentsParams SEQUENCE SIZE (1..MaxComponents)
OF AlgorithmIdentifier,
}
pk-kofn-CompositePublicKey PUBLIC-KEY ::= {
id id-kofn-CompositeCrypto
KeyValue pk-kofn-CompositePublicKey
Params TYPE kofn-CompositePublicKeyParams ARE required
PrivateKey kofn-CompositePrivateKey
}
The use of any Composite algorithms (e.g., the pk-kofn-
CompositePublicKey or any of the Explicit Composite algorithms
defined in [I-D.ounsworth-pq-composite-sigs]) is NOT allowed as a
component of a pk-kofn-CompositePublicKey.
3.3. Key Generation
The KeyGen() -> (pk, sk) is defined as a probabilistic key generation
algorithm, which generates a public key pk and a secret key sk.
The KeyGen() -> (pk, sk) of a composite algorithm performs the
KeyGen() of the respective component signature algorithms and it
produces a composite public key pk as per Section 3.2 and a composite
secret key sk is per Section 3.1.
4. K-of-N Composite Signatures
A K-of-N Composite signature allows two or more underlying signature
algorithms to be combined into a single cryptographic signature
operation and can be used for applications that require signatures.
In this section, we detail the K-of-N Composite signature definition
and two associated algorithms for signature generation and
validation.
Although K-of-N Composite signatures are defined as a sequence of
component signatures, as detailed in many parts of this document and
in alignment with Explicit Composite processes, the sign and verify
algorithms are to be considered as a single atomic operations.
Pala, et al. Expires 6 June 2024 [Page 8]
Internet-Draft k-of-n Composite Signatures December 2023
5. Signature Data Structures
The kofn-CompositeSignatureParams and sa-kofn-CompositeSignature
structures are defined as follows:
kofn-CompositeSignatureParams ::= SEQUENCE {
componentsParams SEQUENCE SIZE
(1..MaxComponents) OF AlgorithmIdentifier,
hashAlgorithm OBJECT IDENTIFIER OPTIONAL,
}
kofn-CompositeComponentSignatureValue ::= SEQUENCE
SIZE (1..MaxComponents) OF BIT STRING
sa-kofn-CompositeSignature SIGNATURE-ALGORITHM ::= {
IDENTIFIER id-kofn-CompositeCrypto
VALUE kofn-CompositeSignatureValue
PARAMS TYPE kofn-CompositeSignatureParams ARE optional
PUBLIC-KEYS { pk-kofn-CompositePublicKey }
SMIME-CAPS { IDENTIFIED BY id-kofn-CompositeCrypto }
}
When a K-of-N Composite Public Key has no defined hashAlgorithm
parameter, the signer MUST include the hashAlgorithm parameter in the
kofn-CompositeSignatureParams structure to specify which hash
algorithm was used to pre-hash the message before signing as
described in Section 4.
When a K-of-N Composite Public Key has the hashAlgorithm parameter
defined, the signer MUST NOT include the hashAlgorithm parameter in
the kofn-CompositeSignatureParams structure.
In case both the K-of-N Composite Public Key and the kofn-
CompositeSignatureParams structure contain the hashAlgorithm
parameter, the verifier MUST ignore the hashAlgorithm parameter from
the kofn-CompositeSignatureParams structure and use the one from the
K-of-N Composite Public Key.
5.1. Cryptographic Primitives
In this section we define K-of-N Composite Signatures as a
cryptographic primitive that consists of three algorithms. The first
one is the kofn-KeyGen() and is defined in Section 3.
The remaining two algorithms are the Sign() and Verify() algorithms,
which are defined in Section 5.2 and Section 5.3 respectively and can
be summarized as follows:
Pala, et al. Expires 6 June 2024 [Page 9]
Internet-Draft k-of-n Composite Signatures December 2023
* kofn-Sign(sk, Message) -> (signature): A signing algorithm which
takes as input a secret key sk and a Message, and outputs a
signature.
* kofn-Verify(pk, Message, signature) -> true or false: A
verification algorithm which takes as input a public key, a
Message, an optional hashing algorithm, and a signature and
outputs true if the signature and public key can be used to verify
the message. Thus it proves the Message was signed with the
secret key associated with the public key and verifies the
integrity of the Message. If the signature and public key cannot
verify the Message, it returns false.
5.2. The kofn-Sign() primitive
When using K-of-N Composite Private Keys to generate signatures, the
process is the same as in the Explicit Composite case (see section
5.1 of [I-D.ounsworth-pq-composite-sigs]).
Specifically, the generation of a K-of-N Composite signature involves
pre-hashing the message to be signed with key-binding data to provide
non-separability properties for the signature, and then applying each
component algorithm's signature process to the modified input message
according to its specification. Each component signature value is
then placed into the CompositeSignatureValue structure defined in
Section 5.
The following process is used to generate composite signature values.
Pala, et al. Expires 6 June 2024 [Page 10]
Internet-Draft k-of-n Composite Signatures December 2023
kofn-Sign (sk, Message) -> (signature)
Input:
K1..KN Signing private keys for each component. See note below on
composite inputs.
A1..AN Component signature algorithms. See note below on
composite inputs.
Message The Message to be signed, an octet string
HASH The Message Digest Algorithm used for pre-hashing. See section
on pre-hashing below.
OID The Composite Signature String Algorithm Name converted
from ASCII to bytes. See section on OID concatenation
below.
Output:
signature The composite signature, a CompositeSignatureValue
Signature Generation Process:
1. Compute a Hash of the Message
M' = HASH(Message)
2. Generate the n component signatures independently,
according to their algorithm specifications.
S1 := Sign( K1, A1, DER(OID) || DER(kofn-CompositeKeyParams) || M' )
...
SN := Sign( KN, AN, OID || M' )
3. Encode each component signature S1..SN into a sequence of BIT STRING
according to its algorithm specification.
signatureComponent ::= BIT STRING
signature ::= SEQUENCE (1..N) OF signatureComponent
4. Output signature
Figure 1: K-of-N Composite Sign(sk, Message)
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. When passed to the Composite Sign(sk, Message) API
the sk is a kofn-CompositePrivateKey. It is possible to construct a
Pala, et al. Expires 6 June 2024 [Page 11]
Internet-Draft k-of-n Composite Signatures December 2023
kofn-CompositePrivateKey from component keys stored in separate
software or hardware keystores. Variations in the process to
accommodate particular private key storage mechanisms 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, no component
signature may itself be a composite of any kind (K-of-N or Explicit);
this means that the signature generation process MUST fail if one of
the private keys K1..KN is a composite.
A composite signature MUST produce, and include in the output, a
signature value for every component key in the corresponding kofn-
CompositePublicKey, and they MUST be in the same order; ie in the
output, S1 MUST correspond to K1, S2 to K2, ..., and SN to KN.
5.3. The kofn-Verify() primitive
When validating composite signatures generated via id-kofn-
CompositeCrypto algorithm, the validation procedures, when compared
to the Explicit Composite, are modified to allow for a well-defined
number of component signatures validation failures to occur before
failing the validation of the composite signature as a whole.
The possibility to be able to still consider a composite signature
valid in the presence of unsupported algorithms is a useful feature
for guaranteeing the interoperability of newer devices with older
ones that might not be able to correctly process all the algorithms
(but they can still validate a subset of them).
In fact, when validating signatures generated via MultiKey keys, the
total number of successful component signature validations shall be
equal or greater than the public key parameter K (when present).
After that, additional component signatures' validations may be
skipped, if and only if the algorithm is unknown to the crypto layer,
without impacting the validity of the whole composite signature. If
any of the signatures of supported algorithms should fail the
validation, the K-of-N Composite signature validation MUST fail,
independently of the value of K.
When the public key parameter K is absent or its value is set to the
number of components in the signing key (i.e., K = n), the validation
process for MultiKey and Composite are the same as they both require
the successful validation of all the signatures.
Pala, et al. Expires 6 June 2024 [Page 12]
Internet-Draft k-of-n Composite Signatures December 2023
When the public key parameter K is set to one (1), the validation
process for K-of-N Composite signatures provides support for fully
alternative signatures where a single successful component
signature's validation validates the whole composite signature.
When compared to the composite signatures' validation process, we
modify the for..loop cycle where the invalid signature output is not
emitted if the algorithm is unknown, but only if the number of
unsupported algorithms is greated than the value N - K.
The second optimization allowed by MultiKey keys is to be able to
consider a composite signature successful right after at least K
successful component signatures' validations, without the need for
even attempting at performing the remaining ones.
The Input and Output definitions are the same as defined in the
Explicit Composite case:
Input:
P1, P2, .., Pn Public verification keys.
HASH The Message Digest Algorithm used for pre-hashing. See section
on pre-hashing below.
M Message
S1, S2, .., Sn Component signature values.
A1, A2, ... An Component signature algorithms.
Output:
Validity (bool) "Valid signature" (true) if the composite
signature is valid, "Invalid signature"
(false) otherwise.
Figure 2
The following process is used to perform composite signatures
verification with a K-of-N Composite algorithm:
Pala, et al. Expires 6 June 2024 [Page 13]
Internet-Draft k-of-n Composite Signatures December 2023
1. Check keys, signatures, and algorithms for consistency.
If Error during desequencing, or the three sequences
have different numbers of elements, or any of the public
keys P1, P2, .., Pn or algorithm identifiers A1, A2, ..,
An are any type of composite (i.e., k-of-n or explicit)
then output "Invalid signature" and stop.
2. Construct the modified message M' to be used for the validation
process with each component signature.
M' = HASH(Message)
Set the initial counter `X` to zero to indicate the number
of unsupported algorithms encountered during the validation
process.
3. Process each signature component in order, from S1 to Sn
as follows:
3.a Check the support for each component of the signature against
the number of required supported algorithms (`threshold`).
If the public key parameter `threshold` is NOT set and the
component signature algorithm is not supported, the validation
fails, output "Invalid signature" and stop.
If the public key parameter `threshold` is set and the component
signature is not supported, the counter `X` is incremented. If `X`
is greater than `N - K`, the validation fails, output "Invalid
signature" and stop.
If a component signature is not supported and the corresponding
`isRequired` field of the associated `kofn-CompositeComponentKeyParams`
is present and set to `TRUE`, the validation fails, output
"Invalid signature" and stop.
3.b Check each component signature individually, according to
its algorithm specification.
Result := Verify(Kx, Ax, DER(OID) || DER(kofn-CompositeKeyParams) || M')
If any of the component signatures S1, S2, .., Sn is not
correctly validated according to the component's algorithm,
the validation fails, output "Invalid signature" and stop.
4. Output "Valid signature"
Pala, et al. Expires 6 June 2024 [Page 14]
Internet-Draft k-of-n Composite Signatures December 2023
Figure 3
6. Algorithm Management
Traditionally, a public key, certificate, or signature contains a
single cryptographic algorithm. To revoke such a certificate due to
algorithm depecation we still need to use serial-number-based
revocations.
However, in a Composite environment (e.g., supported via Explicit
Composite, K-of-N Composite, or other Hybrid approaches), it might be
possible to deprecate an entire algorithm and still be able to
securely continue performing authentications and validations instead
of revoking (or simply distrust) the entire infrastructure (and
without adding every single certificate that relies on the deprecated
algorithm on the revocation list).
By integrating the concept of deprecated algorithms, in the K-of-N
case it is possible to dynamically switch among which algorithms are
going to be used for signature validations by informing the
validating entity about the OIDs of the individual algorithms that
are considered "failures".
Additionally, by integrating the concept of required algorithms, in
the K-of-N case it is possible to make sure that specific algorithms
are always required to be supported by the validating entity. This
could be the case, for example, when the trust in one of the
algorithm might be higher (e.g., certified and/or longer crypto-
analysis history).
6.1. Validation Policy and Revocation Information
As we just mentioned, in multi-algorithm environments, there are
situations where the validation of a component signature that carries
a deprecated algorithm identifier might still be allowed, e.g. when
at least another K algorithms validate correctly. In a K-of-N
environment, this means that the device does not need to be re-
provisioned (or replaced) and can continue to operate by relying on
the non-deprecated algorithm(s).
On top of that, there are also typical use-cases where the
deprecation of an algorithm is paramount to make sure that
authentications do not rely only on deprecated algorithms. This is
the case, for example, when older devices that can only successfully
validate one algorithm from a composite signature (e.g., it can
validate RSA signatures but no other) are still part of the network.
When the only algorithm that they can use is deprecated, validation
of composite signature MUST fail.
Pala, et al. Expires 6 June 2024 [Page 15]
Internet-Draft k-of-n Composite Signatures December 2023
The list of deprecated algorithms that are to be considered automatic
validation "unknowns" can be directly configured as a parameter in
the validating entity's process, or by accessing a trusted source of
information such as a trusted Certificate Revocation List (CRL) or
Online Certificate Status Protocol (OCSP) response.
Similarly, the list of required algorithms that cannot be skipped,
even if not supported by the device can be directly configured as a
parameter in the validating entity's process, or by accessing a
trusted source of information such as a trusted Certificate
Revocation List (CRL) or Online Certificate Status Protocol (OCSP)
response.
6.2. The DeprecatedKeyTypes extension
In an ecosystem such as the Internet PKI or IoT PKIs, since algorithm
deprecation can be seen as another form of (mass) revocation, a
convenient mechanism to distribute the list of deprecated algorithms
by adding a specific extension to Certificate Revocation Lists
[RFC5280] or Online Certificate Status Protocol [RFC6960] responses.
We define a new DeprecatedKeyTypes extension together with the
associated id-ce-deprecatedKeyTypes identifier. The data structure
of the extension is defined as a SEQUENCE of OBJECT IDENTIFIER. The
corresponding ASN.1 structures are defined as follows:
id-ce-deprecatedKeyTypes OBJECT IDENTIFIER ::= {
iso(1) identified-organization(3) dod(6)
internet(1) private(4) enterprise(1) OpenCA(18227)
Extensions(3) deprecated-algs (2) }
DeprecatedKeyTypes ::= SEQUENCE SIZE (1..MaxThreshold)
OF OBJECT IDENTIFIER
When this extension is present in a CRL or OCSP response, the
validating party MUST consider the algorithms listed in the extension
as "unknown", even in the case where the algorithm is supported by
the device. At a practical level, this means that the validation of
a component signature that carries a deprecated algorithm identifier
MUST fail if the threshold (or K-of-N) validations is not met because
of the deprecation of algorithms.
Pala, et al. Expires 6 June 2024 [Page 16]
Internet-Draft k-of-n Composite Signatures December 2023
For example, let's imagine a K-of-N Composite key that combines
AlgorithmA and AlgorithmB together. Let's also imagine that a device
can only validate AlgorithmA and does not have support for
AlgorithmB. If the K-of-N threshold is set to 1, then the device can
still validate the composite signature since it can still rely on
AlgorithmA. However, if AlgorithmA is deprecated via the
DeprecatedKeyTypes extension, then the validation MUST fail because
the device can no longer rely on AlgorithmA.
6.3. The RequiredKeyTypes extension
When backward or forward compatibility is required, it might be
useful to provide the possibility to pin specific algorithms to be
required to be supported during signature and validations processes.
For example, when a K-of-N is used with N = 3 and K =2, there migth
be requirements to make sure that one of the two required algorithms
to be validated is a specific one (e.g., AlgorithmA).
To handle this situation, we define a new RequiredKeyTypes extension,
together with the associated id-ce-requiredKeyTypes identifier, that
can be added to Certificate Revocation Lists [RFC5280], Online
Certificate Status Protocol [RFC6960] responses.
We define a new RequiredKeyTypes extension together with the
associated id-ce-requiredKeyTypes identifier. The data structure of
the extension is defined as a SEQUENCE of OBJECT IDENTIFIER. The
corresponding ASN.1 structures are defined as follows:
id-ce-requiredKeyTypes OBJECT IDENTIFIER ::= {
iso(1) identified-organization(3) dod(6)
internet(1) private(4) enterprise(1) OpenCA(18227)
Extensions(3) required-algs (3) }
RequiredKeyTypes ::= SEQUENCE SIZE (1..MaxThreshold)
OF OBJECT IDENTIFIER
7. IANA Considerations
No IANA actions are required by this document.
8. Security Considerations
TBD.
Pala, et al. Expires 6 June 2024 [Page 17]
Internet-Draft k-of-n Composite Signatures December 2023
9. 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), Scott Fluhrer (Cisco Systems), Klaus-Dieter
Wirth (D-Trust), and Francois Rousseau.
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].
10. References
10.1. Normative References
[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-05, 29 May 2023,
<https://datatracker.ietf.org/doc/html/draft-ounsworth-pq-
composite-keys-05>.
[I-D.ounsworth-pq-composite-sigs]
Ounsworth, M., Gray, J., Pala, M., and J. Klaußner,
"Composite Signatures For Use In Internet PKI", Work in
Progress, Internet-Draft, draft-ounsworth-pq-composite-
sigs-10, 23 October 2023,
<https://datatracker.ietf.org/doc/html/draft-ounsworth-pq-
composite-sigs-10>.
[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>.
Pala, et al. Expires 6 June 2024 [Page 18]
Internet-Draft k-of-n Composite Signatures December 2023
[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>.
[RFC4211] Schaad, J., "Internet X.509 Public Key Infrastructure
Certificate Request Message Format (CRMF)", RFC 4211,
DOI 10.17487/RFC4211, September 2005,
<https://www.rfc-editor.org/info/rfc4211>.
[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>.
[RFC5958] Turner, S., "Asymmetric Key Packages", RFC 5958,
DOI 10.17487/RFC5958, August 2010,
<https://www.rfc-editor.org/info/rfc5958>.
[RFC6960] Santesson, S., Myers, M., Ankney, R., Malpani, A.,
Galperin, S., and C. Adams, "X.509 Internet Public Key
Infrastructure Online Certificate Status Protocol - OCSP",
RFC 6960, DOI 10.17487/RFC6960, June 2013,
<https://www.rfc-editor.org/info/rfc6960>.
[RFC7292] Moriarty, K., Ed., Nystrom, M., Parkinson, S., Rusch, A.,
and M. Scott, "PKCS #12: Personal Information Exchange
Syntax v1.1", RFC 7292, DOI 10.17487/RFC7292, July 2014,
<https://www.rfc-editor.org/info/rfc7292>.
[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
Pala, et al. Expires 6 June 2024 [Page 19]
Internet-Draft k-of-n Composite Signatures December 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-02, 7 March 2023,
<https://datatracker.ietf.org/doc/html/draft-driscoll-pqt-
hybrid-terminology-02>.
Appendix A. ASN.1 Module
kofn-Composite-Crypto-2023
{ joint-iso-itu-t(2) country(16) us(840) organization(1) OpenCA(18277)
Algorithms(2) PublicKey(1) kofn-CompositeCrypto(2) }
DEFINITIONS IMPLICIT TAGS ::= BEGIN
EXPORTS ALL;
IMPORTS
PUBLIC-KEY, SIGNATURE-ALGORITHM, 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) }
SubjectPublicKeyInfo
FROM PKIX1Explicit-2009
{ iso(1) identified-organization(3) dod(6) internet(1)
security(5) mechanisms(5) pkix(7) id-mod(0)
id-mod-pkix1-explicit-02(51) }
OneAsymmetricKey
FROM AsymmetricKeyPackageModuleV1
{ iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1)
pkcs-9(9) smime(16) modules(0)
id-mod-asymmetricKeyPkgV1(50) }
;
--
-- Object Identifiers
--
-- Defined in ITU-T X.690
der OBJECT IDENTIFIER ::=
{joint-iso-itu-t asn1(1) ber-derived(2) distinguished-encoding(1)}
id-kofn-CompositeCrypto OBJECT IDENTIFIER ::= {
iso(1) identified-organization(3) dod(6)
Pala, et al. Expires 6 June 2024 [Page 20]
Internet-Draft k-of-n Composite Signatures December 2023
internet(1) private(4) enterprise(1) OpenCA(18227)
Algorithms(2) PublicKey(1) Experimental(999)
kofn-CompositeCrypto(2)
}
id-ce-deprecatedKeyTypes OBJECT IDENTIFIER ::= {
iso(1) identified-organization(3) dod(6)
internet(1) private(4) enterprise(1) OpenCA(18227)
Extensions(3) deprecated-algs (2)
}
id-ce-requiredKeyTypes OBJECT IDENTIFIER ::= {
iso(1) identified-organization(3) dod(6)
internet(1) private(4) enterprise(1) OpenCA(18227)
Extensions(3) required-algs (3)
}
--
-- Constants
--
MaxComponents INTEGER ::= 16
-- Maximum number of allowed components in a Key
MaxThreshold INTEGER ::= 15
-- Maximum value for required algoritmic threshold
CompositeThreshold ::= INTEGER (1..MaxThreshold)
-- Allowed value ranges for the K-of-N threshold (K)
--
-- Private Keys
--
kofn-CompositePrivateKey ::= SEQUENCE SIZE (2..MaxComponents)
OF OneAsymmetricKey
kofn-CompositeParams ::= SEQUECE {
hashAlgorithm AlgorithmIdentifier,
-- Identifier for the hash algorithm used to pre-hash the message
threshold CompositeThreshold OPTIONAL,
-- Number of required supported algorithms (must be less than N)
}
--
-- Public Keys
--
Pala, et al. Expires 6 June 2024 [Page 21]
Internet-Draft k-of-n Composite Signatures December 2023
kofn-CompositePublicKeyParams ::= SEQUENCE {
params kofn-CompositeParams,
componentsParams SEQUENCE SIZE (1..MaxComponents)
OF AlgorithmIdentifier,
}
pk-kofn-CompositePublicKey PUBLIC-KEY ::= {
id id-kofn-CompositeCrypto
KeyValue pk-kofn-CompositePublicKey
Params TYPE kofn-CompositePublicKeyParams ARE required
PrivateKey kofn-CompositePrivateKey
}
--
-- Signature Algorithm
--
kofn-CompositeSignatureParams ::= SEQUENCE {
componentsParams SEQUENCE SIZE
(1..MaxComponents) OF AlgorithmIdentifier,
hashAlgorithm OBJECT IDENTIFIER OPTIONAL,
}
kofn-CompositeComponentSignatureValue ::= SEQUENCE
SIZE (1..MaxComponents) OF BIT STRING
sa-kofn-CompositeSignature SIGNATURE-ALGORITHM ::= {
IDENTIFIER id-kofn-CompositeCrypto
VALUE kofn-CompositeSignatureValue
PARAMS TYPE kofn-CompositeSignatureParams ARE optional
PUBLIC-KEYS { pk-kofn-CompositePublicKey }
SMIME-CAPS { IDENTIFIED BY id-kofn-CompositeCrypto }
}
--
-- Extensions
--
DeprecatedKeyTypes ::= SEQUENCE SIZE (1..MaxThreshold)
OF OBJECT IDENTIFIER
RequiredKeyTypes ::= SEQUENCE SIZE (1..MaxThreshold)
OF OBJECT IDENTIFIER
END
Pala, et al. Expires 6 June 2024 [Page 22]
Internet-Draft k-of-n Composite Signatures December 2023
Appendix B. Intellectual Property Considerations
The following IPR Disclosure relates to this draft:
* https://datatracker.ietf.org/ipr/3588/
(https://datatracker.ietf.org/ipr/3588/)
B.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-klaussner-pala-composite-
kofn (https://github.com/EntrustCorporation/draft-klaussner-pala-
composite-kofn)
Authors' Addresses
Massimiliano Pala
CableLabs Inc.
858 Coal Creek Cir
Louisville, Colorado, 80027
United States of America
Email: director@openca.org
Jan Klaussner
D-Trust GmbH
Kommandantenstr. 15
10969 Berlin
Germany
Email: jan.klaussner@d-trust.net
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
Pala, et al. Expires 6 June 2024 [Page 23]
