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, . [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, . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . 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, . [RFC4211] Schaad, J., "Internet X.509 Public Key Infrastructure Certificate Request Message Format (CRMF)", RFC 4211, DOI 10.17487/RFC4211, September 2005, . [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, . [RFC5958] Turner, S., "Asymmetric Key Packages", RFC 5958, DOI 10.17487/RFC5958, August 2010, . [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, . [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, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . [RFC8411] Schaad, J. and R. Andrews, "IANA Registration for the Cryptographic Algorithm Object Identifier Range", RFC 8411, DOI 10.17487/RFC8411, August 2018, . [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, . 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]