Network Working Group S. Kousidis Internet-Draft BSI Intended status: Informational J. Roth Expires: 2 August 2024 F. Strenzke MTG AG A. Wussler Proton AG 30 January 2024 Post-Quantum Cryptography in OpenPGP draft-ietf-openpgp-pqc-00 Abstract This document defines a post-quantum public-key algorithm extension for the OpenPGP protocol. Given the generally assumed threat of a cryptographically relevant quantum computer, this extension provides a basis for long-term secure OpenPGP signatures and ciphertexts. Specifically, it defines composite public-key encryption based on ML- KEM (formerly CRYSTALS-Kyber), composite public-key signatures based on ML-DSA (formerly CRYSTALS-Dilithium), both in combination with elliptic curve cryptography, and SLH-DSA (formerly SPHINCS+) as a standalone public key signature scheme. About This Document This note is to be removed before publishing as an RFC. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-ietf-openpgp-pqc/. Discussion of this document takes place on the WG Working Group mailing list (mailto:openpgp@ietf.org), which is archived at https://mailarchive.ietf.org/arch/browse/openpgp/. Subscribe at https://www.ietf.org/mailman/listinfo/openpgp/. Source for this draft and an issue tracker can be found at https://github.com/openpgp-pqc/draft-openpgp-pqc. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Kousidis, et al. Expires 2 August 2024 [Page 1] Internet-Draft PQC in OpenPGP January 2024 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 2 August 2024. 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 . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. Conventions used in this Document . . . . . . . . . . . . 5 1.1.1. Terminology for Multi-Algorithm Schemes . . . . . . . 5 1.2. Post-Quantum Cryptography . . . . . . . . . . . . . . . . 5 1.2.1. ML-KEM . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.2. ML-DSA . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.3. SLH-DSA . . . . . . . . . . . . . . . . . . . . . . . 6 1.3. Elliptic Curve Cryptography . . . . . . . . . . . . . . . 6 1.3.1. Curve25519 and Curve448 . . . . . . . . . . . . . . . 6 1.3.2. Generic Prime Curves . . . . . . . . . . . . . . . . 7 1.4. Standalone and Multi-Algorithm Schemes . . . . . . . . . 7 1.4.1. Standalone and Composite Multi-Algorithm Schemes . . 7 1.4.2. Non-Composite Algorithm Combinations . . . . . . . . 7 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1. Elliptic curves . . . . . . . . . . . . . . . . . . . . . 8 2.1.1. SEC1 EC Point Wire Format . . . . . . . . . . . . . . 8 2.1.2. Measures to Ensure Secure Implementations . . . . . . 8 3. Supported Public Key Algorithms . . . . . . . . . . . . . . . 9 3.1. Algorithm Specifications . . . . . . . . . . . . . . . . 9 3.2. Parameter Specification . . . . . . . . . . . . . . . . . 10 Kousidis, et al. Expires 2 August 2024 [Page 2] Internet-Draft PQC in OpenPGP January 2024 3.2.1. SLH-DSA-SHA2 . . . . . . . . . . . . . . . . . . . . 10 3.2.2. SLH-DSA-SHAKE . . . . . . . . . . . . . . . . . . . . 11 4. Algorithm Combinations . . . . . . . . . . . . . . . . . . . 12 4.1. Composite KEMs . . . . . . . . . . . . . . . . . . . . . 12 4.2. Parallel Public-Key Encryption . . . . . . . . . . . . . 12 4.3. Composite Signatures . . . . . . . . . . . . . . . . . . 12 4.4. Multiple Signatures . . . . . . . . . . . . . . . . . . . 12 5. Composite KEM schemes . . . . . . . . . . . . . . . . . . . . 13 5.1. Building Blocks . . . . . . . . . . . . . . . . . . . . . 13 5.1.1. ECC-Based KEMs . . . . . . . . . . . . . . . . . . . 13 5.1.2. ML-KEM . . . . . . . . . . . . . . . . . . . . . . . 17 5.2. Composite Encryption Schemes with ML-KEM . . . . . . . . 19 5.2.1. Fixed information . . . . . . . . . . . . . . . . . . 20 5.2.2. Key combiner . . . . . . . . . . . . . . . . . . . . 20 5.2.3. Key generation procedure . . . . . . . . . . . . . . 21 5.2.4. Encryption procedure . . . . . . . . . . . . . . . . 21 5.2.5. Decryption procedure . . . . . . . . . . . . . . . . 22 5.3. Packet specifications . . . . . . . . . . . . . . . . . . 23 5.3.1. Public-Key Encrypted Session Key Packets (Tag 1) . . 23 5.3.2. Key Material Packets . . . . . . . . . . . . . . . . 23 6. Composite Signature Schemes . . . . . . . . . . . . . . . . . 24 6.1. Building blocks . . . . . . . . . . . . . . . . . . . . . 24 6.1.1. EdDSA-Based signatures . . . . . . . . . . . . . . . 24 6.1.2. ECDSA-Based signatures . . . . . . . . . . . . . . . 24 6.1.3. ML-DSA signatures . . . . . . . . . . . . . . . . . . 25 6.2. Composite Signature Schemes with ML-DSA . . . . . . . . . 26 6.2.1. Signature data digest . . . . . . . . . . . . . . . . 26 6.2.2. Key generation procedure . . . . . . . . . . . . . . 26 6.2.3. Signature Generation . . . . . . . . . . . . . . . . 27 6.2.4. Signature Verification . . . . . . . . . . . . . . . 27 6.3. Packet Specifications . . . . . . . . . . . . . . . . . . 28 6.3.1. Signature Packet (Tag 2) . . . . . . . . . . . . . . 28 6.3.2. Key Material Packets . . . . . . . . . . . . . . . . 28 7. SLH-DSA . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 7.1. The SLH-DSA Algorithms . . . . . . . . . . . . . . . . . 29 7.1.1. Signature Data Digest . . . . . . . . . . . . . . . . 30 7.1.2. Key generation . . . . . . . . . . . . . . . . . . . 31 7.1.3. Signature Generation . . . . . . . . . . . . . . . . 31 7.1.4. Signature Verification . . . . . . . . . . . . . . . 31 7.2. Packet specifications . . . . . . . . . . . . . . . . . . 31 7.2.1. Signature Packet (Tag 2) . . . . . . . . . . . . . . 31 7.2.2. Key Material Packets . . . . . . . . . . . . . . . . 31 8. Migration Considerations . . . . . . . . . . . . . . . . . . 32 8.1. Key preference . . . . . . . . . . . . . . . . . . . . . 32 8.2. Key generation strategies . . . . . . . . . . . . . . . . 33 9. Security Considerations . . . . . . . . . . . . . . . . . . . 33 9.1. Hashing in ECC-KEM . . . . . . . . . . . . . . . . . . . 33 9.2. Key combiner . . . . . . . . . . . . . . . . . . . . . . 33 Kousidis, et al. Expires 2 August 2024 [Page 3] Internet-Draft PQC in OpenPGP January 2024 9.3. Domain separation and binding . . . . . . . . . . . . . . 34 9.4. SLH-DSA Message Randomizer . . . . . . . . . . . . . . . 36 9.5. Binding hashes in signatures with signature algorithms . 36 10. Additional considerations . . . . . . . . . . . . . . . . . . 36 10.1. Performance Considerations for SLH-DSA . . . . . . . . . 36 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 37 12. Changelog . . . . . . . . . . . . . . . . . . . . . . . . . . 37 12.1. draft-wussler-openpgp-pqc-01 . . . . . . . . . . . . . . 37 12.2. draft-wussler-openpgp-pqc-02 . . . . . . . . . . . . . . 38 12.3. draft-wussler-openpgp-pqc-03 . . . . . . . . . . . . . . 38 12.4. draft-wussler-openpgp-pqc-04 . . . . . . . . . . . . . . 38 12.5. draft-ietf-openpgp-pqc-00 . . . . . . . . . . . . . . . 38 13. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 38 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 38 14.1. Normative References . . . . . . . . . . . . . . . . . . 38 14.2. Informative References . . . . . . . . . . . . . . . . . 39 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 41 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 41 1. Introduction The OpenPGP protocol supports various traditional public-key algorithms based on the factoring or discrete logarithm problem. As the security of algorithms based on these mathematical problems is endangered by the advent of quantum computers, there is a need to extend OpenPGP by algorithms that remain secure in the presence of quantum computers. Such cryptographic algorithms are referred to as post-quantum cryptography. The algorithms defined in this extension were chosen for standardization by the National Institute of Standards and Technology (NIST) in mid 2022 [NISTIR-8413] as the result of the NIST Post-Quantum Cryptography Standardization process initiated in 2016 [NIST-PQC]. Namely, these are ML-KEM (formerly CRYSTALS-Kyber) as a Key Encapsulation Mechanism (KEM), a KEM being a modern building block for public-key encryption, and ML-DSA (formerly CRYSTALS- Dilithium) as well as SLH-DSA (formerly SPHINCS+) as signature schemes. For the two ML-* schemes, this document follows the conservative strategy to deploy post-quantum in combination with traditional schemes such that the security is retained even if all schemes but one in the combination are broken. In contrast, the stateless hash- based signature scheme SLH-DSA is considered to be sufficiently well understood with respect to its security assumptions in order to be used standalone. To this end, this document specifies the following new set: SLH-DSA standalone and the two ML-* as composite with ECC- based KEM and digital signature schemes. Here, the term "composite" Kousidis, et al. Expires 2 August 2024 [Page 4] Internet-Draft PQC in OpenPGP January 2024 indicates that any data structure or algorithm pertaining to the combination of the two components appears as single data structure or algorithm from the protocol perspective. The document specifies the conventions for interoperability between compliant OpenPGP implementations that make use of this extension and the newly defined algorithms or algorithm combinations. 1.1. Conventions used in this Document 1.1.1. Terminology for Multi-Algorithm Schemes The terminology in this document is oriented towards the definitions in [draft-driscoll-pqt-hybrid-terminology]. Specifically, the terms "multi-algorithm", "composite" and "non-composite" are used in correspondence with the definitions therein. The abbreviation "PQ" is used for post-quantum schemes. To denote the combination of post- quantum and traditional schemes, the abbreviation "PQ/T" is used. The short form "PQ(/T)" stands for PQ or PQ/T. 1.2. Post-Quantum Cryptography This section describes the individual post-quantum cryptographic schemes. All schemes listed here are believed to provide security in the presence of a cryptographically relevant quantum computer. However, the mathematical problems on which the two ML-* schemes and SLH-DSA are based, are fundamentally different, and accordingly the level of trust commonly placed in them as well as their performance characteristics vary. [Note to the reader: This specification refers to the NIST PQC draft standards FIPS 203, FIPS 204, and FIPS 205 as if they were a final specification. This is a temporary solution until the final versions of these documents are available. The goal is to provide a sufficiently precise specification of the algorithms already at the draft stage of this specification, so that it is possible for implementers to create interoperable implementations. Furthermore, we want to point out that, depending on possible future changes to the draft standards by NIST, this specification may be updated as soon as corresponding information becomes available.] Kousidis, et al. Expires 2 August 2024 [Page 5] Internet-Draft PQC in OpenPGP January 2024 1.2.1. ML-KEM ML-KEM [FIPS-203] is based on the hardness of solving the learning- with-errors problem in module lattices (MLWE). The scheme is believed to provide security against cryptanalytic attacks by classical as well as quantum computers. This specification defines ML-KEM only in composite combination with ECC-based encryption schemes in order to provide a pre-quantum security fallback. 1.2.2. ML-DSA ML-DSA [FIPS-204] is a signature scheme that, like ML-KEM, is based on the hardness of solving the Learning With Errors problem and a variant of the Short Integer Solution problem in module lattices (MLWE and SelfTargetMSIS). Accordingly, this specification only defines ML-DSA in composite combination with ECC-based signature schemes. 1.2.3. SLH-DSA SLH-DSA [FIPS-205] is a stateless hash-based signature scheme. Its security relies on the hardness of finding preimages for cryptographic hash functions. This feature is generally considered to be a high security guarantee. Therefore, this specification defines SLH-DSA as a standalone signature scheme. In deployments the performance characteristics of SLH-DSA should be taken into account. We refer to Section 10.1 for a discussion of the performance characteristics of this scheme. 1.3. Elliptic Curve Cryptography The ECC-based encryption is defined here as a KEM. This is in contrast to [I-D.ietf-openpgp-crypto-refresh] where the ECC-based encryption is defined as a public-key encryption scheme. All elliptic curves for the use in the composite combinations are taken from [I-D.ietf-openpgp-crypto-refresh]. However, as explained in the following, in the case of Curve25519 encoding changes are applied to the new composite schemes. 1.3.1. Curve25519 and Curve448 Curve25519 and Curve448 are defined in [RFC7748] for use in a Diffie- Hellman key agreement scheme and defined in [RFC8032] for use in a digital signature scheme. For Curve25519 this specification adapts the encoding of objects as defined in [RFC7748] in contrast to [I-D.ietf-openpgp-crypto-refresh]. Kousidis, et al. Expires 2 August 2024 [Page 6] Internet-Draft PQC in OpenPGP January 2024 1.3.2. Generic Prime Curves For interoperability this extension offers CRYSTALS-* in composite combinations with the NIST curves P-256, P-384 defined in [SP800-186] and the Brainpool curves brainpoolP256r1, brainpoolP384r1 defined in [RFC5639]. 1.4. Standalone and Multi-Algorithm Schemes This section provides a categorization of the new algorithms and their combinations. 1.4.1. Standalone and Composite Multi-Algorithm Schemes This specification introduces new cryptographic schemes, which can be categorized as follows: * PQ/T multi-algorithm public-key encryption, namely a composite combination of ML-KEM with an ECC-based KEM, * PQ/T multi-algorithm digital signature, namely composite combinations of ML-DSA with ECC-based signature schemes, * PQ digital signature, namely SLH-DSA as a standalone cryptographic algorithm. For each of the composite schemes, this specification mandates that the recipient has to successfully perform the cryptographic algorithms for each of the component schemes used in a cryptrographic message, in order for the message to be deciphered and considered as valid. This means that all component signatures must be verified successfully in order to achieve a successful verification of the composite signature. In the case of the composite public-key decryption, each of the component KEM decapsulation operations must succeed. 1.4.2. Non-Composite Algorithm Combinations As the OpenPGP protocol [I-D.ietf-openpgp-crypto-refresh] allows for multiple signatures to be applied to a single message, it is also possible to realize non-composite combinations of signatures. Furthermore, multiple OpenPGP signatures may be combined on the application layer. These latter two cases realize non-composite combinations of signatures. Section 4.4 specifies how implementations should handle the verification of such combinations of signatures. Kousidis, et al. Expires 2 August 2024 [Page 7] Internet-Draft PQC in OpenPGP January 2024 Furthermore, the OpenPGP protocol also allows for parallel encryption to different keys held by the same recipient. Accordingly, if the sender makes use of this feature and sends an encrypted message with multiple PKESK packages for different encryption keys held by the same recipient, a non-composite multi-algorithm public-key encryption is realized where the recipient has to decrypt only one of the PKESK packages in order to decrypt the message. See Section 4.2 for restrictions on parallel encryption mandated by this specification. 2. Preliminaries This section provides some preliminaries for the definitions in the subsequent sections. 2.1. Elliptic curves 2.1.1. SEC1 EC Point Wire Format Elliptic curve points of the generic prime curves are encoded using the SEC1 (uncompressed) format as the following octet string: B = 04 || X || Y where X and Y are coordinates of the elliptic curve point P = (X, Y), and each coordinate is encoded in the big-endian format and zero- padded to the adjusted underlying field size. The adjusted underlying field size is the underlying field size rounded up to the nearest 8-bit boundary, as noted in the "Field size" column in Table 6, Table 7, or Table 11. This encoding is compatible with the definition given in [SEC1]. 2.1.2. Measures to Ensure Secure Implementations In the following measures are described that ensure secure implementations according to existing best practices and standards defining the operations of Elliptic Curve Cryptography. Even though the zero point, also called the point at infinity, may occur as a result of arithmetic operations on points of an elliptic curve, it MUST NOT appear in any ECC data structure defined in this document. Furthermore, when performing the explicitly listed operations in Section 5.1.1.1, Section 5.1.1.2 or Section 5.1.1.3 it is REQUIRED to follow the specification and security advisory mandated from the respective elliptic curve specification. Kousidis, et al. Expires 2 August 2024 [Page 8] Internet-Draft PQC in OpenPGP January 2024 3. Supported Public Key Algorithms This section specifies the composite ML-KEM + ECC and ML-DSA + ECC schemes as well as the standalone SLH-DSA signature scheme. The composite schemes are fully specified via their algorithm ID. The SLH-DSA signature schemes are fully specified by their algorithm ID and an additional parameter ID. 3.1. Algorithm Specifications For encryption, the following composite KEM schemes are specified: +====+===============================+=============+=============+ | ID | Algorithm | Requirement | Definition | +====+===============================+=============+=============+ | 29 | ML-KEM-768 + X25519 | MUST | Section 5.2 | +----+-------------------------------+-------------+-------------+ | 30 | ML-KEM-1024 + X448 | SHOULD | Section 5.2 | +----+-------------------------------+-------------+-------------+ | 31 | ML-KEM-768 + ECDH-NIST-P-256 | MAY | Section 5.2 | +----+-------------------------------+-------------+-------------+ | 32 | ML-KEM-1024 + ECDH-NIST-P-384 | MAY | Section 5.2 | +----+-------------------------------+-------------+-------------+ | 33 | ML-KEM-768 + ECDH- | MAY | Section 5.2 | | | brainpoolP256r1 | | | +----+-------------------------------+-------------+-------------+ | 34 | ML-KEM-1024 + ECDH- | MAY | Section 5.2 | | | brainpoolP384r1 | | | +----+-------------------------------+-------------+-------------+ Table 1: KEM algorithm specifications For signatures, the following (composite) signature schemes are specified: Kousidis, et al. Expires 2 August 2024 [Page 9] Internet-Draft PQC in OpenPGP January 2024 +====+==============================+=============+=============+ | ID | Algorithm | Requirement | Definition | +====+==============================+=============+=============+ | 35 | ML-DSA-65 + Ed25519 | MUST | Section 6.2 | +----+------------------------------+-------------+-------------+ | 36 | ML-DSA-87 + Ed448 | SHOULD | Section 6.2 | +----+------------------------------+-------------+-------------+ | 37 | ML-DSA-65 + ECDSA-NIST-P-256 | MAY | Section 6.2 | +----+------------------------------+-------------+-------------+ | 38 | ML-DSA-87 + ECDSA-NIST-P-384 | MAY | Section 6.2 | +----+------------------------------+-------------+-------------+ | 39 | ML-DSA-65 + ECDSA- | MAY | Section 6.2 | | | brainpoolP256r1 | | | +----+------------------------------+-------------+-------------+ | 40 | ML-DSA-87 + ECDSA- | MAY | Section 6.2 | | | brainpoolP384r1 | | | +----+------------------------------+-------------+-------------+ | 41 | SLH-DSA-SHA2 | SHOULD | Section 7.1 | +----+------------------------------+-------------+-------------+ | 42 | SLH-DSA-SHAKE | MAY | Section 7.1 | +----+------------------------------+-------------+-------------+ Table 2: Signature algorithm specifications 3.2. Parameter Specification 3.2.1. SLH-DSA-SHA2 For the SLH-DSA-SHA2 signature algorithm from Table 2, the following parameters are specified: Kousidis, et al. Expires 2 August 2024 [Page 10] Internet-Draft PQC in OpenPGP January 2024 +==============+===================+ | Parameter ID | Parameter | +==============+===================+ | 1 | SLH-DSA-SHA2-128s | +--------------+-------------------+ | 2 | SLH-DSA-SHA2-128f | +--------------+-------------------+ | 3 | SLH-DSA-SHA2-192s | +--------------+-------------------+ | 4 | SLH-DSA-SHA2-192f | +--------------+-------------------+ | 5 | SLH-DSA-SHA2-256s | +--------------+-------------------+ | 6 | SLH-DSA-SHA2-256f | +--------------+-------------------+ Table 3: SLH-DSA-SHA2 security parameters All security parameters inherit the requirement of SLH-DSA-SHA2 from Table 2. That is, implementations SHOULD implement the parameters specified in Table 3. The values 0x00 and 0xFF are reserved for future extensions. 3.2.2. SLH-DSA-SHAKE For the SLH-DSA-SHAKE signature algorithm from Table 2, the following parameters are specified: +==============+====================+ | Parameter ID | Parameter | +==============+====================+ | 1 | SLH-DSA-SHAKE-128s | +--------------+--------------------+ | 2 | SLH-DSA-SHAKE-128f | +--------------+--------------------+ | 3 | SLH-DSA-SHAKE-192s | +--------------+--------------------+ | 4 | SLH-DSA-SHAKE-192f | +--------------+--------------------+ | 5 | SLH-DSA-SHAKE-256s | +--------------+--------------------+ | 6 | SLH-DSA-SHAKE-256f | +--------------+--------------------+ Table 4: SLH-DSA-SHAKE security parameters Kousidis, et al. Expires 2 August 2024 [Page 11] Internet-Draft PQC in OpenPGP January 2024 All security parameters inherit the requirement of SLH-DSA-SHAKE from Table 2. That is, implementations MAY implement the parameters specified in Table 4. The values 0x00 and 0xFF are reserved for future extensions. 4. Algorithm Combinations 4.1. Composite KEMs The ML-KEM + ECC public-key encryption involves both the ML-KEM and an ECC-based KEM in an a priori non-separable manner. This is achieved via KEM combination, i.e. both key encapsulations/ decapsulations are performed in parallel, and the resulting key shares are fed into a key combiner to produce a single shared secret for message encryption. 4.2. Parallel Public-Key Encryption As explained in Section 1.4.2, the OpenPGP protocol inherently supports parallel encryption to different keys of the same recipient. Implementations MUST NOT encrypt a message with a purely traditional public-key encryption key of a recipient if it is encrypted with a PQ/T key of the same recipient. 4.3. Composite Signatures The ML-DSA + ECC signature consists of independent ML-DSA and ECC signatures, and an implementation MUST successfully validate both signatures to state that the ML-DSA + ECC signature is valid. 4.4. Multiple Signatures The OpenPGP message format allows multiple signatures of a message, i.e. the attachment of multiple signature packets. An implementation MAY sign a message with a traditional key and a PQ(/T) key from the same sender. This ensures backwards compatibility due to [I-D.ietf-openpgp-crypto-refresh] Section 5.2.5, since a legacy implementation without PQ(/T) support can fall back on the traditional signature. Newer implementations with PQ(/T) support MAY ignore the traditional signature(s) during validation. Implementations SHOULD consider the message correctly signed if at least one of the non-ignored signatures validates successfully. Kousidis, et al. Expires 2 August 2024 [Page 12] Internet-Draft PQC in OpenPGP January 2024 [Note to the reader: The last requirement, that one valid signature is sufficient to identify a message as correctly signed, is an interpretation of [I-D.ietf-openpgp-crypto-refresh] Section 5.2.5.] 5. Composite KEM schemes 5.1. Building Blocks 5.1.1. ECC-Based KEMs In this section we define the encryption, decryption, and data formats for the ECDH component of the composite algorithms. Table 5, Table 6, and Table 7 describe the ECC-KEM parameters and artifact lengths. The artefacts in Table 5 follow the encodings described in [RFC7748]. +========================+===================+==================+ | | X25519 | X448 | +========================+===================+==================+ | Algorithm ID reference | 29 | 30 | +------------------------+-------------------+------------------+ | Field size | 32 octets | 56 octets | +------------------------+-------------------+------------------+ | ECC-KEM | x25519Kem | x448Kem (Section | | | (Section 5.1.1.1) | 5.1.1.2) | +------------------------+-------------------+------------------+ | ECDH public key | 32 octets | 56 octets | | | [RFC7748] | [RFC7748] | +------------------------+-------------------+------------------+ | ECDH secret key | 32 octets | 56 octets | | | [RFC7748] | [RFC7748] | +------------------------+-------------------+------------------+ | ECDH ephemeral | 32 octets | 56 octets | | | [RFC7748] | [RFC7748] | +------------------------+-------------------+------------------+ | ECDH share | 32 octets | 56 octets | | | [RFC7748] | [RFC7748] | +------------------------+-------------------+------------------+ | Key share | 32 octets | 64 octets | +------------------------+-------------------+------------------+ | Hash | SHA3-256 | SHA3-512 | +------------------------+-------------------+------------------+ Table 5: Montgomery curves parameters and artifact lengths Kousidis, et al. Expires 2 August 2024 [Page 13] Internet-Draft PQC in OpenPGP January 2024 +==============+===========================+==================+ | | NIST P-256 | NIST P-384 | +==============+===========================+==================+ | Algorithm ID | 31 | 32 | | reference | | | +--------------+---------------------------+------------------+ | Field size | 32 octets | 48 octets | +--------------+---------------------------+------------------+ | ECC-KEM | ecdhKem (Section 5.1.1.3) | ecdhKem (Section | | | | 5.1.1.3) | +--------------+---------------------------+------------------+ | ECDH public | 65 octets of SEC1-encoded | 97 octets of | | key | public point | SEC1-encoded | | | | public point | +--------------+---------------------------+------------------+ | ECDH secret | 32 octets big-endian | 48 octets big- | | key | encoded secret scalar | endian encoded | | | | secret scalar | +--------------+---------------------------+------------------+ | ECDH | 65 octets of SEC1-encoded | 97 octets of | | ephemeral | ephemeral point | SEC1-encoded | | | | ephemeral point | +--------------+---------------------------+------------------+ | ECDH share | 65 octets of SEC1-encoded | 97 octets of | | | shared point | SEC1-encoded | | | | shared point | +--------------+---------------------------+------------------+ | Key share | 32 octets | 64 octets | +--------------+---------------------------+------------------+ | Hash | SHA3-256 | SHA3-512 | +--------------+---------------------------+------------------+ Table 6: NIST curves parameters and artifact lengths Kousidis, et al. Expires 2 August 2024 [Page 14] Internet-Draft PQC in OpenPGP January 2024 +==============+===========================+==================+ | | brainpoolP256r1 | brainpoolP384r1 | +==============+===========================+==================+ | Algorithm ID | 33 | 34 | | reference | | | +--------------+---------------------------+------------------+ | Field size | 32 octets | 48 octets | +--------------+---------------------------+------------------+ | ECC-KEM | ecdhKem (Section 5.1.1.3) | ecdhKem (Section | | | | 5.1.1.3) | +--------------+---------------------------+------------------+ | ECDH public | 65 octets of SEC1-encoded | 97 octets of | | key | public point | SEC1-encoded | | | | public point | +--------------+---------------------------+------------------+ | ECDH secret | 32 octets big-endian | 48 octets big- | | key | encoded secret scalar | endian encoded | | | | secret scalar | +--------------+---------------------------+------------------+ | ECDH | 65 octets of SEC1-encoded | 97 octets of | | ephemeral | ephemeral point | SEC1-encoded | | | | ephemeral point | +--------------+---------------------------+------------------+ | ECDH share | 65 octets of SEC1-encoded | 97 octets of | | | shared point | SEC1-encoded | | | | shared point | +--------------+---------------------------+------------------+ | Key share | 32 octets | 64 octets | +--------------+---------------------------+------------------+ | Hash | SHA3-256 | SHA3-512 | +--------------+---------------------------+------------------+ Table 7: Brainpool curves parameters and artifact lengths The SEC1 format for point encoding is defined in Section 2.1.1. The various procedures to perform the operations of an ECC-based KEM are defined in the following subsections. Specifically, each of these subsections defines the instances of the following operations: (eccCipherText, eccKeyShare) <- ECC-KEM.Encaps(eccPublicKey) and (eccKeyShare) <- ECC-KEM.Decaps(eccSecretKey, eccCipherText) To instantiate ECC-KEM, one must select a parameter set from Table 5, Table 6, or Table 7. Kousidis, et al. Expires 2 August 2024 [Page 15] Internet-Draft PQC in OpenPGP January 2024 5.1.1.1. X25519-KEM The encapsulation and decapsulation operations of x25519kem are described using the function X25519() and encodings defined in [RFC7748]. The eccSecretKey is denoted as r, the eccPublicKey as R, they are subject to the equation R = X25519(r, U(P)). Here, U(P) denotes the u-coordinate of the base point of Curve25519. The operation x25519Kem.Encaps() is defined as follows: 1. Generate an ephemeral key pair {v, V} via V = X25519(v,U(P)) where v is a random scalar 2. Compute the shared coordinate X = X25519(v, R) where R is the public key eccPublicKey 3. Set the output eccCipherText to V 4. Set the output eccKeyShare to SHA3-256(X || eccCipherText || eccPublicKey) The operation x25519Kem.Decaps() is defined as follows: 1. Compute the shared coordinate X = X25519(r, V), where r is the eccSecretKey and V is the eccCipherText 2. Set the output eccKeyShare to SHA3-256(X || eccCipherText || eccPublicKey) 5.1.1.2. X448-KEM The encapsulation and decapsulation operations of x448kem are described using the function X448() and encodings defined in [RFC7748]. The eccSecretKey is denoted as r, the eccPublicKey as R, they are subject to the equation R = X25519(r, U(P)). Here, U(P) denotes the u-coordinate of the base point of Curve448. The operation x448.Encaps() is defined as follows: 1. Generate an ephemeral key pair {v, V} via V = X448(v,U(P)) where v is a random scalar 2. Compute the shared coordinate X = X448(v, R) where R is the public key eccPublicKey 3. Set the output eccCipherText to V Kousidis, et al. Expires 2 August 2024 [Page 16] Internet-Draft PQC in OpenPGP January 2024 4. Set the output eccKeyShare to SHA3-512(X || eccCipherText || eccPublicKey) The operation x448Kem.Decaps() is defined as follows: 1. Compute the shared coordinate X = X448(r, V), where r is the eccSecretKey and V is the eccCipherText 2. Set the output eccKeyShare to SHA3-512(X || eccCipherText || eccPublicKey) 5.1.1.3. ECDH-KEM The operation ecdhKem.Encaps() is defined as follows: 1. Generate an ephemeral key pair {v, V=vG} as defined in [SP800-186] or [RFC5639] where v is a random scalar 2. Compute the shared point S = vR, where R is the component public key eccPublicKey, according to [SP800-186] or [RFC5639] 3. Extract the X coordinate from the SEC1 encoded point S = 04 || X || Y as defined in section Section 2.1.1 4. Set the output eccCipherText to the SEC1 encoding of V 5. Set the output eccKeyShare to Hash(X || eccCipherText || eccPublicKey), with Hash chosen according to Table 6 or Table 7 The operation ecdhKem.Decaps() is defined as follows: 1. Compute the shared Point S as rV, where r is the eccSecretKey and V is the eccCipherText, according to [SP800-186] or [RFC5639] 2. Extract the X coordinate from the SEC1 encoded point S = 04 || X || Y as defined in section Section 2.1.1 3. Set the output eccKeyShare to Hash(X || eccCipherText || eccPublicKey), with Hash chosen according to Table 6 or Table 7 5.1.2. ML-KEM ML-KEM features the following operations: (mlkemCipherText, mlkemKeyShare) <- ML-KEM.Encaps(mlkemPublicKey) and Kousidis, et al. Expires 2 August 2024 [Page 17] Internet-Draft PQC in OpenPGP January 2024 (mlkemKeyShare) <- ML-KEM.Decaps(mlkemCipherText, mlkemSecretKey) The above are the operations ML-KEM.Encaps and ML-KEM.Decaps defined in [FIPS-203]. Note that mlkemPublicKey is the encapsulation and mlkemSecretKey is the decapsulation key. ML-KEM has the parameterization with the corresponding artifact lengths in octets as given in Table 8. All artifacts are encoded as defined in [FIPS-203]. +==============+=============+========+========+============+=======+ | Algorithm | ML-KEM | Public | Secret | Ciphertext | Key | | ID | | key | key | | share | | reference | | | | | | +==============+=============+========+========+============+=======+ | 29, 31, | ML-KEM-768 | 1184 | 2400 | 1088 | 32 | | 33 | | | | | | +--------------+-------------+--------+--------+------------+-------+ | 30, 32, | ML-KEM-1024 | 1568 | 3168 | 1568 | 32 | | 34 | | | | | | +--------------+-------------+--------+--------+------------+-------+ Table 8: ML-KEM parameters artifact lengths in octets To instantiate ML-KEM, one must select a parameter set from the column "ML-KEM" of Table 8. The procedure to perform ML-KEM.Encaps() is as follows: 1. Extract the encapsulation key mlkemPublicKey that is part of the recipient's composite public key 2. Invoke (mlkemCipherText, mlkemKeyShare) <- ML- KEM.Encaps(mlkemPublicKey) 3. Set mlkemCipherText as the ML-KEM ciphertext 4. Set mlkemKeyShare as the ML-KEM symmetric key share The procedure to perform ML-KEM.Decaps() is as follows: 1. Invoke mlkemKeyShare <- ML-KEM.Decaps(mlkemCipherText, mlkemSecretKey) 2. Set mlkemKeyShare as the ML-KEM symmetric key share Kousidis, et al. Expires 2 August 2024 [Page 18] Internet-Draft PQC in OpenPGP January 2024 5.2. Composite Encryption Schemes with ML-KEM Table 1 specifies the following ML-KEM + ECC composite public-key encryption schemes: +==============+=============+===========+=================+ | Algorithm ID | ML-KEM | ECC-KEM | ECC-KEM curve | | reference | | | | +==============+=============+===========+=================+ | 29 | ML-KEM-768 | x25519Kem | Curve25519 | +--------------+-------------+-----------+-----------------+ | 30 | ML-KEM-1024 | x448Kem | Curve448 | +--------------+-------------+-----------+-----------------+ | 31 | ML-KEM-768 | ecdhKem | NIST P-256 | +--------------+-------------+-----------+-----------------+ | 32 | ML-KEM-1024 | ecdhKem | NIST P-384 | +--------------+-------------+-----------+-----------------+ | 33 | ML-KEM-768 | ecdhKem | brainpoolP256r1 | +--------------+-------------+-----------+-----------------+ | 34 | ML-KEM-1024 | ecdhKem | brainpoolP384r1 | +--------------+-------------+-----------+-----------------+ Table 9: ML-KEM + ECC composite schemes The ML-KEM + ECC composite public-key encryption schemes are built according to the following principal design: * The ML-KEM encapsulation algorithm is invoked to create a ML-KEM ciphertext together with a ML-KEM symmetric key share. * The encapsulation algorithm of an ECC-based KEM, namely one out of X25519-KEM, X448-KEM, or ECDH-KEM is invoked to create an ECC ciphertext together with an ECC symmetric key share. * A Key-Encryption-Key (KEK) is computed as the output of a key combiner that receives as input both of the above created symmetric key shares and the protocol binding information. * The session key for content encryption is then wrapped as described in [RFC3394] using AES-256 as algorithm and the KEK as key. * The PKESK package's algorithm-specific parts are made up of the ML-KEM ciphertext, the ECC ciphertext, and the wrapped session key. Kousidis, et al. Expires 2 August 2024 [Page 19] Internet-Draft PQC in OpenPGP January 2024 5.2.1. Fixed information For the composite KEM schemes defined in Table 1 the following procedure, justified in Section 9.3, MUST be used to derive a string to use as binding between the KEK and the communication parties. // Input: // algID - the algorithm ID encoded as octet fixedInfo = algID 5.2.2. Key combiner For the composite KEM schemes defined in Table 1 the following procedure MUST be used to compute the KEK that wraps a session key. The construction is a one-step key derivation function compliant to [SP800-56C] Section 4, based on KMAC256 [SP800-185]. It is given by the following algorithm. // multiKeyCombine(eccKeyShare, eccCipherText, // mlkemKeyShare, mlkemCipherText, // fixedInfo, oBits) // // Input: // eccKeyShare - the ECC key share encoded as an octet string // eccCipherText - the ECC ciphertext encoded as an octet string // mlkemKeyShare - the ML-KEM key share encoded as an octet string // mlkemCipherText - the ML-KEM ciphertext encoded as an octet string // fixedInfo - the fixed information octet string // oBits - the size of the output keying material in bits // // Constants: // domSeparation - the UTF-8 encoding of the string // "OpenPGPCompositeKeyDerivationFunction" // counter - the fixed 4 byte value 0x00000001 // customizationString - the UTF-8 encoding of the string "KDF" eccData = eccKeyShare || eccCipherText mlkemData = mlkemKeyShare || mlkemCipherText encData = counter || eccData || mlkemData || fixedInfo MB = KMAC256(domSeparation, encData, oBits, customizationString) Note that the values eccKeyShare defined in Section 5.1.1 and mlkemKeyShare defined in Section 5.1.2 already use the relative ciphertext in the derivation. The ciphertext is by design included again in the key combiner to provide a robust security proof. Kousidis, et al. Expires 2 August 2024 [Page 20] Internet-Draft PQC in OpenPGP January 2024 The value of domSeparation is the UTF-8 encoding of the string "OpenPGPCompositeKeyDerivationFunction" and MUST be the following octet sequence: domSeparation := 4F 70 65 6E 50 47 50 43 6F 6D 70 6F 73 69 74 65 4B 65 79 44 65 72 69 76 61 74 69 6F 6E 46 75 6E 63 74 69 6F 6E The value of counter MUST be set to the following octet sequence: counter := 00 00 00 01 The value of fixedInfo MUST be set according to Section 5.2.1. The value of customizationString is the UTF-8 encoding of the string "KDF" and MUST be set to the following octet sequence: customizationString := 4B 44 46 5.2.3. Key generation procedure The implementation MUST independently generate the ML-KEM and the ECC component keys. ML-KEM key generation follows the specification [FIPS-203] and the artifacts are encoded as fixed-length octet strings as defined in Section 5.1.2. For ECC this is done following the relative specification in [RFC7748], [SP800-186], or [RFC5639], and encoding the outputs as fixed-length octet strings in the format specified in Table 5, Table 6, or Table 7. 5.2.4. Encryption procedure The procedure to perform public-key encryption with a ML-KEM + ECC composite scheme is as follows: 1. Take the recipient's authenticated public-key packet pkComposite and sessionKey as input 2. Parse the algorithm ID from pkComposite 3. Extract the eccPublicKey and mlkemPublicKey component from the algorithm specific data encoded in pkComposite with the format specified in Section 5.3.2. 4. Instantiate the ECC-KEM and the ML-KEM depending on the algorithm ID according to Table 9 5. Compute (eccCipherText, eccKeyShare) := ECC- KEM.Encaps(eccPublicKey) Kousidis, et al. Expires 2 August 2024 [Page 21] Internet-Draft PQC in OpenPGP January 2024 6. Compute (mlkemCipherText, mlkemKeyShare) := ML- KEM.Encaps(mlkemPublicKey) 7. Compute fixedInfo as specified in Section 5.2.1 8. Compute KEK := multiKeyCombine(eccKeyShare, eccCipherText, mlkemKeyShare, mlkemCipherText, fixedInfo, oBits=256) as defined in Section 5.2.2 9. Compute C := AESKeyWrap(KEK, sessionKey) with AES-256 as per [RFC3394] that includes a 64 bit integrity check 10. Output eccCipherText || mlkemCipherText || len(C) || C 5.2.5. Decryption procedure The procedure to perform public-key decryption with a ML-KEM + ECC composite scheme is as follows: 1. Take the matching PKESK and own secret key packet as input 2. From the PKESK extract the algorithm ID and the encryptedKey 3. Check that the own and the extracted algorithm ID match 4. Parse the eccSecretKey and mlkemSecretKey from the algorithm specific data of the own secret key encoded in the format specified in Section 5.3.2 5. Instantiate the ECC-KEM and the ML-KEM depending on the algorithm ID according to Table 9 6. Parse eccCipherText, mlkemCipherText, and C from encryptedKey encoded as eccCipherText || mlkemCipherText || len(C) || C as specified in Section 5.3.1 7. Compute (eccKeyShare) := ECC-KEM.Decaps(eccCipherText, eccSecretKey) 8. Compute (mlkemKeyShare) := ML-KEM.Decaps(mlkemCipherText, mlkemSecretKey) 9. Compute fixedInfo as specified in Section 5.2.1 10. Compute KEK := multiKeyCombine(eccKeyShare, eccCipherText, mlkemKeyShare, mlkemCipherText, fixedInfo, oBits=256) as defined in Section 5.2.2 Kousidis, et al. Expires 2 August 2024 [Page 22] Internet-Draft PQC in OpenPGP January 2024 11. Compute sessionKey := AESKeyUnwrap(KEK, C) with AES-256 as per [RFC3394], aborting if the 64 bit integrity check fails 12. Output sessionKey 5.3. Packet specifications 5.3.1. Public-Key Encrypted Session Key Packets (Tag 1) The algorithm-specific fields consists of: * A fixed-length octet string representing an ECC ephemeral public key in the format associated with the curve as specified in Section 5.1.1. * A fixed-length octet string of the ML-KEM ciphertext, whose length depends on the algorithm ID as specified in Table 8. * The one-octet algorithm identifier, if it is passed (in the case of a v3 PKESK packet). * A variable-length field containing the wrapped session key: - A one-octet size of the following field; - The wrapped session key represented as an octet string, i.e., the output of the encryption procedure described in Section 5.2.4. Note that unlike most public-key algorithms, in the case of a v3 PKESK packet, the symmetric algorithm identifier is not encrypted. Instead, it is prepended to the encrypted session key in plaintext. In this case, the symmetric algorithm used MUST be AES-128, AES-192 or AES-256 (algorithm ID 7, 8 or 9). 5.3.2. Key Material Packets The algorithm-specific public key is this series of values: * A fixed-length octet string representing an EC point public key, in the point format associated with the curve specified in Section 5.1.1. * A fixed-length octet string containing the ML-KEM public key, whose length depends on the algorithm ID as specified in Table 8. The algorithm-specific secret key is these two values: Kousidis, et al. Expires 2 August 2024 [Page 23] Internet-Draft PQC in OpenPGP January 2024 * A fixed-length octet string of the encoded secret scalar, whose encoding and length depend on the algorithm ID as specified in Section 5.1.1. * A fixed-length octet string containing the ML-KEM secret key, whose length depends on the algorithm ID as specified in Table 8. 6. Composite Signature Schemes 6.1. Building blocks 6.1.1. EdDSA-Based signatures To sign and verify with EdDSA the following operations are defined: (eddsaSignature) <- EdDSA.Sign(eddsaSecretKey, dataDigest) and (verified) <- EdDSA.Verify(eddsaPublicKey, eddsaSignature, dataDigest) The public and secret key, as well as the signature MUST be encoded according to [RFC8032] as fixed-length octet strings. The following table describes the EdDSA parameters and artifact lengths: +==============+=========+=======+========+========+===========+ | Algorithm ID | Curve | Field | Public | Secret | Signature | | reference | | size | key | key | | +==============+=========+=======+========+========+===========+ | 35 | Ed25519 | 32 | 32 | 32 | 64 | +--------------+---------+-------+--------+--------+-----------+ | 36 | Ed448 | 57 | 57 | 57 | 114 | +--------------+---------+-------+--------+--------+-----------+ Table 10: EdDSA parameters and artifact lengths in octets 6.1.2. ECDSA-Based signatures To sign and verify with ECDSA the following operations are defined: (ecdsaSignatureR, ecdsaSignatureS) <- ECDSA.Sign(ecdsaSecretKey, dataDigest) and (verified) <- ECDSA.Verify(ecdsaPublicKey, ecdsaSignatureR, ecdsaSignatureS, dataDigest) Kousidis, et al. Expires 2 August 2024 [Page 24] Internet-Draft PQC in OpenPGP January 2024 The public keys MUST be encoded in SEC1 format as defined in section Section 2.1.1. The secret key, as well as both values R and S of the signature MUST each be encoded as a big-endian integer in a fixed- length octet string of the specified size. The following table describes the ECDSA parameters and artifact lengths: +=========+===============+=====+======+======+=========+=========+ |Algorithm|Curve |Field|Public|Secret|Signature|Signature| | ID| |size |key |key |value R |value S | |reference| | | | | | | +=========+===============+=====+======+======+=========+=========+ | 37|NIST P-256 |32 |65 |32 |32 |32 | +---------+---------------+-----+------+------+---------+---------+ | 38|NIST P-384 |48 |97 |48 |48 |48 | +---------+---------------+-----+------+------+---------+---------+ | 39|brainpoolP256r1|32 |65 |32 |32 |32 | +---------+---------------+-----+------+------+---------+---------+ | 40|brainpoolP384r1|48 |97 |48 |48 |48 | +---------+---------------+-----+------+------+---------+---------+ Table 11: ECDSA parameters and artifact lengths in octets 6.1.3. ML-DSA signatures For ML-DSA signature generation the default hedged version of ML- DSA.Sign given in [FIPS-204] is used. That is, to sign with ML-DSA the following operation is defined: (mldsaSignature) <- ML-DSA.Sign(mldsaSecretKey, dataDigest) For ML-DSA signature verification the algorithm ML-DSA.Verify given in [FIPS-204] is used. That is, to verify with ML-DSA the following operation is defined: (verified) <- ML-DSA.Verify(mldsaPublicKey, dataDigest, mldsaSignature) ML-DSA has the parameterization with the corresponding artifact lengths in octets as given in Table 12. All artifacts are encoded as defined in [FIPS-204]. Kousidis, et al. Expires 2 August 2024 [Page 25] Internet-Draft PQC in OpenPGP January 2024 +========================+===========+========+========+===========+ | Algorithm ID reference | ML-DSA | Public | Secret | Signature | | | | key | key | value | +========================+===========+========+========+===========+ | 35, 37, 39 | ML-DSA-65 | 1952 | 4000 | 3293 | +------------------------+-----------+--------+--------+-----------+ | 36, 38, 40 | ML-DSA-87 | 2592 | 4864 | 4595 | +------------------------+-----------+--------+--------+-----------+ Table 12: ML-DSA parameters and artifact lengths in octets 6.2. Composite Signature Schemes with ML-DSA 6.2.1. Signature data digest Signature data (i.e. the data to be signed) is digested prior to signing operations, see [I-D.ietf-openpgp-crypto-refresh] Section 5.2.4. Composite ML-DSA + ECC signatures MUST use the associated hash algorithm as specified in Table 13 for the signature data digest. Signatures using other hash algorithms MUST be considered invalid. An implementation supporting a specific ML-DSA + ECC algorithm MUST also support the matching hash algorithm. +========================+===============+===============+ | Algorithm ID reference | Hash function | Hash function | | | | ID reference | +========================+===============+===============+ | 35, 37, 39 | SHA3-256 | 12 | +------------------------+---------------+---------------+ | 36, 38, 40 | SHA3-512 | 14 | +------------------------+---------------+---------------+ Table 13: Binding between ML-DSA and signature data digest 6.2.2. Key generation procedure The implementation MUST independently generate the ML-DSA and the ECC component keys. ML-DSA key generation follows the specification [FIPS-204] and the artifacts are encoded as fixed-length octet strings as defined in Section 6.1.3. For ECC this is done following the relative specification in [RFC7748], [SP800-186], or [RFC5639], and encoding the artifacts as specified in Section 6.1.1 or Section 6.1.2 as fixed-length octet strings. Kousidis, et al. Expires 2 August 2024 [Page 26] Internet-Draft PQC in OpenPGP January 2024 6.2.3. Signature Generation To sign a message M with ML-DSA + EdDSA the following sequence of operations has to be performed: 1. Generate dataDigest according to [I-D.ietf-openpgp-crypto-refresh] Section 5.2.4 2. Create the EdDSA signature over dataDigest with EdDSA.Sign() from Section 6.1.1 3. Create the ML-DSA signature over dataDigest with ML-DSA.Sign() from Section 6.1.3 4. Encode the EdDSA and ML-DSA signatures according to the packet structure given in Section 6.3.1. To sign a message M with ML-DSA + ECDSA the following sequence of operations has to be performed: 1. Generate dataDigest according to [I-D.ietf-openpgp-crypto-refresh] Section 5.2.4 2. Create the ECDSA signature over dataDigest with ECDSA.Sign() from Section 6.1.2 3. Create the ML-DSA signature over dataDigest with ML-DSA.Sign() from Section 6.1.3 4. Encode the ECDSA and ML-DSA signatures according to the packet structure given in Section 6.3.1. 6.2.4. Signature Verification To verify a ML-DSA + EdDSA signature the following sequence of operations has to be performed: 1. Verify the EdDSA signature with EdDSA.Verify() from Section 6.1.1 2. Verify the ML-DSA signature with ML-DSA.Verify() from Section 6.1.3 To verify a ML-DSA + ECDSA signature the following sequence of operations has to be performed: 1. Verify the ECDSA signature with ECDSA.Verify() from Section 6.1.2 Kousidis, et al. Expires 2 August 2024 [Page 27] Internet-Draft PQC in OpenPGP January 2024 2. Verify the ML-DSA signature with ML-DSA.Verify() from Section 6.1.3 As specified in Section 4.3 an implementation MUST validate both signatures, i.e. EdDSA/ECDSA and ML-DSA, to state that a composite ML-DSA + ECC signature is valid. 6.3. Packet Specifications 6.3.1. Signature Packet (Tag 2) The composite ML-DSA + ECC schemes MUST be used only with v6 signatures, as defined in [I-D.ietf-openpgp-crypto-refresh]. The algorithm-specific v6 signature parameters for ML-DSA + EdDSA signatures consists of: * A fixed-length octet string representing the EdDSA signature, whose length depends on the algorithm ID as specified in Table 10. * A fixed-length octet string of the ML-DSA signature value, whose length depends on the algorithm ID as specified in Table 12. The algorithm-specific v6 signature parameters for ML-DSA + ECDSA signatures consists of: * A fixed-length octet string of the big-endian encoded ECDSA value R, whose length depends on the algorithm ID as specified in Table 11. * A fixed-length octet string of the big-endian encoded ECDSA value S, whose length depends on the algorithm ID as specified in Table 11. * A fixed-length octet string of the ML-DSA signature value, whose length depends on the algorithm ID as specified in Table 12. 6.3.2. Key Material Packets The composite ML-DSA + ECC schemes MUST be used only with v6 keys, as defined in [I-D.ietf-openpgp-crypto-refresh]. The algorithm-specific public key for ML-DSA + EdDSA keys is this series of values: * A fixed-length octet string representing the EdDSA public key, whose length depends on the algorithm ID as specified in Table 10. Kousidis, et al. Expires 2 August 2024 [Page 28] Internet-Draft PQC in OpenPGP January 2024 * A fixed-length octet string containing the ML-DSA public key, whose length depends on the algorithm ID as specified in Table 12. The algorithm-specific secret key for ML-DSA + EdDSA keys is this series of values: * A fixed-length octet string representing the EdDSA secret key, whose length depends on the algorithm ID as specified in Table 10. * A fixed-length octet string containing the ML-DSA secret key, whose length depends on the algorithm ID as specified in Table 12. The algorithm-specific public key for ML-DSA + ECDSA keys is this series of values: * A fixed-length octet string representing the ECDSA public key in SEC1 format, as specified in section Section 2.1.1 and with length specified in Table 11. * A fixed-length octet string containing the ML-DSA public key, whose length depends on the algorithm ID as specified in Table 12. The algorithm-specific secret key for ML-DSA + ECDSA keys is this series of values: * A fixed-length octet string representing the ECDSA secret key as a big-endian encoded integer, whose length depends on the algorithm used as specified in Table 11. * A fixed-length octet string containing the ML-DSA secret key, whose length depends on the algorithm ID as specified in Table 12. 7. SLH-DSA 7.1. The SLH-DSA Algorithms The following table describes the SLH-DSA parameters and artifact lengths: Kousidis, et al. Expires 2 August 2024 [Page 29] Internet-Draft PQC in OpenPGP January 2024 +==============+=============+============+============+===========+ | Parameter ID | Parameter | SLH-DSA | SLH-DSA | SLH-DSA | | reference | name suffix | public key | secret key | signature | +==============+=============+============+============+===========+ | 1 | 128s | 32 | 64 | 7856 | +--------------+-------------+------------+------------+-----------+ | 2 | 128f | 32 | 64 | 17088 | +--------------+-------------+------------+------------+-----------+ | 3 | 192s | 48 | 96 | 16224 | +--------------+-------------+------------+------------+-----------+ | 4 | 192f | 48 | 96 | 35664 | +--------------+-------------+------------+------------+-----------+ | 5 | 256s | 64 | 128 | 29792 | +--------------+-------------+------------+------------+-----------+ | 6 | 256f | 64 | 128 | 49856 | +--------------+-------------+------------+------------+-----------+ Table 14: SLH-DSA parameters and artifact lengths in octets. The values equally apply to the parameter IDs of SLH-DSA-SHA2 and SLH-DSA-SHAKE. 7.1.1. Signature Data Digest Signature data (i.e. the data to be signed) is digested prior to signing operations, see [I-D.ietf-openpgp-crypto-refresh] Section 5.2.4. SLH-DSA signatures MUST use the associated hash algorithm as specified in Table 15 for the signature data digest. Signatures using other hash algorithms MUST be considered invalid. An implementation supporting a specific SLH-DSA algorithm and parameter MUST also support the matching hash algorithm. +========================+==============+==========+===============+ | Algorithm ID reference | Parameter ID | Hash | Hash function | | | reference | function | ID reference | +========================+==============+==========+===============+ | 41 | 1, 2 | SHA-256 | 8 | +------------------------+--------------+----------+---------------+ | 41 | 3, 4, 5, 6 | SHA-512 | 10 | +------------------------+--------------+----------+---------------+ | 42 | 1, 2 | SHA3-256 | 12 | +------------------------+--------------+----------+---------------+ | 42 | 3, 4, 5, 6 | SHA3-512 | 14 | +------------------------+--------------+----------+---------------+ Table 15: Binding between SLH-DSA and signature data digest Kousidis, et al. Expires 2 August 2024 [Page 30] Internet-Draft PQC in OpenPGP January 2024 7.1.2. Key generation SLH-DSA key generation is performed via the algorithm SLH-DSA.KeyGen as specified in [FIPS-205], and the artifacts are encoded as fixed- length octet strings as defined in Section 7.1. 7.1.3. Signature Generation SLH-DSA signature generation is performed via the algorithm SLH- DSA.Sign as specified in [FIPS-205]. The variable opt_rand is set to PK.seed. See also Section 9.4. An implementation MUST set the Parameter ID in the signature equal to the issuing secret key Parameter ID. 7.1.4. Signature Verification SLH-DSA signature verification is performed via the algorithm SLH- DSA.Verify as specified in [FIPS-205]. An implementation MUST check that the Parameter ID in the signature and in the key match when verifying. 7.2. Packet specifications 7.2.1. Signature Packet (Tag 2) The SLH-DSA scheme MUST be used only with v6 signatures, as defined in [I-D.ietf-openpgp-crypto-refresh] Section 5.2.3. The algorithm-specific v6 Signature parameters consists of: * A one-octet value specifying the SLH-DSA parameter ID defined in Table 3 and Table 4. The values 0x00 and 0xFF are reserved for future extensions. * A fixed-length octet string of the SLH-DSA signature value, whose length depends on the parameter ID in the format specified in Table 14. 7.2.2. Key Material Packets The SLH-DSA scheme MUST be used only with v6 keys, as defined in [I-D.ietf-openpgp-crypto-refresh]. The algorithm-specific public key is this series of values: Kousidis, et al. Expires 2 August 2024 [Page 31] Internet-Draft PQC in OpenPGP January 2024 * A one-octet value specifying the SLH-DSA parameter ID defined in Table 3 and Table 4. The values 0x00 and 0xFF are reserved for future extensions. * A fixed-length octet string containing the SLH-DSA public key, whose length depends on the parameter ID as specified in Table 14. The algorithm-specific secret key is this value: * A fixed-length octet string containing the SLH-DSA secret key, whose length depends on the parameter ID as specified in Table 11. 8. Migration Considerations The post-quantum KEM algorithms defined in Table 1 and the signature algorithms defined in Table 2 are a set of new public key algorithms that extend the algorithm selection of [I-D.ietf-openpgp-crypto-refresh]. During the transition period, the post-quantum algorithms will not be supported by all clients. Therefore various migration considerations must be taken into account, in particular backwards compatibility to existing implementations that have not yet been updated to support the post- quantum algorithms. 8.1. Key preference Implementations SHOULD prefer PQ(/T) keys when multiple options are available. For instance, if encrypting for a recipient for which both a valid PQ/T and a valid ECC certificate are available, the implementation SHOULD choose the PQ/T certificate. In case a certificate has both a PQ/T and an ECC encryption-capable valid subkey, the PQ/T subkey SHOULD be preferred. An implementation MAY sign with both a PQ(/T) and an ECC key using multiple signatures over the same data as described in Section 4.4. Signing only with PQ(/T) key material is not backwards compatible. Note that the confidentiality of a message is not post-quantum secure when encrypting to multiple recipients if at least one recipient does not support PQ/T encryption schemes. An implementation SHOULD NOT abort the encryption process in this case to allow for a smooth transition to post-quantum cryptography. Kousidis, et al. Expires 2 August 2024 [Page 32] Internet-Draft PQC in OpenPGP January 2024 8.2. Key generation strategies It is REQUIRED to generate fresh secrets when generating PQ(/T) keys. Reusing key material from existing ECC keys in PQ(/T) keys does not provide backwards compatibility, and the fingerprint will differ. An OpenPGP (v6) certificate is composed of a certification-capable primary key and one or more subkeys for signature, encryption, and authentication. Two migration strategies are recommended: 1. Generate two independent certificates, one for PQ(/T)-capable implementations, and one for legacy implementations. Implementations not understanding PQ(/T) certificates can use the legacy certificate, while PQ(/T)-capable implementations will prefer the newer certificate. This allows having an older v4 or v6 ECC certificate for compatibility and a v6 PQ(/T) certificate, at a greater complexity in key distribution. 2. Attach PQ(/T) encryption and signature subkeys to an existing v6 ECC certificate. Implementations understanding PQ(/T) will be able to parse and use the subkeys, while PQ(/T)-incapable implementations can gracefully ignore them. This simplifies key distribution, as only one certificate needs to be communicated and verified, but leaves the primary key vulnerable to quantum computer attacks. 9. Security Considerations 9.1. Hashing in ECC-KEM Our construction of the ECC-KEMs, in particular the inclusion of eccCipherText in the final hashing step in encapsulation and decapsulation that produces the eccKeyShare, is standard and known as hashed ElGamal key encapsulation, a hashed variant of ElGamal encryption. It ensures IND-CCA2 security in the random oracle model under some Diffie-Hellman intractability assumptions [CS03]. The additional inclusion of eccPublicKey follows the security advice in Section 6.1 of [RFC7748]. 9.2. Key combiner For the key combination in Section 5.2.2 this specification limits itself to the use of KMAC. The sponge construction used by KMAC was proven to be indifferentiable from a random oracle [BDPA08]. This means, that in contrast to SHA2, which uses a Merkle-Damgard construction, no HMAC-based construction is required for key combination. Except for a domain separation it is sufficient to simply process the concatenation of any number of key shares when Kousidis, et al. Expires 2 August 2024 [Page 33] Internet-Draft PQC in OpenPGP January 2024 using a sponge-based construction like KMAC. The construction using KMAC ensures a standardized domain separation. In this case, the processed message is then the concatenation of any number of key shares. More precisely, for a given capacity c the indifferentiability proof shows that assuming there are no weaknesses found in the Keccak permutation, an attacker has to make an expected number of 2^(c/2) calls to the permutation to tell KMAC from a random oracle. For a random oracle, a difference in only a single bit gives an unrelated, uniformly random output. Hence, to be able to distinguish a key K, derived from shared keys K1 and K2 (and ciphertexts C1 and C2) as K = KMAC(domainSeparation, counter || K1 || C1 || K2 || C2 || fixedInfo, outputBits, customization) from a random bit string, an adversary has to know (or correctly guess) both key shares K1 and K2, entirely. The proposed construction in Section 5.2.2 preserves IND-CCA2 of any of its ingredient KEMs, i.e. the newly formed combined KEM is IND- CCA2 secure as long as at least one of the ingredient KEMs is. Indeed, the above stated indifferentiability from a random oracle qualifies Keccak as a split-key pseudorandom function as defined in [GHP18]. That is, Keccak behaves like a random function if at least one input shared secret is picked uniformly at random. Our construction can thus be seen as an instantiation of the IND-CCA2 preserving Example 3 in Figure 1 of [GHP18], up to some reordering of input shared secrets and ciphertexts. In the random oracle setting, the reordering does not influence the arguments in [GHP18]. 9.3. Domain separation and binding The domSeparation information defined in Section 5.2.2 provides the domain separation for the key combiner construction. This ensures that the input keying material is used to generate a KEK for a specific purpose or context. The fixedInfo defined in Section 5.2.1 binds the derived KEK to the chosen algorithm and communication parties. The algorithm ID identifies univocally the algorithm, the parameters for its instantiation, and the length of all artifacts, including the derived key. Kousidis, et al. Expires 2 August 2024 [Page 34] Internet-Draft PQC in OpenPGP January 2024 This is in line with the Recommendation for ECC in section 5.5 of [SP800-56A]. Other fields included in the recommendation are not relevant for the OpenPGP protocol, since the sender is not required to have a key of their own, there are no pre-shared secrets, and all the other parameters are univocally defined by the algorithm ID. Furthermore, we do not require the recipients public key into the key combiner as the public key material is already included in the component key derivation functions. Given two KEMs which we assume to be multi-user secure, we combine their outputs using a KEM- combiner: K = H(K1, C1, K2, C2), C = (C1, C2) Our aim is to preserve multi-user security. A common approach to this is to add the public key into the key derivation for K. However, it turns out that this is not necessary here. To break security of the combined scheme in the multi-user setting, the adversary has to distinguish a set of challenge keys K__u = H(K1__u, C1__u, K2__u, C2*_u) for users u in some set from random, also given ciphertexts C*_u = (C1*_u, C2*_u). For each of these K* it holds that if the adversary never makes a query H(K1*_u, C1*_u, K2*_u, C2*_u) they have a zero advantage over guessing. The only multi-user advantage that the adversary could gain therefore consists of queries to H that are meaningful for two different users u1 != u2 and their associated public keys. This is only the case if (c1*_u1, c2*_u1) = (c1*_u2, c2*_u2) as the ciphertext values decide for which challenge the query is meaningful. This means that a ciphertext collision is needed between challenges. Assuming that the randomness used in the generation of the two challenges is uncorrelated, this is negligible. In consequence, the ciphertexts already work sufficiently well as domain-separator. Kousidis, et al. Expires 2 August 2024 [Page 35] Internet-Draft PQC in OpenPGP January 2024 9.4. SLH-DSA Message Randomizer The specification of SLH-DSA [FIPS-205] prescribes an optional non- deterministic message randomizer. This is not used in this specification, as OpenPGP v6 signatures already provide a salted signature data digest of the appropriate size. 9.5. Binding hashes in signatures with signature algorithms In order not to extend the attack surface, we bind the hash algorithm used for signature data digestion to the hash algorithm used internally by the signature algorithm. ML-DSA internally uses a SHAKE256 digest, therefore we require SHA3 in the ML-DSA + ECC signature packet, see Section 6.2.1. Note that we bind a NIST security category 2 hash function to a signature algorithm that falls into NIST security category 3. This does not constitute a security bottleneck: because of the unpredictable random salt that is prepended to the digested data in v6 signatures, the hardness assumption is not collision resistance but second-preimage resistance. In the case of SLH-DSA the internal hash algorithm varies based on the algorithm and parameter ID, see Section 7.1.1. 10. Additional considerations 10.1. Performance Considerations for SLH-DSA This specification introduces both ML-DSA + ECC as well as SLH-DSA as PQ(/T) signature schemes. Generally, it can be said that ML-DSA + ECC provides a performance in terms of execution time requirements that is close to that of traditional ECC signature schemes. Regarding the size of signatures and public keys, though, ML-DSA has far greater requirements than traditional schemes like EC-based or even RSA signature schemes. Implementers may want to offer SLH-DSA for applications where a higher degree of trust in the signature scheme is required. However, SLH-DSA has performance characteristics in terms of execution time of the signature generation as well as space requirements for the signature that are even greater than those of ML-DSA + ECC signature schemes. Kousidis, et al. Expires 2 August 2024 [Page 36] Internet-Draft PQC in OpenPGP January 2024 Pertaining to the execution time, the particularly costly operation in SLH-DSA is the signature generation. In order to achieve short signature generation times, one of the parameter sets with the name ending in the letter "f" for "fast" should be chosen. This comes at the expense of a larger signature size. In order to minimize the space requirements of a SLH-DSA signature, a parameter set ending in "s" for "small" should be chosen. This comes at the expense of a longer signature generation time. 11. IANA Considerations IANA will add the following registries to the Pretty Good Privacy (PGP) registry group at https://www.iana.org/assignments/pgp- parameters: * Registry name: SLH-DSA-SHA2 parameters Registration procedure: SPECIFICATION REQUIRED [RFC8126] Values defined in this document, Table 3. * Registry name: SLH-DSA-SHAKE parameters Registration procedure: SPECIFICATION REQUIRED [RFC8126] Values defined in this document, Table 4. Furthermore IANA will add the algorithm IDs defined in Table 1 and Table 2 to the registry Public Key Algorithms. 12. Changelog 12.1. draft-wussler-openpgp-pqc-01 * Shifted the algorithm IDs by 4 to align with the crypto-refresh. * Renamed v5 packets into v6 to align with the crypto-refresh. * Defined IND-CCA2 security for KDF and key combination. * Added explicit key generation procedures. * Changed the key combination KMAC salt. * Mandated Parameter ID check in SPHINCS+ signature verification. * Fixed key share size for Kyber-768. Kousidis, et al. Expires 2 August 2024 [Page 37] Internet-Draft PQC in OpenPGP January 2024 * Added "Preliminaries" section. * Fixed IANA considerations. 12.2. draft-wussler-openpgp-pqc-02 * Added the ephemeral and public key in the ECC key derivation function. * Removed public key hash from key combiner. * Allowed v3 PKESKs and v4 keys with PQ algorithms, limiting them to AES symmetric ciphers. for encryption with SEIPDv1, in line with the crypto-refresh. 12.3. draft-wussler-openpgp-pqc-03 * Replaced round 3 submission with NIST PQC Draft Standards FIPS 203, 204, 205. * Added consideration about security level for hashes. 12.4. draft-wussler-openpgp-pqc-04 * Added Johannes Roth as author 12.5. draft-ietf-openpgp-pqc-00 * Renamed draft 13. Contributors Stephan Ehlen (BSI) Carl-Daniel Hailfinger (BSI) Andreas Huelsing (TU Eindhoven) 14. References 14.1. Normative References [I-D.ietf-openpgp-crypto-refresh] Wouters, P., Huigens, D., Winter, J., and N. Yutaka, "OpenPGP", Work in Progress, Internet-Draft, draft-ietf- openpgp-crypto-refresh-13, 4 January 2024, . Kousidis, et al. Expires 2 August 2024 [Page 38] Internet-Draft PQC in OpenPGP January 2024 [RFC3394] Schaad, J. and R. Housley, "Advanced Encryption Standard (AES) Key Wrap Algorithm", RFC 3394, DOI 10.17487/RFC3394, September 2002, . [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, January 2016, . [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital Signature Algorithm (EdDSA)", RFC 8032, DOI 10.17487/RFC8032, January 2017, . [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, June 2017, . 14.2. Informative References [BDPA08] Bertoni, G., Daemen, J., Peters, M., and G. Assche, "On the Indifferentiability of the Sponge Construction", 2008, . [CS03] Cramer, R. and V. Shoup, "Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack", 2003, . [draft-driscoll-pqt-hybrid-terminology] Driscoll, F., "Terminology for Post-Quantum Traditional Hybrid Schemes", March 2023, . [FIPS-203] National Institute of Standards and Technology, "Module- Lattice-Based Key-Encapsulation Mechanism Standard", August 2023, . [FIPS-204] National Institute of Standards and Technology, "Module- Lattice-Based Digital Signature Standard", August 2023, . [FIPS-205] National Institute of Standards and Technology, "Stateless Hash-Based Digital Signature Standard", August 2023, . Kousidis, et al. Expires 2 August 2024 [Page 39] Internet-Draft PQC in OpenPGP January 2024 [GHP18] Giacon, F., Heuer, F., and B. Poettering, "KEM Combiners", 2018, . [NIST-PQC] Chen, L., Moody, D., and Y. Liu, "Post-Quantum Cryptography Standardization", December 2016, . [NISTIR-8413] Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Smith-Tone, D., and Y. Liu, "Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process", NIST IR 8413 , September 2022, . [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation", RFC 5639, DOI 10.17487/RFC5639, March 2010, . [SEC1] Standards for Efficient Cryptography Group, "Standards for Efficient Cryptography 1 (SEC 1)", May 2009, . [SP800-185] Kelsey, J., Chang, S., and R. Perlner, "SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash, and ParallelHash", NIST Special Publication 800-185 , December 2016, . [SP800-186] Chen, L., Moody, D., Regenscheid, A., and K. Randall, "Recommendations for Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters", NIST Special Publication 800-186 , February 2023, . [SP800-56A] Barker, E., Chen, L., Roginsky, A., Vassilev, A., and R. Davis, "Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography", NIST Special Publication 800-56A Rev. 3 , April 2018, . Kousidis, et al. Expires 2 August 2024 [Page 40] Internet-Draft PQC in OpenPGP January 2024 [SP800-56C] Barker, E., Chen, L., and R. Davis, "Recommendation for Key-Derivation Methods in Key-Establishment Schemes", NIST Special Publication 800-56C Rev. 2 , August 2020, . Acknowledgments Thanks to Daniel Huigens and Evangelos Karatsiolis for the early review and feedback on this document. Authors' Addresses Stavros Kousidis BSI Germany Email: stavros.kousidis@bsi.bund.de Johannes Roth MTG AG Germany Email: johannes.roth@mtg.de Falko Strenzke MTG AG Germany Email: falko.strenzke@mtg.de Aron Wussler Proton AG Switzerland Email: aron@wussler.it Kousidis, et al. Expires 2 August 2024 [Page 41]