Post-Quantum Cryptography

Preparing for a quantum-safe future

Almost all digital communications are secured by three cryptographic systems: public key encryption, digital signatures, and key exchange.

In today’s Public Key Infrastructure, these systems are implemented using RSA or ECC asymmetric cryptographic algorithms. RSA and ECC cryptography rely on something called a computational hardness assumption—the hypothesis that a theoretic number problem (such as integer factorization or the discrete logarithm problem) have no efficient solution. However, these assumptions were based on the processing power of classical computers.

In 1994, Peter Shor demonstrated that asymmetric algorithms that rely on a computational hardness assumption could be broken very easily with a sufficiently powerful quantum computer and a specific algorithm, later named Shor’s algorithm. In fact, a quantum computer with enough qubits and circuit depth could crack asymmetric algorithms instantly. A study published by the ASC X9 Quantum Computing Risk Study Group estimated these exact requirements:

Algorithm Required logical qubits Required circuit depth
RSA-2048 4700 8 10^9
ECC NIST P-256 2330 1.3 10^112

For a detailed explanation of Shor’s algorithm and how quantum computers can break asymmetric encryption, watch this video.

Most experts estimate that, within the next 20 years, a sufficiently powerful quantum computer with the required qubits and circuit depth to crack RSA and ECC keys will be built.

Two decades might seem like a long time, but keep in mind that the PKI industry we know today has taken roughly the same amount to get here. According to the NIST Post-Quantum Cryptography project, "there is unlikely to be a simple ‘drop-in’ replacement for our current public-key cryptographic algorithms. A significant effort will be required to develop, standardize, and deploy new post-quantum cryptosystems."

This is why DigiCert has started working with several post-quantum industry players now, in order to help create a PKI ecosystem that is quantum-safe and agile enough to face future threats.

Quantum attack vectors

The first step to effectively protect against these future threats is to identify the various attack vectors posed by a post-quantum threat landscape.

TLS/SSL handshake

Quantum computers pose the greatest threat to asymmetric cryptographic algorithms. This means the cryptographic system used to digitally sign certificates and handle the initial SSL/TLS handshake are both potential attack vectors.

Fortunately, both NIST and ASC X9 assert that symmetric cryptographic algorithms (such as AES) used to create the session keys for securing data in transit after the initial TLS/SSL handshake appear to be resistant to quantum computer attacks. In fact, doubling the bit length of a symmetric key (e.g., from AES-128 to AES-256) seems to be enough to protect against quantum computer attacks. This is because symmetric keys are based on a pseudo-random string of characters and would require the use of a brute force attack or exploiting a known vulnerability to break the encryption, as opposed to using an algorithm (e.g., Shor’s algorithm) to break asymmetric cryptography.

This simplified TLS/SSL handshake diagram highlights which actions are at risk to quantum computer attacks and which are safe.

TLS/SSL handshake using current asymmetric cryptographic algorithms (RSA, ECC) and AES-256

This attack vector threatens the initial communication with servers using end-entity digital certificates. While this is still a pretty big threat, it’s probably not the most dangerous attack vector.

Even with a powerful enough quantum computer, the resources required to calculate a certificate’s private key is still considerable. Because of this, it’s safe to assume that no single end-entity digital certificate is important enough to warrant a quantum attack. Not to mention, it’s relatively trivial to re-key and re-issue an end-entity certificate.

Chain of trust

Probably the most dangerous attack vector posed by quantum computers is the chain of trust (certificate chain) used by digital certificates. RSA and ECC asymmetric cryptographic algorithms are used in every level of the chain of trust­­–the root certificate signs itself and the intermediate certificate, and the intermediate certificate signs the end-entity certificates.

If a quantum computer were able to calculate the private key of an intermediate certificate or root certificate, the foundation that PKI was built on would crumble. With access to the private key, a threat actor could issue fraudulent certificates that would be automatically trusted in browsers. And unlike an end-entity certificate, replacing a root certificate is anything but trivial.

Quantum-safe cryptographic systems

Before changes to the current PKI cryptographic systems can happen, replacement cryptographic systems need to be identified. While several quantum-safe cryptographic systems do exist, further research and study is needed before they can be relied on to secure sensitive information.

Since late 2016, the NIST Post-Quantum Cryptography (PQC) project has been leading research efforts for quantum-safe cryptographic systems. So far, they have identified 26 post-quantum algorithms as potential replacement candidates. However, much more research and testing are still needed before these cryptographic systems are ready to be standardized and deployed.

According to the NIST PQC project’s timeline, another round of eliminations will happen sometime between 2020 and 2021, with a draft standards made available between 2022 and 2024.

Planning for a post-quantum future

This transition needs to take place well before any large-scale quantum computers are built, so that any information that is later compromised by quantum cryptanalysis is no longer sensitive when that compromise occurs.

NIST PQC project

Because of the time it will take to develop, standardize, and deploy post-quantum cryptographic techniques, DigiCert has started testing the viability of embedding post-quantum algorithms in hybrid certificates using this IETF draft.