Post-Quantum Cryptography Keys and Signatures

The following provides and introduction to Post-Quantum Cryptography (PQC) keys and signatures.

Background

Post-quantum cryptography is cryptography that is resistant to the theoretical threat that a cryptographically relevant quantum computer could port. While such a quantum computer does not yet exist, governments and standardization organizations are working towards a migration from classic asymmetric cryptography to new post-quantum cryptography algorithms. The largest actor in this process is the National Institute of Standards and Technology (NIST).

NIST has announced the standardization of three post-quantum cryptography (PQC) algorithms, FIPS 203 for ML-KEM (derived from CRYSTALS-KYBER), FIPS 204 for ML-DSA (derived from CRYSTALS-Dilithium), and FIPS 205 for SLH-DSA (derived from SPHINCS+).

A fourth digital signature standard FN-DSA (derived from FALCON) will follow. In addition, there are two stateful hash-based signature (SHBS) algorithms standardized in NIST SP800-208 and IETF.

EJBCA versions prior to 9.1 supported NIST candidate PQC algorithms Dilithium and Kyber. These algorithms are removed in EJBCA 9.1 and replaced by the NIST approved PQC algorithms ML-DSA and ML-KEM.

Generated Keys and Certificates

Signature algorithms suitable for a CA are:

• ML-DSA (derived from Dilithium), FIPS 204
• SLH-DSA (derived from SPHINCS+), FIPS 205
• Falcon (NIST standard based on FALCON is planned for 2025 under the name FN-DSA). Non-standardized PQC algorithms are only valid for non-production use.
• LMS and XMSS (SP800-208, RFC 8554, and RFC 8391)

When generating a CA in EJBCA, up to three keys and certificates are generated:

• A CA signing key pair and certificate
• An encryption key pair, used for encrypting key recovery information
• An OCSP signer key pair and certificate

When using PQC keys, the CA signing key pair will be the PQC key type you select when creating the CA. The CA signing certificate will be signed using your selected signature algorithm. The encryption key pair must still be RSA.

OCSP signing is not yet supported using PQC, EC and RSA must still be used.

Signing large CRLs with PQC algorithms

The new algorithms are generally not hash-and-sign as classic RSA and EC (for example SHA256WithRSA and SHA256WithECDSA) meaning that all data to be signed are sent to the signature function. This can cause problems for signing for example large CRLs using HSMs as the amount of data that can be sent over the network to an HSM is usually limited. Albeit pre-hash versions of ML-DSA and SLH-DSA exist in the FIPS standards it is still not yet decided (Dec 2024) if these will be allowed by IETF RFC as drafted in the current Internet draft for using ML-DSA signatures in PKIX.

Due to the above we recommend early production scale testing of uses cases when using PQC algorithms in order to avoid issues that CRLs can not be created if they grow more than expected. The expected result may depend heavily on the exact HSM being used and the architecture of your solution.

Using Post-Quantum algorithms with an HSM

ENTERPRISE

There is currently no standard in PKCS#11 for using the NIST post-quantum algorithms and HSM support for post-quantum algorithms is being worked on. LMS/HSS is standardized in PKCS#11 v3.1, ML-DSA and ML-KEM will be standardized in PKCS#11 v3.2.

As post-quantum support for HSMs is added, it is important to note that this may differ between different HSM vendors. Thus, the HSM support will be tied to specific vendors and will not be general for all HSMs.

As of EJBCA 9.1, there may be HSM support for ML-DSA for a few selected HSMs. Interoperability tests are pending. Contact Keyfactor for more information.

Post-Quantum Algorithms

EJBCA currently supports the following post-quantum algorithms for CAs, also supported by Bouncy Castle. This can change rapidly, so check the availability in the EJBCA user interface to be certain of the latest updates.

A comparison of security levels is that RSA 2048 is 112 bit security level, RSA 3072 and P-256 is 128 bit, and P-521 is 256 bit.

Creating Client Certificates

You can also issue normal requests for client certificates using post-quantum keys.

All certificates signed by a post-quantum CA will naturally use post-quantum signatures, regardless of whether the client keys are RSA, ECDSA, EdDSA, or one of the post-quantum algorithms.

Post-quantum KEM keys cannot be used for signature generation, and therefore, PKCS#10 CSRs that require signature proof of possession (POP) cannot be used. Instead, CRMF messages using the RA Verified POP method can be used. Currently, ML-DSA keys are supported for this purpose. Additionally, for ML-KEM keys, CMP using encrCert POP is supported as of EJBCA 9.1. Furthermore, EJBCA supports the following KEM keys for inclusion in client certificates.

Example CSR Generation

To generate a valid sample CSR for your clients, you can use the EJBCA gencsr CLI command. The following provides an example for generating a CSR with ML-DSA-44:

bin/ejbca.sh gencsr --keyalg ML-DSA-44 --sigalg ML-DSA-44 --subjectdn "CN=mldsa subject"

Issuing certificates with KEM subject public keys

As KEM keys cannot be used to create signatures, you cannot currently create a PKCS#10 CSR with a KEM public key to request a certificate, since a signature is required for proof of possession (POP). The CRMF CSR format supports alternative POP methods, and you can, for example, use CMP with encrCert POP (see CMP). You can also use other mechanisms that do not require PKCS#10 CSRs to issue certificates with KEM keys, such as CA-generated PEM files or WS API plain public keys.

Example:

ant cmpclient
cd dist/cmpclient
./cmpclient.sh crmf --url http://localhost/ejbca/publicweb/cmp/encrcert --dn "CN=encrCertPOP" --authparam qw --reqnewkeyspec ML-KEM-512 --includepopo --v

Related Content

To learn more abut what it might entail to get ready for PQC, see Post-Quantum Readiness.

To find out more about using the Bouncy Castle Kotlin API, see How to Use the Bouncy Castle Kotlin API.