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]