| Internet-Draft | K-threshold Sigs | November 2022 |
| Pala & Klaussner | Expires 19 May 2023 | [Page] |
With the need to evolve the cryptography used in today applications, devices, and networks, there might be many scenarios where the use of a single-key certificate is not sufficient. For example, there might be the need for migrating between two existing algorithms (e.g., from classic to post-quantum) or there might be the need to test the capabilities of devices via test drivers and/or non-standard algorithms.¶
Differently from the situation where algorithms are not yet (or no more) trusted to be used by themselves, this document addresses the use of multiple keys and signatures that can be individually trusted to implement a generic 1-threshold and K-threshold signature validation procedures.¶
This document provides the definition of a new type of multi-algorithm public key and relies on the definition of CompositePrivateKey, and CompositeSignature which are sequences of the respective structure for each component algorithm as defined in [I-D.ounsworth-pq-composite-sigs] and [I-D.ounsworth-pq-composite-sigs].¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 19 May 2023.¶
Copyright (c) 2022 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶
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:¶
Any software that is making use of a cryptographic key. This includes a signer, verifier, encrypter, decrypter.¶
The public and private portion of an asymmetric cryptographic key, making no assumptions about which algorithm.¶
One component of the Composite Key. For example, an RSA, a Dilithium3 or a Falcon512 key.¶
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 address the crypto-uncertainty of the envisioned period.¶
An example of such a situation can be found in the planning for the transition to post-quantum cryptography (PQ or PQC). While classic algorithms will still be trusted for some time (but we do not know how much), there is uncertainty as to the strength of the new cryptographic algorithms. Unlike previous cryptographic algorithm migrations, the choice of when to migrate and which algorithms to migrate to, is not so clear.¶
Even after the migration period, it may be advantageous for an entity cryptographic identity to be composed of multiple public-key algorithms by using a Post-Quantum/Traditional (PQ/T) or Post-Quantum/Post-Quantum (PQ/PQ) Hybrid scheme.¶
For further considerations on the challenges related to crypto-agility, please refer to [I-D.ounsworth-pq-composite-keys].¶
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.). The use of multi-algorithms provides a mechanism for enabling forward compatibility with newer devices even when they cannot be upgraded.¶
At a practical level this means that we need a mechanism to still be able to validate Composite signatures even when not all algorithms are supported by all devices.¶
This work introduces the concept of alternative signatures which joins the family of hybrid options such as Composite Crypto.¶
The MultiKey approach focus is to provide the possibility to validate Composite signatures even when not all algorithms that were used in the generation of the Composite signature are supported. From this point of view, the MultiKey approach differs from the Composite crypto one in that it allows relying parties to perform the validation of a subset of signatures instead of requiring the successful validation of all signatures.¶
We define n the number of component key in the MultiKey key, and k the minimum
number of component signature successful validations required for the Composite
signature to be considered valid.¶
The MultiKey approach defined in this document leverages the same procedures
and data structures defined for pk-Composite [I-D.ounsworth-pq-composite-keys] with the
addition of an optional public key parameter. This optional parameter carries
the K value that represents the total number of skipped or erroneous signature
validations.¶
In practice, the MultiKey approach can support different validation policies based on the value of the optional key parameter. For example, by setting the value to one (1) it is possible to require that at least one (1) component signature is correctly validated, thus providing support for true alternative signatures. When using values greater than one (1), MultiKey keys can support K of N models where at least K successful validations MUST take place before the Composite signature is considered valid.¶
In the rest of the section we focus on the description of private and public key structures, while in the next section we focus on the changes in the validation process when compared to signatures generated via Composite Keys.¶
This section provides an encoding for MultiKey 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].¶
The format for the individual component key in a MultiKey key is defined by the algorithm OID that identifies the component key. The format of the MultiKey described in this section is meant to provide an interoperable format that can be adopted and implemented across implementations.¶
This document does not cover the use-case where individual components may be stored in multiple cryptographic modules.¶
The MultiKey private key data use the same structure as in CompositePrivateKey where each component key is a OneAsymmetricKey [RFC5958] object:¶
MultiKeyPrivateKey ::= CompositePrivateKey¶
A MultiKeyPrivateKey MUST contain at least two component private keys, and they MUST be in the same order as in the corresponding MultiKeyPublicKey.¶
MultiKey Public Keys are identified by a unique OID and the associated definition of the related data structure for a multi-algorithm public key, namely a MultiKey key.¶
The OID that identifies a generic MultiKey key is defined as follows:¶
id-multikey-key OBJECT IDENTIFIER ::= {
iso(1) identified-organization(3) dod(6)
internet(1) private(4) enterprise(1) OpenCA(18227)
Algorithms(2) PublicKey(1) Experimental(999)
MultiKey(2) }
¶
The associated definition of MultiKey's public key (pk-MultiKey) and MultiKey's public key parameters (MultiKey-params) structures are as follows:¶
MultiKey-params ::= INTEGER (1..MAX)
pk-MultiKey PUBLIC-KEY ::= {
id id-multikey-key
KeyValue MultiKeyPublicKey
Params TYPE MultiKey-params ARE optional
PrivateKey MultiKeyPrivateKey
}
¶
Where the MultiKey-params is used to specify the number of minimum successful validations required for the signature to be considered valid.¶
The value of the MultiKey-params must be greater or equal to one (1) and shall not exceed the number of component keys present in the MultiKey public key.¶
The use of MultiKey algorithm in a component key is not allowed in a MultiKey key.¶
The sa-CompositeSignature structure is extended as follows:¶
sa-CompositeSignatureEx SIGNATURE-ALGORITHM ::= {
IDENTIFIER id-alg-composite
VALUE CompositeSignatureValue
PARAMS ANY DEFINED BY ALGORITHM
PUBLIC-KEYS { pk-Composite | pk-MultiKey }
SMIME-CAPS { IDENTIFIED BY id-alg-composite } }
¶
The difference with the original sa-CompositeSignature definition is the introduction
of the pk-MultiKey in the PUBLIC-KEYS definition.¶
This section specifies the processes for generating and verifying composite signatures generated via MultiKey keys.¶
When using MultiKey to generate signatures, the process is the same as in the Composite case. Please refer to section 5.1 of [I-D.ounsworth-pq-composite-sigs].¶
When validating composite signatures generated via MultiKey keys, the validation procedures 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 protocols 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 (or fail)
without impacting the validity of the whole composite signature.¶
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.¶
When the public key parameter K is set to one (1), the validation
process for MultiKey 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 after the first validation failure, but only if the number of remaining successful validations is larger than the number of remaining validations.¶
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 composite:¶
Input:
P1, P2, .., Pn Public verification keys.
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 MultiKey key:¶
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 multikey with the OID id-alg-composite or an
explicit composite OID then output "Invalid signature"
and stop.
2. Check each component signature individually, according to
its algorithm specification. Parameter K holds the number of successful
validations yet required and is reduced as soon as a component signature is verified.
If K reaches 0, the entire signature validation
succeeds. If all component signatures are processed and K is not 0, The Validation as whole fails.
IF MultiKey-params
K := MultiKey-params
ELSE
K := n
FOR i := 1 TO n:
IF verify( Pi, M, Si, Ai ):
K--
IF (K == 0):
Output "Valid signature"
IF (n - i < K):
Output "Invalid Signature"
¶
In this work, we define a set of OIDs that allow for assigning explicit algorithm combination to specific MultiKey keys configuration.¶
Please refer to Appendix Section 5 for more details about explicit MultiKey identifiers.¶
This document does not define a separate sets of algorithms and leverages the extends the definitions of composite signatures defined in [I-D.ounsworth-pq-composite-sigs] with the addition of the pk-multikey-key in the PUBLIC-KEYS set.¶
Section Section 3.3 provides the definition for the generic MultiKey key identifier. The generic construct for a MultiKey key allows for both standard and non-standard (i.e., private, test, etc.) public key algorithms to be used to produce composite signatures.¶
Similarly to the composite case, the use of explicit combinations of algorithms can simplify the management of identities by allowing for inspecting a single OID (the outmost one) instead of requiring the inspection of the individual components of the MultiKey key.¶
Traditionally, a public key, certificate, or signature contains a single cryptographic algorithm and to revoke a certificate due to algorithm depecation we still need to use serial-number-based revocations.¶
However, in a multi-algorithms environment (e.g., supported via Composite, MultiKey, 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 MultiKey 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".¶
In fact, the validating entity can automatically "fail" the validation of component signatures that match any value present in the list of revoked algorithms, exactly in the same fashion as when the algorithm is not supported in the first place.¶
As we just mentioned, in MultiKey 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 validate correctly.¶
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.¶
Differently from the pure composite case, if the device can still
successfully validate K component signatures, the device does not need
to be re-provisioned (or replaced) and can continue to operate by
relying on the non-deprecated algorithm.¶
The list of deprecated algorithms that are to be considered automatic validation "failures" can be directly configured as a parameter in the validating entity's process, or by accessing a trusted source of information.¶
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 deprecated-algorithms extension together with the
associated id-ext-deprecated-algorithms identifier. The data structure
of the extension is defined as a SEQUENCE of DeprecatedAlgorithm.
Each DeprecatedAlgorithm is defined as an OBJECT IDENTIFIER.¶
We define the following identifier:¶
id-ce-deprecatedAlgsList OBJECT IDENTIFIER ::= {
iso(1) identified-organization(3) dod(6)
internet(1) private(4) enterprise(1) OpenCA(18227)
Extensions(3) deprecated-algs (2) }
¶
This document registers the following in the SMI "Security for PKIX Algorithms (1.3.6.1.5.5.7.6)" registry:¶
id-composite-key OBJECT IDENTIFIER ::= {
iso(1) identified-organization(3) dod(6) internet(1) security(5)
mechanisms(5) pkix(7) algorithms(6) id-multikey-key(??) }
¶
This document registers the following in the SMI " " registry:¶
id-ce-deprecatedAlgsList OBJECT IDENTIFIER ::= { id-ce deprecatedAlgsList(??) }
¶
This variant provides a rigid way of specifying supported combinations of algorithms.¶
Although this variant limits the possibility for combining non-standard algorithms (or algorithms not considered by the authors of this document), the use of identifiers that identify pairs of standard algorithms might be easier in certain situations such as referencing and/or enforcing specific combinations of algorithms without the need for developing additional validation procedures external to the signature validation one.¶
Explicit algorithms must define a new signature algorithm which consists of:¶
The definition of the explicit algorithm identifiers follows the same definitions provided in Section 4.2 of [I-D.ounsworth-pq-composite-keys] with the exception of the parameters that are not ABSENT but OPTIONAL and their TYPE is MultiKey-params as defined in Section 3.3.¶
<CODE STARTS>
MultiKey-2022
DEFINITIONS IMPLICIT TAGS ::= BEGIN
EXPORTS ALL;
IMPORTS
PUBLIC-KEY, SIGNATURE-ALGORITHM, ParamOptions, 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) } ;
COMPOSITE-KEY-ALGORITHM, pk-Composite, CompositePublicKey,
CompositePrivateKey, pk-explicitComposite, id-composite-key
FROM Composite-Keys-2022 -- {{I-D.draft-ounsworth-pq-sigs}}
{ ... }
--
-- Object Identifiers
--
--
-- Public Key
--
END
<CODE ENDS>
¶
The following IPR Disclosure relates to this draft:¶
https://datatracker.ietf.org/ipr/3588/¶
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:¶
John Gray (Entrust), Serge Mister (Entrust), Scott Fluhrer (Cisco Systems), Panos Kampanakis (Cisco Systems), Daniel Van Geest (ISARA), Tim Hollebeek (Digicert), 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].¶
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-ounsworth-pq-composite-keys¶