We’re beginning to see the beginning of the end – or the end of the beginning – for how we’ve done PKI for the last 30 years. The quantum computing threat against our beloved RSA and EC keys, while hyped, remains ten years out, as it has for the last twenty.
New fields of physics or computer science need to be uncovered before anyone can construct a quantum computer capable of breaking contemporary asymmetric keys. Unless this scientific progress is of a truly world-changing nature, constructing a quantum computer will remain in the domain of a few large actors.
Even so, there is good reason to take the threat seriously—such a leap may happen faster than we anticipate, and we still need to future-proof much of the data we send today against unwanted decryption decades in the future.
While the ongoing competition and evaluation by NIST of quantum-safe algorithms will hopefully see its conclusion by the midpoint of this year, the ciphers themselves are, of course, merely one piece of the puzzle. Key management, from a practical sense, relies on the chosen ciphers being supported by the HSM vendors, and the PKI ecosystem needs to migrate as well. While producing X.509 certificates using the NIST candidates has been experimented with for several years, we saw with the migration from SHA1 that the challenge lies in the transition.
The practical problem has two main elements:
- It will take time until all clients support the new algorithms.
- Certificates may be issued with validities spanning years.
Ignoring either of these two points and going for a single atomic switchover can and will have a society-wide impact in many areas.
Fortunately, this problem has not been ignored, and several candidates for transitionary certificates, able to handle both legacy and quantum-safe keys, are in the pipeline. As with the ciphers, each has its pros and cons, and different application areas.
Let’s explore some of the different options below on post-quantum options.
Hybrid certificates
Hybrids, also known as Catalyst or X.509 Alternative, is the simplest and most straightforward of the proposals. The draft is promoted by ISARA, Entrust, and Cisco, and while it was (in)famous some years ago for patent issues, they have since been resolved. As one of its names suggests, it is so far the only proposal that has been standardized as X.509 Alternative Keys and is further being discussed in the ITU-T X.509, X9.146 (20240122), as well as in a non-quantum context in ISO 15118-20.
The Hybrid Certificate Standard proposes adding three non-critical extensions, containing:
- The alternative key
- The alternative signature algorithm
- The alternative signature
In practice, the legacy signature is constructed over the entire certificate, barring the alternative signature, while the alternative signature is over the entire certificate, barring the legacy signature.
The extensions’ non-critical nature means that legacy clients are not impacted by encountering a Hybrid Certificate, while the simplicity of the implementation promotes widespread support by certificate issuers and consumers. In addition, ISO 15118-20 is currently exploring non-quantum use cases where it may be advantageous to provide both a signing and an encryption key in one certificate.
On the day of reckoning, the transition would consist of both server and client agreeing to use only the public key defined in the extension instead of the one encoded into the standard X.509 field.
Keyfactor EJBCA has full support for Hybrid Certificates (as well as Dilithum, Falcon, and Kyber in their current states as candidates) as of EJBCA 8.3.0.
Chameleons
While immediately winning the prize for the most interesting name and concept, Chameleons take the concept of Hybrids further. The Chameleon draft, written by DigiCert and Entrust, involves the issuance of two certificates during the same issuance process:
- A Base certificate
- A Delta certificate
Starting from the end, the Delta certificate would then use quantum-safe ciphers, while the Base certificate contains a legacy public key and the addition of a non-critical extension called a Descriptor. The key for the transition is that the Delta certificate can be derived using the Base and the Descriptor, allowing for a transition while the non-critical nature of the extension doesn’t lock out legacy clients.
The advantage of Chameleons in comparison to Hybrids is that the two certificates can not only have different keys, but also validities and key usages. They may even be revoked independently of each other. This is not only an elegant solution, but provides Chameleons with many other usages, such as being able to derive a SMIME certificate from a TLS certificate. However, the added complexity naturally creates a greater hurdle for issuers and consumers.
Composites
Composite certificates, whose draft is being promoted by Entrust, CableLabs, and D-Trust, is the first proposal to imply a clean break from X.509.
Composites take a different approach by using a complex signature form called a Composite Signature, where several signatures are combined into one construct, which remains valid even if one or more (but not all) of the ciphers become broken. This not only solves the transitionary problem but also takes into account the relative novelty of the mathematics behind most of the NIST candidate ciphers, minimizing impact if a vulnerability is discovered in a few years.
The main disadvantage to Composites may also be viewed as its main advantage, which is the lack of backward compatibility. The pains of deprecating SHA1 remain fresh with many due to inertia on the client side, so forcing a clean break may be the best move for the ecosystem.
Another non-trivial pain point inherited from quantum-safe ciphers is the large keys and/or signatures associated with them (depending on the cipher), making Composites with multiple quantum-safe keys perhaps a poor choice for bandwidth-critical applications.
Merkle Tree certificates
Even in 2024, the blockchain hype still rears its face. No, I kid. As proposed by Google and Cloudflare, Merkle Tree certificates forego including a signature in the certificate itself, largely as a counter to the large signature sizes associated with quantum-safe ciphers, as previously discussed.
Instead, the signatures would be stored in a Merkle Tree, typically in the Trillian-based Certificate Transparency logs already used in the public TLS sphere for many years. This would allow quantum-safe certificates to remain under 1000 bytes in size, which would be a critical boon in TLS and other low-bandwidth environments
This solution does have its drawbacks, though, the most obvious being that a certificate consumer must have connectivity with the log(s) in order to verify the certificate, which also adds another critical element to log uptime. There may also be a significant time delay from issuance to usability for up to an hour, due to the complex computations needed to encode another node to a log – even the authors of the draft acknowledge this as a serious disadvantage.
Summary
Unlike the quantum-safe cipher evaluation, there is no governmental body deciding on which of the proposed standards will become the new norm. While they vary widely in complexity and impact, the proponents of each foresee a use case that they need to solve, so the final decider of where we land will be the market itself.
At Keyfactor, technical challenges are why we brush our teeth and put on our socks in the morning; thus, proposing novel use cases and solutions is merely threatening us with a good time. So, while Quantum Ragnarök looms on the horizon, from where we stand, the future is bright.
Take a few minutes to explore Keyfactor’s PQC Lab, a place for IT leaders, security pros, and developers to learn, explore, and prepare for the post-quantum world.
