Preparing for a Quantum World: Examining the Migration Path of Hybrid Certificates

For the migration to quantum-safe cryptography, the term “hybrid” is often used. In some discussions, the term itself leads to a deeper dive into what it actually means. 

The term “hybrid cryptosystem” from Wikipedia is not helpful, as it describes it as combining asymmetric and symmetric cryptosystems. This is not what it means in the context of post-quantum cryptography discussions.   

What everyone means by “hybrid cryptography” in the context of quantum-safe is combining classic asymmetric cryptography with post-quantum asymmetric cryptography. For example, EC + Dilithium, RSA + SPHINCS+, ECDH + Kyber, or other combinations where classic or traditional algorithms typically mean RSA or EC and post-quantum mean Dilithium SPHINCS+, Kyber, or one of the other proposed post-quantum algorithms. 

If the new post-quantum algorithms are secure against a future quantum computer, why would we want hybrid systems is a question many people ask. And it is true that there is a debate in the community on the need for hybrid, and on the pros and cons of different hybrid systems. There are (at least) two arguments for hybrid systems: 

1. During a migration phase, there will be endpoints that are PQC-capable and those that are not. To enable them to communicate, a backward-compatible hybrid solution is needed where they can negotiate capabilities. If both endpoints are PQC-capable, they can use post-quantum cryptography, but if one endpoint is not PQC-capable, it can fall back to classic encryption.
2. Some of the new post-quantum algorithms and their implementations are not as well-analyzed and battle-tested as classic encryption algorithms, resulting in a fear that some PQC algorithms may, in the future, be broken by today’s computers. By cleverly combining algorithms in a hybrid design, you can enforce verification of both. If a future quantum computer breaks RSA and EC while PQC algorithms are safe, the PQC part of the hybrid system will protect the whole. If current computers are able to break PQC algorithms, and no cryptographically relevant quantum computer exists, the classic algorithm protects the whole. 

Three immediate use cases for hybrid cryptography that are easy to identify: 

• TLS connections: protecting data in transit from decryption against today’s computers and potential quantum computers of the future.
   

• Digital identities: usually in the form of certificates to protect authentication from today’s and future threats.
   

• Digital signatures: protecting the integrity of code and documents far into the future. 

Some organizations are against hybrid systems, while some are in favor. Both have arguments for and against, as I mentioned above. The conclusion that is easiest to make is that “it depends,” which is, unfortunately, one of the most used phrases in cybersecurity when asked for simple advice. Whether you need or want hybrid systems depends on your use case, threat level, ability to manage complexity and many other factors.

If I would dare to draw any consensus, it would be that there are lots of skilled organizations out there and if someone considers hybrid systems essential, I will not argue against them. But, if they consider hybrid systems unnecessary, I will not argue against that either. As it stands, we will likely have to live with both hybrid and non-hybrid solutions for a long time. 

We have identified four different PKI migration paths, using different types of non-hybrid and currently proposed hybrid solutions. The names given to the different approaches are my own invention. Which strategy an organization should use will depend on the use case and how much control they have on the end points and their capabilities. 

1. Complete migration with hard cutoff: Where a new PKI is set up using a post-quantum algorithm. When all endpoints are PQC capable the classic PKI is retired, and certificates are issued from the new PQC PKI. The old PKI is shut down very soon after the new PKI goes into production.
2. Transitional migration with soft cutoff: Where a new PKI is set up using a post-quantum algorithm. Both PKIs live in parallel, and clients can be issued with either a classic certificate or a PQC certificate, or both, depending on their capabilities. The old and the new PKI live in parallel for an extended period of time.
3. Hybrid backward compatible migration: Where a new PKI is set up with backward compatible hybrid certificates. The new PKI can issue certificates to PQC-capable devices, and non-PQC-capable devices will simply ignore the PQC algorithms and negotiate classic cryptography. The old PKI can be shut down and replaced with the new backward-compatible hybrid PKI.
4. Composite non-backward compatible migration: Where a new PKI is set up with non-backward-compatible hybrid certificates (composites). Similar to a hard or soft cutoff in that PQC certificates can only be issued to PQC capable devices, with the additional feature that post-quantum cryptography is also protected by classic cryptography. 

Pros and cons of different strategies, and demands on the environment are topics for another post. There is of course nothing to prevent combinations of the above strategies either. 

Migration to a complete set of new algorithms will not be a walk in the park. Something may look simple, but in general, there are a lot of things out there with hundreds of thousands of different use cases and millions of different environments. There is no one-size-fits-all solution, which is why we have to develop multiple, different migration strategies — something that unfortunately adds complexity. 

In the meantime, discover how organizations are making strides to prepare and protect their data from the future threat of quantum computing in our report, The State of Quantum Readiness in 2024.