Post-Quantum Readiness

The following provides an introduction to what is going on with Post-Quantum Cryptography (PQC) and outlines what it might entail to get ready for PQC, certificate issuance and digital signatures, and crypto agility.

Background

What is Post-Quantum Cryptography about?

For Public Key Infrastructure (PKI), the eventual arrival of quantum computers is going to mean that most of the algorithms we currently rely on are no longer secure. According to the National Institute of Standards and Technology (NIST):

The goal of post-quantum cryptography is to develop cryptographic systems that are secure against both quantum and classical computers and can interoperate with existing communications protocols and networks.

The question of when a large-scale quantum computer will be built is a complicated one. At the moment, estimates put the arrival of "meaningful" (at least in this sense) quantum computers at around 2030 or soon after.

What is going on with Post-Quantum Cryptography at the moment?

NIST has formally published three post-quantum cryptography Federal Information Processing Standards (FIPS):

FIPS 203, ML-KEM (derived from CRYSTALS-KYBER)
FIPS 204, ML-DSA (derived from CRYSTALS-Dilithium)
FIPS 205, SLH-DSA (derived from SPHINCS+)

These standards specify key establishment and digital signature schemes that are designed to resist future attacks by quantum computers, which threaten the security of current standards. The three algorithms specified in these standards are each derived from different submissions to the NIST Post-Quantum Cryptography Standardization Project.

A fourth digital signature standard FN-DSA (derived from FALCON) will follow, in addition to the other recommended hash-based schemes, XMSS and LMS, previously covered in SP 800-208.

Details on the new standards

The new standards are designed for two essential tasks for which encryption is typically used: general encryption, used to protect information exchanged across a public network, and digital signatures, used for identity authentication. NIST announced its selection of four algorithms: CRYSTALS-Kyber, CRYSTALS-Dilithium, SPHINCS+ and FALCON, slated for standardization in 2022 and released draft versions of three of these standards in 2023. The fourth draft standard based on FALCON is planned for late 2024.

NIST has changed the algorithms’ names to specify the versions that appear in the three finalized standards:

FIPS 203: Intended as the primary standard for general encryption. Among its advantages are comparatively small encryption keys that two parties can exchange easily, as well as its speed of operation. The standard is based on the CRYSTALS-Kyber algorithm, which has been renamed ML-KEM, short for Module-Lattice-Based Key-Encapsulation Mechanism.
FIPS 204: Intended as the primary standard for protecting digital signatures. The standard uses the CRYSTALS-Dilithium algorithm, which has been renamed ML-DSA, short for Module-Lattice-Based Digital Signature Algorithm.
FIPS 205: Also designed for digital signatures. The standard employs the SPHINCS+ algorithm, which has been renamed SLH-DSA, short for Stateless Hash-Based Digital Signature Algorithm. The standard is based on a different math approach than ML-DSA, and it is intended as a backup method in case ML-DSA proves vulnerable.

Current NIST-approved digital signature schemes are specified in FIPS 186-5, Digital Signature Standard, and SP 800-208, Recommendation for Stateful Hash-Based Signature Schemes.

NIST is also developing a FIPS that specifies a digital signature algorithm derived from FALCON as an additional alternative to these standards. When the draft FIPS 206 standard built around FALCON is released, the algorithm will be dubbed FN-DSA, short for FFT (fast-Fourier transform) over NTRU-Lattice-Based Digital Signature Algorithm.

How can Keyfactor help?

Keyfactor provides a complete solution stack to enable a seamless transition to quantum-safe standards, with the ability to discover and inventory certificates, deploy quantum-ready PKI and signing solutions, automate certificate migration, and implement quantum-safe cryptography.

Keyfactor solutions have already supported pre-standardized PQC algorithms for some time and we are working to adopt the final standards into our solution stack.

Post-Quantum Readiness

The following sections strategize on getting ready and explore challenges in the following areas:

Cryptography
Certificate Issuance and Digital Signatures
Crypto Agility

Cryptography

Cryptography in the majority of Keyfactor products is implemented in the Bouncy Castle crypto APIs and in Hardware Security Modules (HSMs). In the area of cryptography, several considerations are reasonable to consider.

What should you be doing now?

Keyfactor is committed to supporting our customers through the transition to these new PQC standards, and we’ll be working to adopt the final standards into our solution stack.

Trying the pre-standardized PQC algorithms, while there are some differences with the final standards, the characteristics of the algorithms are unlikely to change. You will find the key sizes, signature sizes, and, in some cases, even the key usages are different from what we are all familiar with. All these things are likely to have long-term effects on resourcing, design, protocols, and performance. That said, governments worldwide have already indicated that they will expect vendors to be moving to these algorithms when standards are available, and sectors in the Enterprise market will likely do likewise.

2030 is a bit close! What about your PKI? You need a trust anchor that will live well beyond 2030.

There are also two existing Post-Quantum signature standards, LMS and XMSS, which are already standardized by both NIST (SP 800-208) and the IETF (RFC 8554 and RFC 8391). While these algorithms are secure in themselves, the NIST standard mandates the use of an HSM as the algorithms are stateful, meaning that with each signature performed, the state of private must change slightly (a new key from a tree of keys actually). Using the same state of the private key twice will completely break the security of the algorithm. Bouncy Castle added support for LMS in BC 1.65, and XMSS in BC 1.68. LMS also has a full CMS/certificate profile defined in RFC 8708, this makes it possible to use in certificates, S/MIME, and TSP. Support for this was also added in BC 1.70.

Bouncy Castle has added LMS to the BCFIPS APIs, it will appear in BC-FJA 2.0.0, but the algorithm will only ever be certified for signature verification, due to the NIST HSM requirements for stateful algorithms.

In addition to the existing Post-Quantum signature standards, LMS and XMSS, NIST is also developing a FIPS that specifies a digital signature algorithm derived from FALCON as an additional alternative to these standards.

Certificate Issuance and Digital Signatures

Certificate issuance and digital signatures can be accomplished using Post Quantum cryptography algorithms.

What is Keyfactor looking at for Digital Signatures?

Code signing based on SignServer using the post-quantum SPHINCS+ and Dilithium algorithms through Bouncy Castle allows you to try out creating post-quantum keys and signatures. The use case is to demonstrate Post-Quantum Cryptography (PQC) code signing based on PQC CA hierarchy in IoT applications, as it is expected to be one of the first areas where PQC is applied. The experimental support is suited for proof-of-concept implementations, for instructions on how to try it out, see Post-Quantum Code Signing How-to.

Other signing use cases like code signing for general-purpose platforms and document signing for public validation depend on the updated PKI ecosystem for these use cases.

What is Keyfactor looking at for Certificate Authorities?

We first recommend creating a separate PQC CA hierarchy, much like is already standard for RSA and EC. As of version 8.3, EJBCA supports hybrid certificates (for experimental use only), such as X.509 alternative signatures, and these are implemented in Bouncy Castle since version 1.73.

For interoperability, there is a need for protocol standardization for X.509, CMS, and other protocols for efficient usage. Keyfactor participates in interoperability exercises with other vendors.

Keep in mind that if you want to use this in a high-security environment such as in a FedRAMP situation, you will need to take advantage of HSM support as well, for which there is yet no standardized API (PKCS#11 and/or REST), and require the use of proprietary mechanisms and API. Keyfactor is engaged with HSM vendors to demonstrate interoperability.

Crypto Agility

As the time to roll out new algorithms gets closer, it is wise to establish a high level of crypto agility in your organization. This is already needed for the use of classic cryptography (even if Quantum never becomes a legitimate threat), as the SHA-1 migration and other incidents have shown in recent years.

Effective “crypto agility” means that to be able to act on a large scale, you need to know where you need to act. Being crypto agile involves factors such as:

Having an inventory of keys, certs and algorithms in use.
Automation and compartmentalization - to better be able to make changes and reduce side effects.
Shorter validity - making agility mandatory in products and solutions.

It involves so much more than changing an algorithm name - and these are all topics that Keyfactor can help you with.

Contact us

We are happy to explore with our users the more general use of post-quantum cryptography. Keyfactor solutions have already supported pre-standardized PQC algorithms for some time, and following the NIST announcement, we are committed to supporting our customers through the transition to these new PQC standards, and we are incorporating the approved algorithms across our PKI, certificate management, code signing, and cryptographic API solutions.

Again, it all depends on what you are trying to do, so feel free to ask, we are here to help.