Convertible Forms with Multiple Keys and Signatures For Use In Internet X.509 Certificates

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

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 20 April 2025.¶

Copyright Notice

Copyright (c) 2024 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. Introduction

The advent of quantum computing poses a significant threat to the security of traditional cryptographic systems. Classical cryptographic algorithms, such as RSA, ECDSA, and their elliptic curve variants, rely on the computational difficulty of certain number-theoretic problems. However, these algorithms are vulnerable to attacks by adversaries with access to a Cryptograpically-Relevant Quantum Computer (CRQC), which can efficiently solve these problems and compromise the security of the entire system.¶

To address this vulnerability, there is a pressing need to migrate to post-quantum cryptography (PQC), which employs algorithms resistant to quantum attacks. This transition presents unique challenges, as the security of PQC algorithms is not yet fully established and requires extensive evaluation. Additionally, during the migration period, systems must maintain compatibility with legacy devices that do not support PQC.¶

This document introduces new Certificate Signing Request (CSR) attributes and X.509v3 certificate extensions to facilitate the migration of post-quantum signature algorithms while ensuring compatibility with existing systems. A key design requirement for this scheme is to enable the coexistence of two public keys and two signatures within a single certificate, and allowing for switching between four distinct certificate forms during transmission without impacting verification.¶

By embedding an alternative public key and an alternative signature into extensions, multiple certificate chains can be effectively embedded within a single chain. This enables legacy devices to continue using traditional cryptographic algorithms, while upgraded devices can utilize PQC algorithms and remain interoperable with legacy devices. The scheme also allows for the flexible selection of certificate forms, including both "by reference" and "by value" options, to accommodate different device scenarios and optimize bandwidth usage.¶

2. Design Overview

+------------+      CSR (pk_1, pk_2, sig_1, sig_2)        +------------+
| Subscriber | ---------------------------------------->  |   Issuer   |
| sk_1, sk_2 | <----------------------------------------  | sk_3, sk_4 |
+------------+   Certificate (pk_1, pk_2, sig_3, sig_4)   +------------+
  ^   ^   ^
  |   |   |
  |   |   | ByRef Certificate (pk_1, hash(pk_2), hash(sig_3), sig_4)
  |   |   +---------------------------------------------------+
  |   |                                                       |
  |   | ByVal Certificate (pk_1, pk_2, sig_3, sig_4)          |
  |   | or ByRef Certificate                                  |
  |   +------- ------------------------------+                |
  |                                          |                |
  v                                          v                v
+-------------+  Download data  +------------------+  +----------------+
|    Store    | <-------------> | Upgraded Devices |  | Legacy Devices |
| pk_2, sig_3 |                 |   pk_3, pk_4     |  |      pk_4      |
+-------------+                 +------------------+  +----------------+

To achieve hybrid signatures in a PKI system, a subscriber needs to apply a certificate that contains two public keys to use hybrid signature schemes. Meanwhile, the issuer needs to sign a certificate with two secret keys and include two signatures in the certificate.¶

The design of this document is outlined as follows:¶

1. A subscriber selects two signature algorithms and generates two key pairs (pk_1, sk_1) and (pk_2, sk_2). It then uses sk_1 and sk_2 to generate sig_1 and sig_2, respectively. The signatures are proof-of-possession of the secret keys sk_1 and sk_2. The two public keys and signatures are included in a Certificate Signing Request as defined in Section 4.1.¶

2. An issuer holds two key pairs (pk_3, sk_3) and (pk_4, sk_4). Upon receiving a CSR, the issuer uses its two secret keys to sign the information provided in the CSR and constructs a certificate as defined in Section 4.3. A certificate has at most four forms as defined in Table 1. The issuer signs Form 4 of the certificate, which includes the values of pk_1 and sig_4, and the hashes of pk_2 and sig_3. The issuer converts the certificate to Form 1 as in Section 4.4, which includes all plain values, and sends the certificate in Form 1 to the subscriber.¶

3. Upon receiving the certificate, a subscriber puts the alternative public key pk_2 and the alternative signature sig_3 into specific locaitons.¶

4. For legacy devices that have not been upgraded, only traditional algorithms are used to establish communication with the subscriber. In this case, certificates in Form 4 are transfered, which only include pk_1, sig_4 and hashes of pk_2 and sig_3.¶

5. For upgraded devices, both traditional algorithms and post-quantum algorithms can be used. In this case, the devices can select a proper certificate form base on their preferences.¶

3. Alternative Public-Key Algorithm Objects

id-altSubPubKeyHashAlgAttr   OBJECT IDENTIFIER ::= {TBD}
id-altSubPubKeyLocAttr       OBJECT IDENTIFIER ::= {TBD}
id-altSigValueHashAlgAttr    OBJECT IDENTIFIER ::= {TBD}
id-altSigValueLocAttr        OBJECT IDENTIFIER ::= {TBD}

id-altSubPubKeyExt           OBJECT IDENTIFIER ::= {TBD}
id-altSignatureExt           OBJECT IDENTIFIER ::= {TBD}

altSubPubKeyHashAlgAttr ATTRIBUTE ::=  {
     WITH SYNTAX AlgorithmIdentifier
     ID id-altSubPubKeyHashAlgAttr }

altSubPubKeyLocAttr ATTRIBUTE ::= {
  location     URI
  ID           id-altSubPubKeyLocAttr }

altSigValueHashAlgAttr ATTRIBUTE ::= {
     WITH SYNTAX AlgorithmIdentifier
     ID id-altSigValueHashAlgAttr }

altSigValueLocAttr ATTRIBUTE ::= {
  location     URI
  ID           id-altSigValueLocAttr }

AltSubPubKeyExt ::= SEQUENCE {
  byVal BOOLEAN DEFAULT FALSE,
  plainOrHash BIT STRING,
  altAlgorithm AlgorithmIdentifier,
  hashAlg AlgorithmIdentifier OPTIONAL,
  location URI OPTIONAL }

AltSignatureExt ::= SEQUENCE {
  byVal BOOLEAN DEFAULT FALSE,
  plainOrHash BIT STRING,
  altSigAlgorithm AlgorithmIdentifier,
  hashAlg AlgorithmIdentifier OPTIONAL,
  location URI OPTIONAL }

4. Scheme Workflow: From CSR to Signed Certificate

CertificationRequest ::= SEQUENCE {
      certificationRequestInfo CertificationRequestInfo,
      signatureAlgorithm AlgorithmIdentifier{{ SignatureAlgorithms }},
      signature          BIT STRING
}

CertificationRequestInfo ::= SEQUENCE {
      version       INTEGER { v1(0) } (v1,...),
      subject       Name,
      subjectPKInfo SubjectPublicKeyInfo{{ PKInfoAlgorithms }},
      attributes    [0] Attributes{{ CRIAttributes }}
}

Certificate  ::=  SEQUENCE  {
     tbsCertificate       TBSCertificate,
     signatureAlgorithm   AlgorithmIdentifier,
     signatureValue       BIT STRING }

Issuer                   Subscriber             Relying Party              Location
  | <-------  CSR  --------- |                        |                        |
  |[Sign on Form 4]          |                        |                        |
  | Certificate /Form 1/3--> |                        |                        |
  |               [extract pk_2,sig_3]                |                        |
  |                          |     -------------Upload pk_2, sig_3-----------> |
  |              [Construct Form 1/2/3/4]             |                        |
  |                          |                        |                        |
  |                          |                        |                        |
  |                          | Certificate /Form 1--> |                        |
  |                          |               [Convert to Form 4]               |
  |                          |                     [verify]                    |
  |                          |                        |                        |
  |                          | Certificate /Form 2--> |                        |
  |                          |                        | <----Fetch sig_3-----> |
  |                          |               [Convert to Form 4]               |
  |                          |                     [verify]                    |
  |                          |                        |                        |
  |                          | Certificate /Form 3--> |                        |
  |                          |                        | <----Fetch pk_2------> |
  |                          |               [Convert to Form 4]               |
  |                          |                     [verify]                    |
  |                          |                        |                        |
  |                          | Certificate /Form 4--> |                        |
  |                          |                        | <--Fetch pk_2,sig_3--> |
  |                          |                     [verify]                    |

5. Use Case: Post-Quantum Migration

During the post-quantum migration, there is going to be a long period of time where legacy devices and upgraded devices coexist. In this scenario, when applying for a certificate, the subscriber selects a traditional signature algorithm for the first public key and a post-quantum signature algorithm for the alternative public key. The issuer also uses a traditional signature algorithm and a post-quantum signature algorithm for its first and alternative public keys, respectively.¶

Assume that a device have some mechanisms to share its capabilities with a subscriber. For example, in TLS, the client sends a ClientHello message, which includes its supported algorithm list and a set of extension requests.¶

Legacy devices only support traditional algorithms and do not recognize the AltSubPubKeyExt extension. In this case, the subscriber sends a certificate in Form 4 to legacy devices. Then, the legacy device ignores the proposed two extensions, verifies the certificate with the issuer's traditional public key, and retrieves the subject's traditional public key from the certificate. The legacy device can then use the subject's traditional public key to verify the identity of the subscriber. This allows legacy devices to continue using traditional algorithms as before, ensuring backward compatibility.¶

Upgraded devices, which support both traditional and post-quantum algorithms, recognize the proposed two extensions. An upgraded device can request any form of a certificate according to its preference. Given a certificate, the device determines its form and verifies the certificate follows Section 4.5. After the verification, the device can use subject's one or two public keys to verify the identity of the subscriber.¶

An upgraded device can obtain the actual value of the alternative materials by requesting a certificate in FORM 1 during the first communication with the subscriber and cache the alternative public key. Later the device can select certificates in other forms to save transmission overhead.¶

6. IANA Considerations

TODO: ADD a table to include the required OIDs.¶

7. Security Considerations

Many of the security considerations for this document closely follow those of [RFC5280] and [I.D.draft-truskovsky-lamps-pq-hybrid-x509-02]. However, the extension introduced in this document does bring rise to additional considerations.¶

The certificate issued as in this document MAY has location fields to allow the relying party to download the alternative materials. It is possible that a malicious actor replaces the content at the refered location, but this action will be detected since the hash of the actual value is given in the certificate.¶

This document uses the composite hybrid signature scheme in CSR follows the description in [I.D.draft-truskovsky-lamps-pq-hybrid-x509-02]. It achieves the Non-Separability security property, which is defined in Section 1.4.3. of [I.D.draft-ietf-pquip-hybrid-signature-spectrums-00]. So an attempt to remove any of the public key or signature of a subscriber will be detected.¶

For the certificate issuance, the issuer uses the nested hybrid signature scheme to sign the information of a certificate with two private keys. To achieve backward-compatibility, the subscriber SHOULD use a traditional signature algorithm and a post-quantum signature algorithm for the outer and inner signature algorithms, respectively. One of the main drawback of nested hybrid signature is that the outer signature can be stripped. But in the case of a certificate, the strpping attack will be detected. Another problem is that if a malicious actor with a CRQC breaks the outer traditional signature algorithm, it can alter all the inner message, including the location, flag and hash for the inner signature. In this powerful attack, a relying party will download a forged signature from a location controlled by the attacker and passed the hash comparison. But when the relying party use the issue's alternative public key to verify the downloaded signature, the verification will certainly fail.¶

For certificate transparency services, certificates in FORM 4 SHOULD be logged and monitored.¶

For a legacy device, to achieve backward-compatibility, it uses the signature field to verify the certificate and the first public key of the subscriber to authenticate handshake transcripts. In this case, there is no post-quantum security.¶

For an upgraded device, the situation is more complicated. It can only use the first public key or two public keys. It can only verify the signature field or verify two signatures. All these choices depend on the communication parties' preferences and/or configuration. The mechanism described in this document gives 4 forms of a certificate. However, the upper-layer applications or protocols needs to decide the strategy when applying the proposed mechanism.¶

8. References

Appendix A. Appendix 1 [REPLACE/DELETE]

This becomes an Appendix [REPLACE]¶

Acknowledgements

This template uses extracts from templates written by Pekka Savola, Elwyn Davies and Henrik Levkowetz. [REPLACE]¶

Authors' Addresses