Post-Quantum Cryptography in OpenPGP

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.1. CRYSTALS-Kyber

CRYSTALS-Kyber [KYBER-Subm] 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 CRYSTALS-Kyber only in composite combination with ECC-based encryption schemes in order to provide a pre-quantum security fallback.¶

1.2.2. CRYSTALS-Dilithium

CRYSTALS-Dilithium, defined in [DILITHIUM-Subm], is a signature scheme that, like CRYSTALS-Kyber, is based on the hardness of solving lattice problems in module lattices. Accordingly, this specification only defines CRYSTALS-Dilithium in composite combination with ECC-based signature schemes.¶

1.2.3. SPHINCS+

SPHINCS+ [SPHINCS-Subm] 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 SPHINCS+ as a standalone signature scheme.¶

In deployments the performance characteristics of SPHINCS+ should be taken into account. We refer to Section 10.1 for a discussion of the performance characteristics of this scheme.¶

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

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.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 CRYSTALS-Kyber with an ECC-based KEM,¶
• PQ/T multi-algorithm digital signature, namely composite combinations of CRYSTALS-Dilithium with ECC-based signature schemes,¶
• PQ digital signature, namely SPHINCS+ 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.¶

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

3.2.1. SPHINCS+-simple-SHA2

For the SPHINCS+-simple-SHA2 signature algorithm from Table 2, the following parameters are specified:¶

All security parameters inherit the requirement of SPHINCS+-simple-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. SPHINCS+-simple-SHAKE

For the SPHINCS+-simple-SHAKE signature algorithm from Table 2, the following parameters are specified:¶

All security parameters inherit the requirement of SPHINCS+-simple-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.¶

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

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) <- eccKem.encap(eccPublicKey)

and¶

(eccKeyShare) <- eccKem.decap(eccPrivateKey, eccCipherText)

The placeholder eccKem has to be replaced with the specific ECC-KEM from the row "ECC-KEM" of Table 5, Table 6, and Table 7.¶

5.1.2. Kyber-KEM

Kyber-KEM features the following operations:¶

(kyberCipherText, kyberKeyShare) <- kyberKem.encap(kyberPublicKey)

and¶

(kyberKeyShare) <- kyberKem.decap(kyberCipherText, kyberPrivateKey)

The above are the operations Kyber.CCAKEM.Enc() and Kyber.CCAKEM.Dec() defined in [KYBER-Subm].¶

Kyber-KEM has the parameterization with the corresponding artifact lengths in octets as given in Table 8. All artifacts are encoded as defined in [KYBER-Subm].¶

The placeholder kyberKem has to be replaced with the specific Kyber-KEM from the column "Kyber-KEM" of Table 8.¶

The procedure to perform kyberKem.encap() is as follows:¶

1. Extract the component public key kyberPublicKey that is part of the recipient's composite public key¶
2. Invoke (kyberCipherText, keyShare) <- kyberKem.encap(kyberPublicKey)¶
3. Set kyberCipherText as the Kyber ciphertext¶
4. Set keyShare as the Kyber symmetric key share¶

The procedure to perform kyberKem.decap() is as follows:¶

1. Invoke keyShare <- kyberKem.decap(kyberCipherText, kyberPrivateKey)¶
2. Set keyShare as the Kyber symmetric key¶

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

SHA3-256 MUST be used to hash the publicKey of the recipient.¶

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,
//                   kyberKeyShare, kyberCipherText,
//                   fixedInfo, oBits)
//
//   Input:
//   eccKeyShare     - the ECC key share encoded as an octet string
//   eccCipherText   - the ECC ciphertext encoded as an octet string
//   kyberKeyShare   - the Kyber key share encoded as an octet string
//   kyberCipherText - the Kyber 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"

eccKemData = eccKeyShare || eccCipherText
kyberKemData = kyberKeyShare || kyberCipherText
encData = counter || eccKemData || kyberKemData || fixedInfo

MB = KMAC256(domSeparation, encData, oBits, customizationString)

Note that the values eccKeyShare defined in Section 5.1.1 and kyberKeyShare 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.¶

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 Kyber and the ECC component keys. Kyber key generation follows the specification [KYBER-Subm] and the artifacts are encoded as fixed-length octet strings. 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 Table 5, Table 6, or Table 7.¶

5.2.4. Encryption procedure

The procedure to perform public-key encryption with a Kyber + 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 kyberPublicKey component from the algorithm specific data encoded in pkComposite with the format specified in Section 5.3.2.¶
4. Instantiate the ECC-KEM eccKem.encap() and the Kyber-KEM kyberKem.encap() depending on the algorithm ID according to Table 9¶
5. Compute (eccCipherText, eccKeyShare) := eccKem.encap(eccPublicKey)¶
6. Compute (kyberCipherText, kyberKeyShare) := kyberKem.encap(kyberPublicKey)¶
7. Compute fixedInfo as specified in Section 5.2.1¶
8. Compute KEK := multiKeyCombine(eccKeyShare, eccCipherText, kyberKeyShare, kyberCipherText, 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 || kyberCipherText || len(C) || C¶

5.2.5. Decryption procedure

The procedure to perform public-key decryption with a Kyber + 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 kyberSecretKey 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 eccKem.decap() and the Kyber-KEM kyberKem.decap() depending on the algorithm ID according to Table 9¶
6. Parse eccCipherText, kyberCipherText, and C from encryptedKey encoded as eccCipherText || kyberCipherText || len(C) || C as specified in Section 5.3.1¶
7. Compute (eccKeyShare) := eccKem.decap(eccCipherText, eccPrivateKey)¶
8. Compute (kyberKeyShare) := kyberKem.decap(kyberCipherText, kyberPrivateKey)¶
9. Compute fixedInfo as specified in Section 5.2.1¶
10. Compute KEK := multiKeyCombine(eccKeyShare, eccCipherText, kyberKeyShare, kyberCipherText, fixedInfo, oBits=256) as defined in Section 5.2.2¶
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.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 Kyber ciphertext, whose length depends on the algorithm ID as specified in Table 8.¶
• The one-octet algorithm identifier, if it was 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 Kyber public key, whose length depends on the algorithm ID as specified in Table 8.¶

The algorithm-specific secret key is these two values:¶

• 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 Kyber secret key, whose length depends on the algorithm ID as specified in Table 8.¶

6.1.1. EdDSA-Based signatures

To sign and verify with EdDSA the following operations are defined:¶

(eddsaSignature) <- eddsa.sign(eddsaPrivateKey, dataDigest)

and¶

(verified) <- eddsa.verify(eddsaPublicKey, eddsaSignature, dataDigest)

The public and private keys, 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:¶

6.1.2. ECDSA-Based signatures

To sign and verify with ECDSA the following operations are defined:¶

(ecdsaSignatureR, ecdsaSignatureS) <- ecdsa.sign(ecdsaPrivateKey,
                                                 dataDigest)

and¶

(verified) <- ecdsa.verify(ecdsaPublicKey, ecdsaSignatureR,
                           ecdsaSignatureS, dataDigest)

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

6.1.3. Dilithium signatures

The procedure for Dilithium signature generation is the function Sign(sk, M) given in Figure 4 in [DILITHIUM-Subm], where sk is the Dilithium private key and M is the data to be signed. OpenPGP does not use the optional randomized signing given as a variant in the definition of this function, i.e. rho' := H(K || mu) is used. The signing function returns the Dilithium signature. That is, to sign with Dilithium the following operation is defined:¶

(dilithiumSignature) <- dilithium.sign(dilithiumPrivateKey,
                                       dataDigest)

The procedure for Dilithium signature verification is the function Verify(pk, M, sigma) given in Figure 4 in [DILITHIUM-Subm], where pk is the Dilithium public key, M is the data to be signed and sigma is the Dilithium signature. That is, to verify with Dilithium the following operation is defined:¶

(verified) <- dilithium.verify(dilithiumPublicKey, dataDigest,
                               dilithiumSignature)

Dilithium has the parameterization with the corresponding artifact lengths in octets as given in Table 12. All artifacts are encoded as defined in [DILITHIUM-Subm].¶

6.2.1. Binding hashes

Composite Dilithium + ECC signatures MUST use SHA3-256 (hash algorithm ID 12) or SHA3-512 (hash algorithm ID 14) as hashing algorithm. Signatures using other hash algorithms MUST be considered invalid.¶

An implementation MUST support SHA3-256 and SHOULD support SHA3-512, in order to support the hash binding with Dilithium + ECC signatures.¶

6.2.2. Key generation procedure

The implementation MUST independently generate the Dilithium and the ECC component keys. Dilithium key generation follows the specification in [DILITHIUM-Subm] 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.¶

6.2.3. Signature Generation

To sign a message M with Dilithium + 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 Dilithium signature over dataDigest with dilithium.sign() from Section 6.1.3¶
4. Encode the EdDSA and Dilithium signatures according to the packet structure given in Section 6.3.1.¶

To sign a message M with Dilithium + 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 Dilithium signature over dataDigest with dilithium.sign() from Section 6.1.3¶
4. Encode the ECDSA and Dilithium signatures according to the packet structure given in Section 6.3.1.¶

6.2.4. Signature Verification

To verify a Dilithium + 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 Dilithium signature with dilithium.verify() from Section 6.1.3¶

To verify a Dilithium + ECDSA signature the following sequence of operations has to be performed:¶

1. Verify the ECDSA signature with ecdsa.verify() from Section 6.1.2¶
2. Verify the Dilithium signature with dilithium.verify() from Section 6.1.3¶

As specified in Section 4.3 an implementation MUST validate both signatures, i.e. EdDSA/ECDSA and Dilithium, to state that a composite Dilithium + ECC signature is valid.¶

6.3.1. Signature Packet (Tag 2)

The composite Dilithium + ECC schemes 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 for Dilithium + 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 Dilithium signature value, whose length depends on the algorithm ID as specified in Table 12.¶

The algorithm-specific v6 signature parameters for Dilithium + 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 Dilithium signature value, whose length depends on the algorithm ID as specified in Table 12.¶

6.3.2. Key Material Packets

The composite Dilithium + ECC schemes MUST be used only with v6 keys, as defined in [I-D.ietf-openpgp-crypto-refresh].¶

The algorithm-specific public key for Dilithium + 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.¶
• A fixed-length octet string containing the Dilithium public key, whose length depends on the algorithm ID as specified in Table 12.¶

The algorithm-specific private key for Dilithium + 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 Dilithium secret key, whose length depends on the algorithm ID as specified in Table 12.¶

The algorithm-specific public key for Dilithium + 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 Dilithium public key, whose length depends on the algorithm ID as specified in Table 12.¶

The algorithm-specific private key for Dilithium + 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 Dilithium secret key, whose length depends on the algorithm ID as specified in Table 12.¶

7.1.1. Binding hashes

SPHINCS+ signature packets MUST use the associated hash as specified in Table 14. Signature packets using other hashes MUST be considered invalid.¶

An implementation supporting a specific SPHINCS+ algorithm and parameter MUST also support the matching hash algorithm.¶

7.1.2. Key generation

The SPHINCS+ key generation is performed according to the function spx_keygen() specified in [SPHINCS-Subm], Sec. 6.2 as Alg. 19. The private and public key are encoded as defined in [SPHINCS-Subm].¶

7.1.3. Signature Generation

The procedure for SPHINCS+ signature generation is the function spx_sign(M, SK) specified in [SPHINCS-Subm], Sec. 6.4 as Alg. 20. Here, M is the dataDigest generated according to [I-D.ietf-openpgp-crypto-refresh] Section 5.2.4 and SK is the SPHINCS+ private key. The global variable RANDOMIZE specified in Alg. 20 is to be considered as not set, i.e. the variable opt shall be initialized with PK.seed. See also Section 9.4.¶

An implementation MUST set the Parameter ID in the signature equal to the issuing private key Parameter ID.¶

7.1.4. Signature Verification

The procedure for SPHINCS+ signature verification is the function spx_verify(M, SIG, PK) specified in [SPHINCS-Subm], Sec. 6.5 as Alg. 21. Here, M is the dataDigest generated according to [I-D.ietf-openpgp-crypto-refresh] Section 5.2.4, SIG is the signature, and PK is the SPHINCS+ public key.¶

An implementation MUST check that the Parameter ID in the signature and in the key match when verifying.¶

7.2.1. Signature Packet (Tag 2)

The SPHINCS+ algorithms 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 SPHINCS+ 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 SPHINCS+ signature value, whose length depends on the parameter ID in the format specified in Table 13.¶

7.2.2. Key Material Packets

The SPHINCS+ algorithms 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:¶

• A one-octet value specifying the SPHINCS+ 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 SPHINCS+ public key, whose length depends on the parameter ID as specified in Table 13.¶

The algorithm-specific private key is this value:¶

• A fixed-length octet string containing the SPHINCS+ secret key, whose length depends on the parameter ID as specified in Table 11.¶