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 supports a variety of post-quantum algorithms for experimentation and testing. As development is moving fast, the algorithms supported by EJBCA at any given moment may change. Keyfactor is committed to supporting our customers through the transition to the new PQC standards and is working to adopt the final standards into our solution stack.

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 draft standard based on FALCON is planned for late 2025). 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.

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

Keys	Signature algorithm	Comment	Security Level
ML-DSA-44	ML-DSA-44	FIPS-204 in EJBCA 9.1	128 bit
ML-DSA-65	ML-DSA-65	FIPS-204 in EJBCA 9.1	>128 <192 bit
ML-DSA-87	ML-DSA-87	FIPS-204 in EJBCA 9.1	256 bit
Falcon-512	Falcon-512	NIST round 3 since EJBCA 8.1	128 bit
Falcon-1024	Falcon-1024	NIST round 3 since EJBCA 8.1	256 bit

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.

Keys	Comment
ML-KEM-512	FIPS-205 in EJBCA 9.1
ML-KEM-1024	FIPS-205 in EJBCA 9.1

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:

BASH

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:

CODE

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