Certificados Quantum-Safe: ¿qué son y qué quieren de nosotros?

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.  

El problema práctico tiene dos elementos principales: 

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

Certificados híbridos

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.  

La norma sobre certificados híbridos propone añadir tres extensiones no críticas, que contienen:

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

Camaleones

Aunque ganaron inmediatamente el premio al nombre y concepto más interesantes, los camaleones llevan más lejos el concepto de híbridos. El proyecto Chameleon, redactado por DigiCert y Entrust, implica la emisión de dos certificados durante el mismo proceso de emisión:

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

Compuestos

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.  

Certificados Merkle Tree

Incluso en 2024, el bombo del blockchain sigue asomando la cabeza. No, es broma. Tal y como proponen Google y Cloudflare, los certificados Merkle Tree renuncian a incluir una firma en el propio certificado, en gran medida para contrarrestar los grandes tamaños de firma asociados a los cifrados de seguridad cuántica, como ya se ha comentado.

En su lugar, las firmas se almacenarían en un árbol Merkle, normalmente en los registros de transparencia de certificados basados en Trillian que ya se utilizan en la esfera pública de TLS desde hace muchos años. Esto permitiría que los certificados de seguridad cuántica tuvieran un tamaño inferior a 1.000 bytes, lo que supondría una gran ayuda en TLS y otros entornos con poco ancho de banda.

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. 

Resumen

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.  

En Keyfactor, los retos técnicos son la razón por la que nos lavamos los dientes y nos ponemos los calcetines por las mañanas; por tanto, proponer casos de uso y soluciones novedosas no es más que amenazar con hacernos pasar un buen rato. Así pues, aunque el Ragnarök cuántico se vislumbra en el horizonte, desde nuestro punto de vista, el futuro es brillante.

Tómese unos minutos para explorar Keyfactor's PQC Lab, un lugar para que los responsables de TI, los profesionales de la seguridad y los desarrolladores aprendan, exploren y se preparen para el mundo post-cuántico.