Certificats Quantum-Safe - Qu'est-ce que c'est et qu'est-ce qu'ils attendent de nous ?

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.  

Le problème pratique comporte deux éléments principaux : 

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

Certificats hybrides

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 norme de certificat hybride propose d'ajouter trois extensions non critiques, à savoir

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

Caméléons

Tout en remportant d'emblée la palme du nom et du concept les plus intéressants, les Caméléons poussent plus loin le concept des hybrides. Le projet Chameleon, rédigé par DigiCert et Entrust, implique l'émission de deux certificats au cours du même processus d'émission :

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

Certificats Merkle Tree

Même en 2024, le battage médiatique autour de la blockchain continue de faire parler de lui. Non, je plaisante. Comme le proposent Google et Cloudflare, les certificats Merkle Tree renoncent à inclure une signature dans le certificat lui-même, principalement pour contrer les grandes tailles de signature associées aux algorithmes de chiffrement à sécurité quantique, comme nous l'avons vu précédemment.

Au lieu de cela, les signatures seraient stockées dans un arbre de Merkle, généralement dans les journaux de transparence des certificats basés sur Trillian, déjà utilisés dans la sphère publique TLS depuis de nombreuses années. Cela permettrait aux certificats à sécurité quantique de conserver une taille inférieure à 1 000 octets, ce qui constituerait un avantage décisif sur le site TLS et dans d'autres environnements à faible bande passante.

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. 

Résumé

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.  

À l'adresse Keyfactor, les défis techniques sont la raison pour laquelle nous nous brossons les dents et mettons nos chaussettes le matin ; par conséquent, proposer de nouveaux cas d'utilisation et de nouvelles solutions revient simplement à nous menacer de passer un bon moment. Ainsi, alors que le Ragnarök quantique se profile à l'horizon, de notre point de vue, l'avenir est radieux.

Prenez quelques minutes pour explorer le PQC Lab de Keyfactor, un endroit où les responsables informatiques, les professionnels de la sécurité et les développeurs peuvent apprendre, explorer et se préparer au monde post-quantique.