k-of-n Composite Signatures for Multi-Algorithm PKI

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

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

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

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

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

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

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

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

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.

The following process is used to perform composite signatures verification with a K-of-N Composite algorithm:¶

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"

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

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

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

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¶