The use of Chameleon certificates can support the transition to quantum security on the certificate management side. To achieve fully quantum secure networks, both key agreement and authentication must be made quantum secure.

chamäleon

Certificates are the key to modern secure IT networks

Digital certificates are key to modern IT security. They allow to verify the identity of a person or device in a network and implement digital signatures. They enable the authentication of communication endpoints in secure network connections, e.g. the Internet.
The certificates contain the name and the public key of their owner, as well as what the key may be used for. The certificate authority checks that the public key belongs to the entity in the certificate and confirms this by signing the certificate with another digital signature.
Certificates have an expiration date, they therefore have to be renewed regularly. The trend in the Internet is towards a shorter validity time and renewing certificates within e.g. 90 days. Additionally, certificates may be revoked if they are lost or compromised.
In the following, we focus on the use of certificates in secure network connections such as TLS. Such secure connections occur as part of the public Internet, e.g., when connecting securely to the e-Banking application, as well as in internal company networks. They ensure the correct devices are communicating with each other and the communication line cannot be eavesdropped on.
When initiating a connection, the endpoints will first do a key agreement protocol to agree on a key for encryption. The certificate is used to ensure that the key is established with the expected correct endpoint and not with an adversary, thereby preventing so-called Man-in-the-Middle attacks. The role of the certificate is therefore to ensure authentication.

The quantum threat

Quantum computers are particularly efficient at solving certain mathematical problems, such as factoring numbers and taking discrete logarithms. These problems are, however, exactly the problems the current public key cryptography bases its security on. Solving them quickly allows to break these cryptographic systems.
Public key cryptography is used for key agreement, authentication and signatures; using algorithms such as RSA, (elliptic curve) Diffie-Hellman and (elliptic curve) Digital Signature Algorithm. In the presence of a large-scale quantum computer, these algorithms are considered broken. To be secure against an attacker with access to a quantum computer, they have to be replaced.

Migration to post-quantum cryptography is on its way

Alternative algorithms for key agreement and for signatures (also used for authentication) which base on mathematical problems that are presumed to be difficult to solve by quantum computers have been proposed. In an effort led by NIST [1], a first set of algorithms is now getting standardized in FIPS 203-205 [2].
Several products such as Chrome and Firefox web browsers, Signal, WhatsApp and Zoom have already included a quantum-safe key agreement algorithm that works well without negatively impacting performance. Most users probably did not notice when the application they used migrated to quantum-safe key agreement algorithms, since this simply happened via a software update.
When a secure connection is initiated, the endpoints agree on which key agreement algorithm shall be used. If both endpoints are able to do post-quantum algorithms they can do so. If one or both only support “traditional” algorithms, they will agree to use these algorithms.
In all of the above examples, authentication of the endpoints is still done using “traditional”, not quantum-safe algorithms. Migrating to quantum-safe authentication is slightly less pressing than key agreement since an attack on authentication needs to happen *during* the key agreement process and this component does not need to be long-term secure. Still, to achieve fully quantum-safe networks both key agreement and authentication have to be made quantum-safe.

Making a Public Key Infrastructure quantum-safe is a challenge

Changing the algorithm for authentication is more involved, since the possible algorithms are fixed by the digital certificate. Even if a system is technically able to do novel signature algorithms, they can only be used in connection with a new pq certificate – containing a key for a post-quantum algorithm. In business IT networks a certificate management system, such as essendi xc, can facilitate the process of requesting and issuing a new certificate considerably, nevertheless a software update is not sufficient to implement this change.
To be able to emit new quantum-safe certificates, the certificate authority also needs to be post-quantum-ready. On the one hand because the CA needs to be able to issue certificates for these new algorithms. On the other hand, the signature of the CA should also be quantum-safe to ensure the security of the complete certificate chain.

Not all network components will be able to update, receive a new certificate and switch the settings simultaneously. This begs the question how to handle “legacy” certificates. As long as they remain accepted, the system is not guaranteed to be quantum-safe, so they should eventually be deprecated.
If “old” certificates are considered invalid too early, this may, however, break applications when the establishment of a connection is refused. In order to transition a running system to quantum-safety several types of algorithms will therefore have to be used in parallel, at least for some time.

The issue with the certificates

In a server-client network setting, a server able to do post-quantum algorithms may have a variety of clients connecting to it. Some clients may have post-quantum algorithms enabled and others not. To allow any of them to connect, the server needs to select the authentication mechanism depending on the client and present the corresponding certificate.
There are several ways to represent in a certificate that devices now need to be able to run *either* of a set of algorithms.
One suggestion was to have *one* certificate with several public keys. A possible technical implementation of this construction with an optional extension with alternative public keys was standardized in X.509 10/2019 [3], but is rarely used. This approach has two main drawbacks:

How Chameleon certificates can help

Figure 1: Illustration of a delta certificate and base certificate from [4].

Chameleon certificates are pairs of two related certificates. One certificate is the *base certificate* and the second one is called *delta certificate*.
The delta certificate only contains the fields which are different from the base certificate. This allows to reconstruct two possible certificates from the pair. However, both certificates have a separate ID, allowing to revoke each of them separately.
The reconstruction of the certificates can be done either on the server or on the client side if both parts are available. When done on the server side, the server will create the adequate certificate depending on the algorithms the client supports as indicated during the handshake. That the certificate is derived from a Chameleon Certificate is in this case perfectly transparent to the client.
In this way, the use of Chameleon certificates can support the transition to quantum-safety on the certificate management side. When the “traditional” algorithms shall be decommissioned, it is sufficient to revoke this part of the Chameleon Certificate. The system continues to work with the post-quantum algorithms and their respective certificates. No new certificates have to be issued.

Take home message

While time-pressure is not quite as high, switching to quantum-safe authentication in TLS connections requires a series of necessary changes, from updating and revoking certificates to quantum-ready certificate authorities. Several technical solutions can facilitate the transition: certificate management solutions can automatize the lifecycle management of certificates and Chameleon Certificates enable a soft transition to quantum-safe networks avoiding breaking changes.

[1] https://www.nist.gov/pqcrypto
[2] https://csrc.nist.gov/pubs/fips/203/ipd
https://csrc.nist.gov/pubs/fips/204/ipd
https://csrc.nist.gov/pubs/fips/205/ipd
[3] https://www.itu.int/rec/T-REC-X.509-201910-I/en
[4] Transition to quantum-safe Authentication in TLS, Joshua Drexel, Masterthesis, HSLU 2024; available at https://portfoliodb.hslu.ch/sets/4093acd9-7277-465e-8e14-11a25eb3a2b7

Prof. Dr. Esther HänggiProf. Dr. Esther Hänggi

Our guest author, Prof Esther Hänggi, teaches Information Security Fundamentals and Quantum Computing at the Lucerne University of Applied Sciences and Arts and conducts research in these areas together with industry partners.

More about the Author