All about quantum-safe certificates

The advent of quantum computers will render ECC and RSA encryption algorithms obsolete, requiring companies to migrate their computing systems and PKI infrastructure to new, quantum-safe cryptographic algorithms.

This migration of PKI solutions to quantum-safe crypto algorithms will pose many major challenges for many enterprises. All existing applications and systems will need to be updated to support the new quantum-safe algorithms now being developed in response to the threats posed by quantum computers. The process of updating to new algorithms requires significant engineering work and many systems will require extensive updates.

For many companies, a “rip-and-replace” approach to upgrading their encryption systems is simply not viable. They need a solution that enables a gradual and low-risk migration of systems to these new crypto algorithms to avoid having to update all systems at once. In addition, all systems need to be tested to ensure they are working properly as they are migrated.

Quantum-safe crypto requires certificates that support quantum-safe algorithms.  New certificate types have been introduced to solve the challenges of migrating to quantum-safe crypto algorithms, with different certificate types for different use cases.

Four Types of Certificates

There are four certificate “types” that are relevant to any discussion about quantum-safe cryptography— each having distinct purposes, uses, and tradeoffs. It is important to note that in each case, we are still discussing X.509 digital certificates. The types of certificates vary according to the purpose of the certificate and the encryption algorithms used to create the certificate.

Traditional PKI certificates

Traditional PKI certificates are the certificates being used in our PKI systems today. “Traditional” refers to the fact that these certificates utilize traditional ECC or RSA encryption algorithms. The majority of PKI systems will continue to use traditional PKI certificates for some time to come. They provide effective protection against existing computing attacks, but in the future, they will be made obsolete by quantum computers and quantum attacks on ECC and RSA encryption.

Quantum-safe certificates

Quantum-safe certificates are X.509 certificates that use quantum-safe encryption algorithms.  While NIST is still in the process of standardizing quantum-safe encryption algorithms, they have identified a number of candidate algorithms and implementations of these algorithms are currently available.

Migrating to quantum-safe algorithms means using quantum-safe certificates. That is to say, X.509 certificates that contain quantum-safe encryption keys used with quantum-safe encryption algorithms. These implementations will require updating existing systems to utilize the new encryption algorithms.

Hybrid certificates

Hybrid certificates are cross-signed certificates containing both a traditional (RSA or ECC) key and signature, and a quantum-safe key and signature. Hybrid certificates enable a migration path for systems with multiple components that cannot all be upgraded or replaced at the same time.

Using hybrid certificates is akin to having a house with two doors and each door has its own separate key. If I install a new front door lock, only people with the new key can open that door.  People with the old key can still enter the house, but only via the unchanged back door. Over time, I can swap out keys to users, giving them access through the new door lock. After a transition period, I can switch out the backdoor lock so that it uses the same new key as the front door.

Companies will need to update the main pieces of their IT infrastructure to utilize quantum-safe algorithms and hybrid certificates. As other systems and devices access the newly updated system, they can continue to utilize classic encryption algorithms. The quantum-safe key and signature are stored as an alternative signature algorithm, alternative key, and alternative signature algorithm. Applications that do not utilize the quantum-safe fields in the hybrid certificates will ignore these additional fields. Over time, security teams can update applications and systems to use the new quantum-safe algorithms. Once the transition is complete, they can deprecate hybrid certificates, and replace them with pure quantum-safe certificates.

Composite certificates

Composite certificates are similar to hybrid certificates in that they contain multiple keys and signatures but were created to solve a different problem. The goal of composite keys is to address the concern that individual encryption algorithms available now may later prove to be insecure. Many new encryption algorithms are being developed to address quantum-safe cryptographic use cases. While NIST is coordinating a process to vet and select quantum-safe crypto algorithms, they have not yet been thoroughly vetted and battle-hardened. It is possible that security researchers or hackers will discover vulnerabilities in one or more of these algorithms at some point in the future.

With the trustworthiness of individual post-quantum algorithms still a question, a multi-key cryptographic solution can provide enhanced levels of security by requiring crypto operations to utilize multiple keys. Breaking a properly implemented composite key encryption scheme requires individually breaking each of the component algorithms. This is not easy.

Composite certificates are akin to having a single door with multiple locks. Someone must have ALL of the keys to open the door. If one of the encryption algorithms proves to have an exploitable vulnerability, the entire system is still secure.

Even though NIST is currently conducting a process to attempt to prove the efficacy of the candidate algorithms before certifying the algorithms as quantum-safe, actually proving the crypto algorithms are secure is a difficult and unreliable process. Algorithms that appear safe today may later be found to be vulnerable to new and novel attacks. Composite certificates provide a strong defense against such longer-term concerns, making them ideal for environments with high security requirements. However, creating composite certificates requires additional computational power, as all the data needs to be encrypted with multiple keys. 

Summary

Migrating to PKI systems and related applications to quantum-safe crypto algorithms requires updating each system using PKI. The encryption libraries and all applications using certificates must be upgraded to support the new algorithms. For many enterprise systems, this will be a major effort with multiple systems requiring updates.

Companies have the option of replacing all systems simultaneously, making a hard switch to using quantum-safe certificates. Unfortunately, for many companies, that simply is not possible. Hybrid certificates provide a workable alternative for these scenarios, allowing a gradual migration to quantum-safe crypto algorithms.

For those with extremely high security requirements, composite certificates provide an alternative that hedges against concerns that some of the new quantum-safe crypto algorithms may later be shown to have vulnerabilities.

Image credit: plotplot/Shutterstock

Alan Grau has 30 years of experience in telecommunications and the embedded software marketplace. He is VP of IoT/Embedded Solutions at Sectigo, the world’s largest commercial Certificate Authority and provider of purpose-built, automated PKI solutions. Alan joined Sectigo in May 2019 as part of the company’s acquisition of Icon Labs, a leading provider of security software for IoT and embedded devices, where he was CTO and co-founder, as well as the architect of Icon Labs' award-winning Floodgate Firewall. He is a frequent industry speaker and blogger and holds multiple patents related to telecommunication and security.