idnits 2.17.1 draft-ounsworth-pq-composite-sigs-07.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There is 1 instance of too long lines in the document, the longest one being 1 character in excess of 72. ** The abstract seems to contain references ([I-D.draft-ounsworth-pq-composite-keys-01]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (8 June 2022) is 681 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'RFC8446' is mentioned on line 645, but not defined == Missing Reference: 'RFC7296' is mentioned on line 646, but not defined == Missing Reference: 'RFC8551' is mentioned on line 647, but not defined == Missing Reference: 'X509ASN1' is mentioned on line 932, but not defined == Unused Reference: 'Bindel2017' is defined on line 856, but no explicit reference was found in the text == Unused Reference: 'I-D.becker-guthrie-noncomposite-hybrid-auth' is defined on line 862, but no explicit reference was found in the text == Unused Reference: 'I-D.ounsworth-pq-composite-keys' is defined on line 870, but no explicit reference was found in the text == Unused Reference: 'RFC3279' is defined on line 877, but no explicit reference was found in the text ** Downref: Normative reference to an Informational RFC: RFC 2986 ** Downref: Normative reference to an Informational RFC: RFC 8411 == Outdated reference: A later version (-05) exists of draft-ounsworth-pq-composite-keys-00 Summary: 4 errors (**), 0 flaws (~~), 10 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 LAMPS M. Ounsworth 3 Internet-Draft Entrust 4 Intended status: Standards Track M. Pala 5 Expires: 10 December 2022 CableLabs 6 8 June 2022 8 Composite Signatures For Use In Internet PKI 9 draft-ounsworth-pq-composite-sigs-07 11 Abstract 13 The migration to post-quantum cryptography is unique in the history 14 of modern digital cryptography in that neither the old outgoing nor 15 the new incoming algorithms are fully trusted to protect data for the 16 required data lifetimes. The outgoing algorithms, such as RSA and 17 elliptic curve, may fall to quantum cryptanalysis, while the incoming 18 post-quantum algorithms face uncertainty about both the underlying 19 mathematics as well as hardware and software implementations that 20 have not had sufficient maturing time to rule out classical 21 cryptanalytic attacks and implementation bugs. 23 Cautious implementer may wish to layer cryptographic algorithms such 24 that an attacker would need to break all of them in order to 25 compromise the data being protected. For digital signatures, this is 26 referred to as "dual", and for encryption key establishment this as 27 referred to as "hybrid". This document, and its companions, defines 28 a specific instantiation of the dual and hybrid paradigm called 29 "composite" where multiple cryptographic algorithms are combined to 30 form a single key, signature, or key encapsulation mechanism (KEM) 31 such that they can be treated as a single atomic object at the 32 protocol level. 34 EDNOTE: the terms "dual" and "hybrid" are currently in flux. We 35 anticipate an Informational draft to normalize terminology, and will 36 update this draft accordingly. 38 This document defines the structures CompositeSignatureValue, and 39 CompositeParams, which are sequences of the respective structure for 40 each component algorithm. The generic composite variant is defined 41 which allows arbitrary combinations of signature algorithms to be 42 used in the CompositeSignatureValue and CompositeParams structures 43 without needing the combination to be pre-registered or pre-agreed. 44 The explicit variant is also defined which allows for a set of 45 signature algorithm identifier OIDs to be registered together as an 46 explicit composite signature algorithm and assigned an OID. 48 This document is intended to be coupled with corresponding documents 49 that define the structure and semantics of composite public and 50 private keys and encryption [I-D.draft-ounsworth-pq-composite-keys- 51 01], however may also be used with non-composite keys, such as when a 52 protocol combines multiple certificates into a single cryptographic 53 operation. 55 Status of This Memo 57 This Internet-Draft is submitted in full conformance with the 58 provisions of BCP 78 and BCP 79. 60 Internet-Drafts are working documents of the Internet Engineering 61 Task Force (IETF). Note that other groups may also distribute 62 working documents as Internet-Drafts. The list of current Internet- 63 Drafts is at https://datatracker.ietf.org/drafts/current/. 65 Internet-Drafts are draft documents valid for a maximum of six months 66 and may be updated, replaced, or obsoleted by other documents at any 67 time. It is inappropriate to use Internet-Drafts as reference 68 material or to cite them other than as "work in progress." 70 This Internet-Draft will expire on 10 December 2022. 72 Copyright Notice 74 Copyright (c) 2022 IETF Trust and the persons identified as the 75 document authors. All rights reserved. 77 This document is subject to BCP 78 and the IETF Trust's Legal 78 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 79 license-info) in effect on the date of publication of this document. 80 Please review these documents carefully, as they describe your rights 81 and restrictions with respect to this document. Code Components 82 extracted from this document must include Revised BSD License text as 83 described in Section 4.e of the Trust Legal Provisions and are 84 provided without warranty as described in the Revised BSD License. 86 Table of Contents 88 1. Changes in version -07 . . . . . . . . . . . . . . . . . . . 3 89 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 90 2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 91 3. Composite Signature Structures . . . . . . . . . . . . . . . 6 92 3.1. Composite Keys . . . . . . . . . . . . . . . . . . . . . 6 93 3.1.1. Key Usage Bits . . . . . . . . . . . . . . . . . . . 6 94 3.2. sa-CompositeSignature . . . . . . . . . . . . . . . . . . 7 95 3.3. CompositeSignatureValue . . . . . . . . . . . . . . . . . 7 96 3.4. Encoding Rules . . . . . . . . . . . . . . . . . . . . . 7 97 4. Algorithm Identifiers . . . . . . . . . . . . . . . . . . . . 8 98 4.1. id-alg-composite (Generic Composite Signatures) . . . . . 8 99 4.2. Explicit Composite Signatures . . . . . . . . . . . . . . 9 100 5. Composite Signature Processes . . . . . . . . . . . . . . . . 10 101 5.1. Composite Signature Generation Process . . . . . . . . . 10 102 5.2. Composite Signature Verification Process . . . . . . . . 12 103 6. Implementation Considerations . . . . . . . . . . . . . . . . 14 104 6.1. Backwards Compatibility . . . . . . . . . . . . . . . . . 15 105 6.1.1. OR modes . . . . . . . . . . . . . . . . . . . . . . 15 106 6.1.2. Parallel PKIs . . . . . . . . . . . . . . . . . . . . 16 107 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 108 8. Security Considerations . . . . . . . . . . . . . . . . . . . 17 109 8.1. Policy for Deprecated and Acceptable Algorithms . . . . . 17 110 8.2. OR Modes . . . . . . . . . . . . . . . . . . . . . . . . 17 111 8.2.1. Subset Signature Generation . . . . . . . . . . . . . 17 112 8.2.2. Subset Signature Verification . . . . . . . . . . . . 18 113 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 18 114 9.1. Normative References . . . . . . . . . . . . . . . . . . 19 115 9.2. Informative References . . . . . . . . . . . . . . . . . 19 116 Appendix A. Work in Progress . . . . . . . . . . . . . . . . . . 20 117 A.1. Combiner modes (KofN) . . . . . . . . . . . . . . . . . . 20 118 Appendix B. Creating explicit combinations . . . . . . . . . . . 21 119 Appendix C. Examples . . . . . . . . . . . . . . . . . . . . . . 21 120 C.1. Generic Composite Signature Examples . . . . . . . . . . 21 121 C.2. Explicit Composite Signature Examples . . . . . . . . . . 21 122 Appendix D. ASN.1 Module . . . . . . . . . . . . . . . . . . . . 21 123 Appendix E. Intellectual Property Considerations . . . . . . . . 22 124 Appendix F. Contributors and Acknowledgements . . . . . . . . . 23 125 F.1. Making contributions . . . . . . . . . . . . . . . . . . 23 126 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23 128 1. Changes in version -07 130 * Merged Generic Composite (Section 4.1) and Explicit Composite 131 (Section 4.2) into one document and made them share a wire 132 encoding (only differing by the OIDs used). 134 * Removed Composite-OR signature mode. 136 * Added Section 6.1 addressing backwards compatibility and ease of 137 migration concerns. 139 * Added CompositeParams := Alg1, Alg2, .. Algn as an input parameter 140 to the sig gen and verification processes. 142 TODO diff this against the public version and see if there are any 143 more changes. 145 2. Introduction 147 During the transition to post-quantum cryptography, there will be 148 uncertainty as to the strength of cryptographic algorithms; we will 149 no longer fully trust traditional cryptography such as RSA, Diffie- 150 Hellman, DSA and their elliptic curve variants, but we will also not 151 fully trust their post-quantum replacements until they have had 152 sufficient scrutiny and time to discover and fix implementation bugs. 153 Unlike previous cryptographic algorithm migrations, the choice of 154 when to migrate and which algorithms to migrate to, is not so clear. 155 Even after the migration period, it may be advantageous for an 156 entity's cryptographic identity to be composed of multiple public-key 157 algorithms. 159 The deployment of composite signatures using post-quantum algorithms 160 will face two challenges 162 * Algorithm strength uncertainty: During the transition period, some 163 post-quantum signature and encryption algorithms will not be fully 164 trusted, while also the trust in legacy public key algorithms will 165 start to erode. A relying party may learn some time after 166 deployment that a public key algorithm has become untrustworthy, 167 but in the interim, they may not know which algorithm an adversary 168 has compromised. 170 * Backwards compatibility: During the transition period, post- 171 quantum algorithms will not be supported by all clients. 173 This document provides a mechanism to address algorithm strength 174 uncertainty concerns by building on [draft-ounsworth-pq-composite- 175 keys-00] (NOTE: need kramdown formatting help with this ref) by 176 providing formats for encoding multiple signature values into 177 existing public signature fields, as well as the process for 178 validating a composite signature. Backwards compatibility is 179 addressed via using composite in conjunction with a non-composite 180 hybrid mode such as that described in [draft-becker-guthrie- 181 noncomposite-hybrid-auth-00] (NOTE: need kramdown formatting help 182 with this ref). 184 This document is intended for general applicability anywhere that 185 digital signatures are used within PKIX and CMS structures. 187 2.1. Terminology 189 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 190 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 191 "OPTIONAL" in this document are to be interpreted as described in BCP 192 14 [RFC2119] [RFC8174] when, and only when, they appear in all 193 capitals, as shown here. 195 The following terms are used in this document: 197 ALGORITHM: A standardized cryptographic primitive, as well as any 198 ASN.1 structures needed for encoding data and metadata needed to use 199 the algorithm. This document is primarily concerned with algorithms 200 for producing digital signatures. 202 BER: Basic Encoding Rules (BER) as defined in [X.690]. 204 CLIENT: Any software that is making use of a cryptographic key. This 205 includes a signer, verifier, encrypter, decrypter. 207 COMPONENT ALGORITHM: A single basic algorithm which is contained 208 within a composite algorithm. 210 COMPOSITE ALGORITHM: An algorithm which is a sequence of two or more 211 component algorithms, as defined in Section 3. 213 DER: Distinguished Encoding Rules as defined in [X.690]. 215 LEGACY: For the purposes of this document, a legacy algorithm is any 216 cryptographic algorithm currently is use which is not believe to be 217 resistant to quantum cryptanalysis. 219 PKI: Public Key Infrastructure, as defined in [RFC5280]. 221 POST-QUANTUM ALGORITHM: Any cryptographic algorithm which is believed 222 to be resistant to classical and quantum cryptanalysis, such as the 223 algorithms being considered for standardization by NIST. 225 PUBLIC / PRIVATE KEY: The public and private portion of an asymmetric 226 cryptographic key, making no assumptions about which algorithm. 228 SIGNATURE: A digital cryptographic signature, making no assumptions 229 about which algorithm. 231 STRIPPING ATTACK: An attack in which the attacker is able to 232 downgrade the cryptographic object to an attacker-chosen subset of 233 original set of component algorithms in such a way that it is not 234 detectable by the receiver. For example, substituting a composite 235 public key or signature for a version with fewer components. 237 3. Composite Signature Structures 239 In order for signatures to be composed of multiple algorithms, we 240 define encodings consisting of a sequence of signature primitives 241 (aka "component algorithms") such that these structures can be used 242 as a drop-in replacement for existing signature fields such as those 243 found in PKCS#10 [RFC2986], CMP [RFC4210], X.509 [RFC5280], CMS 244 [RFC5652]. 246 3.1. Composite Keys 248 A composite signature MAY be associated with a composite public key 249 as defined in [draft-ounsworth-pq-composite-keys-00] (NOTE: need 250 kramdown formatting help with this ref), but MAY also be associated 251 with multiple public keys from different sources, for example 252 multiple X.509 certificates, or multiple cryptographic modules. In 253 the latter case, composite signatures MAY be used as the mechanism 254 for carrying multiple signatures in a non-composite authentication 255 mechanism such as those described in [draft-becker-guthrie- 256 noncomposite-hybrid-auth-00] (NOTE: need kramdown formatting help 257 with this ref). 259 3.1.1. Key Usage Bits 261 For protocols such as X.509 [RFC5280] that specify key usage along 262 with the public key, then the composite public key associated with a 263 composite signature MUST have a signing-type key usage. 265 If the keyUsage extension is present in a Certification Authority 266 (CA) certificate that indicates id-composite-key, then any 267 combination of the following values MAY be present: 269 digitalSignature; 270 nonRepudiation; 271 keyCertSign; and 272 cRLSign. 274 If the keyUsage extension is present in an End Entity (EE) 275 certificate that indicates id-composite-key, then any combination of 276 the following values MAY be present: 278 digitalSignature; and 279 nonRepudiation; 281 3.2. sa-CompositeSignature 283 The ASN.1 algorithm object for a composite signature is: 285 sa-CompositeSignature SIGNATURE-ALGORITHM ::= { 286 IDENTIFIER identifier 287 VALUE CompositeSignatureValue 288 PARAMS ANY DEFINED BY ALGORITHM 289 PUBLIC-KEYS { pk-Composite } 290 SMIME-CAPS { IDENTIFIED BY id-alg-composite } } 291 } 293 The identifier specifies the type of composite signature and the 294 component algorithms. This document defines a generic composite 295 algorithm, identified by id-alg-composite, in Section 4.1, and allows 296 for other standards that will define explicit algorithms that specify 297 which component algorithms are to be contained within them. 299 3.3. CompositeSignatureValue 301 The output of the composite signature algorithm is the DER encoding 302 of the following structure: 304 CompositeSignatureValue ::= SEQUENCE SIZE (2..MAX) OF BIT STRING 306 Where each BIT STRING within the SEQUENCE is a signature value 307 produced by one of the component keys. It MUST contain one signature 308 value produced by each component algorithm, and in the same order as 309 in the associated CompositeParams object. 311 A CompositeSignatureValue MUST contain the same number of component 312 signatures as the corresponding public and private keys, and the 313 order of component signature values MUST correspond to the component 314 public keys. 316 The choice of SEQUENCE OF BIT STRING, rather than for example a 317 single BIT STRING containing the concatenated signature values, is to 318 gracefully handle variable-length signature values by taking 319 advantage of ASN.1's built-in length fields. 321 3.4. Encoding Rules 323 Many protocol specifications will require that composite signature 324 data structures be represented by an octet string or bit string. 326 When an octet string is required, the DER encoding of the composite 327 data structure SHALL be used directly. 329 EDNOTE: will this definition include an ASN.1 tag and length byte 330 inside the OCTET STRING object? If so, that's probably an extra 331 unnecessary layer. 333 When a bit string is required, the octets of the DER encoded 334 composite data structure SHALL be used as the bits of the bit string, 335 with the most significant bit of the first octet becoming the first 336 bit, and so on, ending with the least significant bit of the last 337 octet becoming the last bit of the bit string. 339 In the interests of simplicity and avoiding compatibility issues, 340 implementations that parse these structures MAY accept both BER and 341 DER. 343 4. Algorithm Identifiers 345 This section defines the algorithm identifier for generic composite, 346 as well as a framework for defining explicit combinations. This 347 section is not intended to be exhaustive and other authors may define 348 others so long as they are compatible with the structures and 349 processes defined in this and companion public and private key 350 documents. 352 Some use-cases desire the flexibility for clients to use any 353 combination of supported algorithms, while others desire the rigidity 354 of explicitly-specified combinations of algorithms. 356 4.1. id-alg-composite (Generic Composite Signatures) 358 The id-alg-composite object identifier is used for identifying a 359 generic composite signature. This algorithm allows arbitrary 360 combinations of signature algorithms to be used in the 361 CompositeSignatureValue and CompositeParams structures without 362 needing the combination to be pre-registered or pre-agreed. This 363 identifier MUST be used in sa-CompositeSignature.identifier. 365 id-alg-composite OBJECT IDENTIFIER ::= { 366 iso(1) identified-organization(3) dod(6) internet(1) private(4) 367 enterprise(1) OpenCA(18227) Algorithms(2) id-alg-composite(1) } 369 EDNOTE: this is a temporary OID for the purposes of prototyping. We 370 are requesting IANA to assign a permanent OID, see Section 7. 372 The following algorithm parameters MUST be included: 374 CompositeParams ::= SEQUENCE SIZE (2..MAX) OF AlgorithmIdentifier 376 The signature's CompositeParams sequence MUST contain the same 377 component algorithms listed in the same order as in the associated 378 CompositePublicKey. 380 The motivation for this variant is primarily for prototyping work 381 prior to the standardization of algorithm identifiers for explicit 382 combinations of algorithms. However, the authors envision that this 383 variant will remain relevant beyond full standardization for example 384 in environments requiring very high levels of crypto agility, for 385 example where clients support a large number of algorithms or where a 386 large number of keys will be used at a time and it is therefore 387 prohibitive to define algorithm identifiers for every combination of 388 pairs, triples, quadruples, etc of algorithms. 390 4.2. Explicit Composite Signatures 392 This variant provides a rigid way of specifying supported 393 combinations of algorithms. 395 The motivation for this variant is to make it easier to reference and 396 enforce specific combinations of algorithms. The authors envision 397 this being useful for client-server negotiated protocols, protocol 398 designers who wish to place constraints on allowable algorithm 399 combinations in the protocol specification, as well as audited 400 environments that wish to prove that only certain combinations will 401 be supported by clients. 403 Explicit algorithms must define a new signature algorithm which 404 consists of: 406 * A new algorithm identifier OID for the explicit algorithm. 408 * The algorithm identifier OID and PUBLIC-KEY type of each component 409 algorithm. 411 * Signature parameters either declared ABSENT, or defined with a 412 type and encoding. 414 See Appendix B for guidance on creating and registering OIDs for 415 specific explicit combinations. 417 For explicit algorithms, it is not necessary to carry a 418 CompositeParams with the list of component algorithms in the 419 signature algorithm parameters because clients can infer the expected 420 component algorithms from the algorithm identifier. The PARAMS is 421 left optional because some types of component algorithms will require 422 parameters to be carried, such as RSASSA-PSS-params as defined in 423 [RFC8017]. Section 3.2 defines PARAMS ANY DEFINED BY ALGORITHM so 424 that explicit algorithms may define params as ABSENT, use 425 CompositeParams defined in Section 4.1 or use any other encoding that 426 is appropriate. 428 In this variant, the signature is encoded as defined in Section 3.2, 429 however the sa-CompositeSignature.identifier SHALL be an OID which is 430 registered to represent a specific combination of component signature 431 algorithms. See Appendix C for examples. 433 5. Composite Signature Processes 435 This section specifies the processes for generating and verifying 436 composite signatures. 438 This process addresses algorithm strength uncertainty by providing 439 the verifier with parallel signatures from all the component 440 signature algorithms; thus forging the composite signature would 441 require forging all of the component signatures. 443 5.1. Composite Signature Generation Process 445 Generation of a composite signature involves applying each component 446 algorithm's signature process to the input message according to its 447 specification, and then placing each component signature value into 448 the CompositeSignatureValue structure defined in Section 3.2. 450 The following process is used to generate composite signature values. 452 Input: 453 K1, K2, .., Kn Signing private keys. See note below on 454 composite inputs. 456 A1, A2, ... An Component signature algorithms. See note below on 457 composite inputs. 459 M Message to be signed, an octet string 461 Output: 462 S The signatures, a CompositeSignatureValue 464 Signature Generation Process: 465 1. Generate the n component signatures independently, 466 according to their algorithm specifications. 468 for i := 1 to n 469 Si := Sign( Ki, Ai, M ) 471 2. Encode each component signature S1, S2, .., Sn into a BIT STRING 472 according to its algorithm specification. 474 S ::= Sequence { S1, S2, .., Sn } 476 3. Output S 478 Note on composite inputs: the method of providing the list of 479 component keys and algorithms is flexible and beyond the scope of 480 this pseudo-code, for example they may be carried in 481 CompositePrivateKey and CompositeParams structures. It is also 482 possible to generate a composite signature that combines signatures 483 from distinct keys stored in separate software or hardware keystores. 484 Variations in the process to accommodate particular private key 485 storage mechanisms are considered to be conformant to this document 486 so long as it produces the same output as the process sketched above. 488 Since recursive composite public keys are disallowed in ~~ Reference 489 draft-ounsworth-pq-composite-pubkeys sec-composite-pub-keys ~~, no 490 component signature may itself be a composite; ie the signature 491 generation process MUST fail if one of the private keys K1, K2, .., 492 Kn is a composite with the OID id-alg-composite. 494 A composite signature MUST produce, and include in the output, a 495 signature value for every component key in and include in the output, 496 a signature value for every component key in the corresponding 497 CompositePublicKey, and they MUST be in the same order; ie in the 498 output, S1 MUST correspond to K1, S2 to K2, etc. The authors 499 recognize that there may be valid use cases for "subset signature 500 generation"; see Section 8.2.1 for further discussion of security 501 implications, and Section 6.1 for further discussion of backwards 502 compatibility implications. 504 For security when using a generic composite signature algorithm as 505 defined in Section 4.1, the list of component signature algorithms 506 A1, A2, .., An, which may be carried in a CompositeParams object, 507 SHOULD be included in the signed message M to prevent an attacker 508 from substituting a weaker algorithm which is compatible with the 509 same public key. This attack is not unique or new to the composite 510 format. 512 5.2. Composite Signature Verification Process 514 Verification of a composite signature involves applying each 515 component algorithm's verification process according to its 516 specification. 518 In the absence of an application profile specifying otherwise, 519 compliant applications MUST output "Valid signature" (true) if and 520 only if all component signatures were successfully validated, and 521 "Invalid signature" (false) otherwise. 523 The following process is used to perform this verification. 525 Input: 526 P1, P2, .., Pn Public verification keys. See note below on 527 composite inputs. 529 M Message whose signature is to be verified, 530 an octet string 532 S1, S2, .., Sn Component signature values to be verified. 533 See note below on composite inputs. 535 A1, A2, ... An Component signature algorithms. See note 536 below on composite inputs. 538 Output: 539 Validity (bool) "Valid signature" (true) if the composite 540 signature is valid, "Invalid signature" 541 (false) otherwise. 543 Signature Verification Procedure:: 544 1. Check keys, signatures, and algorithms lists for consistency. 546 If Error during Desequencing, or the three sequences have 547 different numbers of elements, or any of the public keys 548 P1, P2, .., Pn or algorithm identifiers A1, A2, .., An are 549 composite with the OID id-alg-composite or an explicit composite 550 OID then output "Invalid signature" and stop. 552 2. Check each component signature individually, according to its 553 algorithm specification. 554 If any fail, then the entire signature validation fails. 556 for i := 1 to n 557 if not verify( Pi, M, Si, Ai ), then 558 output "Invalid signature" 560 if all succeeded, then 561 output "Valid signature" 563 Note on composite inputs: the method of providing the list of 564 component keys, algorithms and signatures is flexible and beyond the 565 scope of this pseudo-code, for example they may be carried in 566 CompositePublicKey, CompositeParams, and compositesignaturevalue 567 structures. It is also possible to verify a composite signature 568 where the component public verification keys belong, for example, to 569 separate X.509 certificates or cryptographic modules. Variations in 570 the process to accommodate particular public verification key storage 571 mechanisms are considered to be conformant to this document so long 572 as it produces the same output as the process sketched above. 574 Since recursive composite public keys are disallowed in ~~ Reference 575 draft-ounsworth-pq-composite-keys sec-composite-pub-keys ~~, no 576 component signature may be composite; ie the signature verification 577 procedure MUST fail if any of the public keys P1, P2, .., Pn or 578 algorithm identifiers A1, A2, .., An are composite with the OID id- 579 alg-composite. 581 Some verification clients may include a policy mechanism for 582 specifying acceptable subsets of algorithms. In these cases, 583 implementer MAY, in the interest of performance of compatibility, 584 modify the above process to skip one or more signature validations as 585 per their local client policy. See Section 8.2 for a discussion of 586 associated risks. 588 In the absence of such a policy mechanism that can be easily updated 589 to reflect new cryptanalytic breakthroughs, clients MUST perform 590 signature verifications in the AND mode defined here. See 591 Section 8.2.1 for further discussion of security implications of 592 subset signature verifications, and Section 6.1 for further 593 discussion of backwards compatibility implications. 595 6. Implementation Considerations 597 This section addresses practical issues of how this draft affects 598 other protocols and standards. 600 ~~~ BEGIN EDNOTE 10~~~ 602 EDNOTE 10: Possible topics to address: 604 * The size of these certs and cert chains. 606 * In particular, implications for (large) composite keys / 607 signatures / certs on the handshake stages of TLS and IKEv2. 609 * If a cert in the chain is a composite cert then does the whole 610 chain need to be of composite Certs? 612 * We could also explain that the root CA cert does not have to be of 613 the same algorithms. The root cert SHOULD NOT be transferred in 614 the authentication exchange to save transport overhead and thus it 615 can be different than the intermediate and leaf certs. 617 * We could talk about overhead (size and processing). 619 * We could also discuss backwards compatibility. 621 * We could include a subsection about implementation considerations. 623 ~~~ END EDNOTE 10~~~ 625 6.1. Backwards Compatibility 627 As noted in the introduction, the post-quantum cryptographic 628 migration will face challenges in both ensuring cryptographic 629 strength against adversaries of unknown capabilities, as well as 630 providing ease of migration. The composite mechanisms defined in 631 this document primarily address cryptographic strength, however this 632 section contains notes on how backwards compatibility may be 633 obtained. 635 The term "ease of migration" is used here to mean that existing 636 systems can be gracefully transitioned to the new technology without 637 requiring large service disruptions or expensive upgrades. The term 638 "backwards compatibility" is used here to mean something more 639 specific; that existing systems as they are deployed today can 640 interoperate with the upgraded systems of the future. 642 These migration and interoperability concerns need to be thought 643 about in the context of various types of protocols that make use of 644 X.509 and PKIX with relation to digital signature objects, from 645 online negotiated protocols such as TLS 1.3 [RFC8446] and IKEv2 646 [RFC7296], to non-negotiated asynchronous protocols such as S/MIME 647 signed email [RFC8551], document signing such as in the context of 648 the European eIDAS regulations [eIDAS2014], and publicly trusted code 649 signing [codeSigningBRsv2.8], as well as myriad other standardized 650 and proprietary protocols and applications that leverage CMS 651 [RFC5652] signed structures. 653 6.1.1. OR modes 655 Section 5.1 and Section 5.2 make reference to subset signature 656 generation and verification modes to achieve an OR relation between 657 component signatures, where senders and / or receivers are permitted 658 to ignore some component keys. Some envisioned uses of this include 659 environments where the client encounters a component signature 660 algorithm for which it does not posses a compatible implementation 661 but wishes to proceed with the signature verification using the 662 subset of component signatures for which it does have compatible 663 implementations. Such a mechanism could be designed to provide ease 664 of migration by allowing for composite keys to be distributed and 665 used before all clients in the environment are fully upgraded, but it 666 does not allow for full backwards compatibility since clients would 667 at least need to be upgraded from their current state to be able to 668 parse the composite structures. 670 6.1.2. Parallel PKIs 672 We present the term "Parallel PKI" to refer to the setup where a PKI 673 end entity possesses two or more distinct public keys or certificates 674 for the same identity (name), but containing keys for different 675 cryptographic algorithms. One could imagine a set of parallel PKIs 676 where an existing PKI using legacy algorithms (RSA, ECC) is left 677 operational during the post-quantum migration but is shadowed by one 678 or more parallel PKIs using pure post quantum algorithms or composite 679 algorithms (legacy and post-quantum). 681 Equipped with a set of parallel public keys in this way, a client 682 would have the flexibility to choose which public key(s) or 683 certificate(s) to use in a given signature operation. 685 For negotiated protocols, the client could choose which public key(s) 686 or certificate(s) to use based on the negotiated algorithms, or could 687 combine two of the public keys for example in a non-composite hybrid 688 method such as [draft-becker-guthrie-noncomposite-hybrid-auth-00] 689 (NOTE: need kramdown formatting help with this ref) or [draft- 690 guthrie-ipsecme-ikev2-hybrid-auth-00]. Note that it is possible to 691 use the signature algorithms defined in Section 4 as a way to carry 692 the multiple signature values generated by one of the non-composite 693 public mechanism in protocols where it is easier to support the 694 composite signature algorithms than to implement such a mechanism in 695 the protocol itself. There is also nothing precluding a composite 696 public key from being one of the components used within a non- 697 composite authentication operation; this may lead to greater 698 convenience in setting up parallel PKI hierarchies that need to 699 service a range of clients implementing different styles of post- 700 quantum migration strategies. 702 For non-negotiated protocols, the details for obtaining backwards 703 compatibility will vary by protocol, but for example in CMS 704 [RFC5652], the inclusion of multiple SignerInfo objects is often 705 already treated as an OR relationship, so including one for each of 706 the signer's parallel PKI public keys would, in many cases, have the 707 desired effect of allowing the receiver to choose one they are 708 compatible with and ignore the others, thus achieving full backwards 709 compatibility. 711 7. IANA Considerations 713 The ASN.1 module OID is TBD. The id-alg-composite OID is to be 714 assigned by IANA. The authors suggest that IANA assign an OID on the 715 id-pkix arc: 717 id-alg-composite OBJECT IDENTIFIER ::= { 718 iso(1) identified-organization(3) dod(6) internet(1) security(5) 719 mechanisms(5) pkix(7) algorithms(6) composite(??) } 721 8. Security Considerations 723 8.1. Policy for Deprecated and Acceptable Algorithms 725 Traditionally, a public key, certificate, or signature contains a 726 single cryptographic algorithm. If and when an algorithm becomes 727 deprecated (for example, RSA-512, or SHA1), it is obvious that 728 clients performing signature verifications should be updated to fail 729 to validate signatures using these algorithms. 731 In the composite model this is less obvious since a single public 732 key, certificate, or signature may contain a mixture of deprecated 733 and non-deprecated algorithms. Moreover, implementers may decide 734 that certain cryptographic algorithms have complementary security 735 properties and are acceptable in combination even though neither 736 algorithm is acceptable by itself. 738 Specifying a modified verification algorithm to handle these 739 situations is beyond the scope of this draft, but could be desirable 740 as the subject of an application profile document, or to be up to the 741 discretion of implementers. 743 2. Check policy to see whether A1, A2, ..., An constitutes a valid 744 combination of algorithms. 746 if not checkPolicy(A1, A2, ..., An), then 747 output "Invalid signature" 749 8.2. OR Modes 751 8.2.1. Subset Signature Generation 753 This document defines a composite signature generation process in 754 Section 5.1 where the signer MUST produce a signature value with each 755 of their component private keys, this providing full protection of 756 the content under all available component algorithms. 758 The authors recognize that there may be cases where a client may wish 759 to generate a composite signature that only uses a subset of the 760 available component algorithms, for example to save bandwidth, or 761 because a client has been issued a key for which it does not (yet) 762 have implementations of all component algorithms. This could be 763 easily encoded by placing a NULL value into the corresponding field 764 of the CompositeSignatureValue. However, this mode was intentionally 765 omitted from this specification as it trivially allows for stripping 766 attacks where an attacker replaces a valid component signature value 767 with NULL, thus reducing the security of the composite signature to 768 the weakest of the available component algorithms. 770 Implementer who wish to perform subset signature generations are 771 advised to couple it with an out-of-band policy mechanism that limits 772 the potential for stripping attacks. Note that, in an effort to keep 773 compliant implementations simple and secure, implementations claiming 774 to be compliant with this draft MUST NOT generate subset signatures 775 in this way, and MUST reject during verification any subset 776 signatures that they encounter. 778 8.2.2. Subset Signature Verification 780 This document defines a composite signature verification process in 781 Section 5.2 where the verifier verifies all component signatures and 782 fails if any component fails. The authors recognize that there will 783 be scenarios where the verifier considers a single component 784 algorithm -- or subset of component algorithms -- to provide 785 sufficient security, and therefore for performance reasons wishes to 786 skip the verification of one or more component signatures. 788 -- harmonize this with Serge's blurb -- 790 Implementers who wish to perform subset signature verifications are 791 advised to couple it with an out-of-band policy mechanism that can 792 control the list of acceptable algorithm combinations, and keep this 793 list up to date as new cryptanalytic advances are made. 795 Risks: 797 * Failing to update client verification policy in response to 798 advances in cryptanalysis 800 * Verifications of a subset of signatures leads to ambiguity in the 801 security strength of the signature verification; ie if a message 802 carries two signatures, one at 128 bits and the other at 112 bits 803 of security and clients are verifying in an OR mode with flexible 804 policy, then it becomes difficult to audit the security strength 805 used at runtime. 807 * Moreover, verifying multiple algorithms provides security even in 808 the event that one of the algorithms has already been broken, but 809 knowledge of the break has not been made public yet. 811 9. References 812 9.1. Normative References 814 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 815 Requirement Levels", BCP 14, RFC 2119, 816 DOI 10.17487/RFC2119, March 1997, 817 . 819 [RFC2986] Nystrom, M. and B. Kaliski, "PKCS #10: Certification 820 Request Syntax Specification Version 1.7", RFC 2986, 821 DOI 10.17487/RFC2986, November 2000, 822 . 824 [RFC4210] Adams, C., Farrell, S., Kause, T., and T. Mononen, 825 "Internet X.509 Public Key Infrastructure Certificate 826 Management Protocol (CMP)", RFC 4210, 827 DOI 10.17487/RFC4210, September 2005, 828 . 830 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., 831 Housley, R., and W. Polk, "Internet X.509 Public Key 832 Infrastructure Certificate and Certificate Revocation List 833 (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008, 834 . 836 [RFC5652] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70, 837 RFC 5652, DOI 10.17487/RFC5652, September 2009, 838 . 840 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 841 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 842 May 2017, . 844 [RFC8411] Schaad, J. and R. Andrews, "IANA Registration for the 845 Cryptographic Algorithm Object Identifier Range", 846 RFC 8411, DOI 10.17487/RFC8411, August 2018, 847 . 849 [X.690] ITU-T, "Information technology - ASN.1 encoding Rules: 850 Specification of Basic Encoding Rules (BER), Canonical 851 Encoding Rules (CER) and Distinguished Encoding Rules 852 (DER)", ISO/IEC 8825-1:2015, November 2015. 854 9.2. Informative References 856 [Bindel2017] 857 Bindel, N., Herath, U., McKague, M., and D. Stebila, 858 "Transitioning to a quantum-resistant public key 859 infrastructure", 2017, . 862 [I-D.becker-guthrie-noncomposite-hybrid-auth] 863 Becker, A., Guthrie, R., and M. J. Jenkins, "Non-Composite 864 Hybrid Authentication in PKIX and Applications to Internet 865 Protocols", Work in Progress, Internet-Draft, draft- 866 becker-guthrie-noncomposite-hybrid-auth-00, 22 March 2022, 867 . 870 [I-D.ounsworth-pq-composite-keys] 871 Ounsworth, M. and M. Pala, "Composite Public and Private 872 Keys For Use In Internet PKI", Work in Progress, Internet- 873 Draft, draft-ounsworth-pq-composite-keys-00, 12 July 2021, 874 . 877 [RFC3279] Bassham, L., Polk, W., and R. Housley, "Algorithms and 878 Identifiers for the Internet X.509 Public Key 879 Infrastructure Certificate and Certificate Revocation List 880 (CRL) Profile", RFC 3279, DOI 10.17487/RFC3279, April 881 2002, . 883 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 884 "PKCS #1: RSA Cryptography Specifications Version 2.2", 885 RFC 8017, DOI 10.17487/RFC8017, November 2016, 886 . 888 Appendix A. Work in Progress 890 A.1. Combiner modes (KofN) 892 For content commitment use-cases, such as legally-binding non- 893 repudiation, the signer (whether it be a CA or an end entity) needs 894 to be able to specify how its signature is to be interpreted and 895 verified. 897 For now we have removed combiner modes (AND, OR, KofN) from this 898 draft, but we are still discussing how to incorporate this for the 899 cases where it is needed (maybe a X.509 v3 extension, or a signature 900 algorithm param). 902 Appendix B. Creating explicit combinations 904 The following ASN.1 Information Objects may be useful in defining and 905 parsing explicit pairs of signature algorithms. 907 ... TODO ... copy & adapt from the keys draft. 909 Appendix C. Examples 911 C.1. Generic Composite Signature Examples 913 TODO 915 C.2. Explicit Composite Signature Examples 917 TODO 919 Appendix D. ASN.1 Module 921 923 Composite-Signatures-2019 924 { TBD } 926 DEFINITIONS IMPLICIT TAGS ::= BEGIN 928 EXPORTS ALL; 930 IMPORTS 931 PUBLIC-KEY, SIGNATURE-ALGORITHM 932 FROM AlgorithmInformation-2009 -- RFC 5912 [X509ASN1] 933 { iso(1) identified-organization(3) dod(6) internet(1) 934 security(5) mechanisms(5) pkix(7) id-mod(0) 935 id-mod-algorithmInformation-02(58) } 937 SubjectPublicKeyInfo 938 FROM PKIX1Explicit-2009 939 { iso(1) identified-organization(3) dod(6) internet(1) 940 security(5) mechanisms(5) pkix(7) id-mod(0) 941 id-mod-pkix1-explicit-02(51) } 943 OneAsymmetricKey 944 FROM AsymmetricKeyPackageModuleV1 945 { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) 946 pkcs-9(9) smime(16) modules(0) 947 id-mod-asymmetricKeyPkgV1(50) } ; 949 -- 950 -- Object Identifiers 951 -- 953 id-alg-composite OBJECT IDENTIFIER ::= { TBD } 955 -- 956 -- Public Key 957 -- 959 pk-Composite PUBLIC-KEY ::= { 960 IDENTIFIER id-alg-composite 961 KEY CompositePublicKey 962 PARAMS ARE absent 963 PRIVATE-KEY CompositePrivateKey 964 } 966 CompositePublicKey ::= SEQUENCE SIZE (2..MAX) OF SubjectPublicKeyInfo 968 CompositePrivateKey ::= SEQUENCE SIZE (2..MAX) OF OneAsymmetricKey 970 -- 971 -- Signature Algorithm 972 -- 974 sa-CompositeSignature SIGNATURE-ALGORITHM ::= { 975 IDENTIFIER id-alg-composite 976 VALUE CompositeSignatureValue 977 PARAMS TYPE CompositeParams ARE required 978 PUBLIC-KEYS { pk-Composite } 979 SMIME-CAPS { IDENTIFIED BY id-alg-composite } } 981 CompositeParams ::= SEQUENCE SIZE (2..MAX) OF AlgorithmIdentifier 983 CompositeSignatureValue ::= SEQUENCE SIZE (2..MAX) OF BIT STRING 985 END 987 989 Appendix E. Intellectual Property Considerations 991 The following IPR Disclosure relates to this draft: 993 https://datatracker.ietf.org/ipr/3588/ 995 Appendix F. Contributors and Acknowledgements 997 This document incorporates contributions and comments from a large 998 group of experts. The Editors would especially like to acknowledge 999 the expertise and tireless dedication of the following people, who 1000 attended many long meetings and generated millions of bytes of 1001 electronic mail and VOIP traffic over the past year in pursuit of 1002 this document: 1004 John Gray (Entrust), Serge Mister (Entrust), Scott Fluhrer (Cisco 1005 Systems), Panos Kampanakis (Cisco Systems), Daniel Van Geest (ISARA), 1006 Tim Hollebeek (Digicert), and Francois Rousseau. 1008 We are grateful to all, including any contributors who may have been 1009 inadvertently omitted from this list. 1011 This document borrows text from similar documents, including those 1012 referenced below. Thanks go to the authors of those documents. 1013 "Copying always makes things easier and less error prone" - 1014 [RFC8411]. 1016 F.1. Making contributions 1018 Additional contributions to this draft are welcome. Please see the 1019 working copy of this draft at, as well as open issues at: 1021 https://github.com/EntrustCorporation/draft-ounsworth-composite-sigs 1023 Authors' Addresses 1025 Mike Ounsworth 1026 Entrust Limited 1027 2500 Solandt Road -- Suite 100 1028 Ottawa, Ontario K2K 3G5 1029 Canada 1030 Email: mike.ounsworth@entrust.com 1032 Massimiliano Pala 1033 CableLabs 1034 Email: director@openca.org