7 Crucial Questions About Quantum Computing and Cybersecurity

What Is Quantum Computing?

Quantum computers take advantage of the very nature of quantum physics to create an entirely new computing paradigm, unlike the traditional 0/1 gated computers we have been using since the 1960s. Instead, they run on quantum bits (known as qubits), which can superpose and entangle themselves in order to perform multiple processes simultaneously.

Quantum computing as we know it was greatly aided and inspired by a piece of mathematics named Shor’s Algorithm. Revealed by Peter Shor in 1994, Shor’s Algorithm provides a roadmap for using a quantum computer to aid in the factorization of prime numbers. The impact of this cannot be overstated, as both RSA and ECC cryptography depend on the difficulty of the factorization of random numbers to remain secure. Quantum computing reduces the time required to break these cryptographic schemes by a great many orders of magnitude, making it not only practical but inevitable that quantum computers will render both RSA and ECC unusable due to security concerns.

Not all aspects of our standardized cryptographic systems are subject to Shor’s Algorithm. Popular hashing algorithms, such as SHA-256 and symmetric encryption algorithms, including AES, do not rely on prime numbers and are therefore not at risk of being broken by quantum-computing-enabled attacks using Shor’s Algorithm.

The approach to defeating these schemes using quantum computers was described by Lov Grover in 1996 using what is known as Grover’s Algorithm. Though Grover’s Algorithm does significantly reduce the time required for a quantum computer to defeat AES crypto and SHA-256 hashing using a brute force attack, the required time to break remains sufficiently long enough so these algorithms are not considered realistic attack vectors using foreseen quantum computing architecture and brute force attacks.

How Will QC Impact our Existing Cryptographic Systems?

Currently, all commercially available hardware, software, and services that depend on Public Key Infrastructure (PKI) take the presence of RSA or ECC encryption algorithms as a given. Likewise, many private encryption development efforts from enterprises, governments, schools, and even at-home hobbyists, assume that RSA and ECC are available.

It would be impossible to catalog the full set of applications, use cases, SaaS offerings, and devices that would be vulnerable in the absence of traditional PKI.

Quantum Computing will render RSA and ECC vulnerable, and new encryption algorithms must be developed to replace them. PKI, as a whole, is not at risk provided new algorithms are deployed to replace RSA and ECC. To the greatest degree possible, any new algorithm must be able to plug and play in our existing environments and applications and just plain work.

Similarly, we cannot overstate the need for our new cryptography to be proven against cryptographic attacks. RSA and ECC schemes have protected the world’s most valuable information targets for decades without anyone discovering a way to fundamentally undermine them using available computing architectures. In fact, ECC did not gain widespread acceptance until the discovery of a proof of Fermat’s last theorem in 1995, as that was required for the community to become convinced that no crafty attack against the algorithm was waiting to be discovered.

Now industry, academics, and governments will be rushing to choose and deploy new algorithms to replace these proven, battle-hardened schemes. If it’s possible for a math genius at a chalkboard to discover a way to fundamentally undermine the security of a chosen algorithm, the effects will be devastating. To prevent that outcome, all candidate algorithms must be thoroughly investigated. For that reason, NIST (National Institute for Standards and Technology) is currently leading efforts to examine potential replacement crypto algorithms.

Everyone is talking about the “Quantum apocalypse.” What do people really mean by that? Is it real or just FUD?

The Quantum apocalypse, or “Z date,” is the day when a quantum computer with enough computing power to defeat current cryptographic algorithms has been developed, rendering current encryption schemes obsolete and allowing information protected with current encryption schemes to be compromised.

Given the current state of quantum computing and recent rates of progress, it is generally unexpected that a quantum computer that can compromise RSA 2048/4096, ECC or comparable discrete logarithm-based public key cryptosystems will be built within the next decade.

Even with quantum computers that can decrypt current cryptographic ciphers is more than a decade off, the hazard of such a machine is high enough — and the time frame for transitioning to a new security protocol is sufficiently long and uncertain — that prioritization of the development, standardization, and deployment of post-quantum cryptography is critical for minimizing the chance of a potential security and privacy disaster.

We must start now if we are to have new, quantum-resistant crypto schemes in place by the time a quantum computer is available.

If security algorithms like SHA and AES are not impacted by quantum computing, why don’t we just switch to those algorithms?

A secure communication or data protection scheme relies on different types of encryption algorithms and hashing algorithms to perform different operations. 

SHA256 is a hash algorithm. It is like a CRC on steroids. It takes input (a file, a stream of data from communication, etc.) and computes a mathematical fingerprint of the data. If you change 1 bit and rerun the hash algorithm, you will get a very different fingerprint or result. Hashing is used to validate that a data file has not changed. It is used to support secure communication (specifically signing and signature validation operations). SHA256 is the current widely used standard hash algorithm. Others are available, but this is the main one in use. This algorithm is not susceptible to Shor’s algorithm. SHA hashing supports secure communication but does not replace RSA or ECC encryption algorithms.

There are two types of encryption algorithms: symmetric and asymmetric.

AES is a symmetric encryption algorithm. With AES, both the party encrypting the data and the party decrypting the data use the same key. AES is robust, secure and fast, so it is a great solution. Also, it is not susceptible to Shor’s algorithm. But there is a problem. To use AES, both parties need to have the same key. Before we can start communicating securely using AES, we need to make sure both parties have that same key. We cannot use AES for this. The way to securely share the key is with asymmetric encryption.

Asymmetric encryption is also known as public key encryption. It uses a keypair which consists of a public key and a private key. I can encrypt something with my private key and send it to you along with my public key. You then use my public key to decrypt that data I encrypted with my private key. Public key encryption is the foundation for PKI (Public Key Infrastructure), which is the process of issuing certificates so that you know who owns the public key.

A certificate includes the public key and information about who owns and has the rights to use the public key. For example, a certificate could identify amazon.com as the website using the specific public key. We use asymmetric encryption to share the AES key. A TLS handshake, for example, uses asymmetric encryption to share an AES key that will be used to encrypt communication for a single TLS session. A new AES key would then be used for the next TLS session.

Asymmetric encryption is great for doing key exchanges, but it is prohibitively slow, so we only use it to encrypt small amounts of data (the key exchange), so we can switch over to AES for the rest of the session. Most existing asymmetric encryption algorithms (i.e., RSA, ECC algorithms) use large prime numbers to create keys. Factoring prime numbers is computationally expensive, making it very hard to break the keys. Shor’s algorithm and quantum computing change that. They provide a method to factor large prime numbers much more quickly, making it possible to break asymmetric encryption, discover the AES key, and decrypt the communication stream

Are there solutions available yet to overcome the quantum computing threat? If not now, when will they be available?

To help the industry arrive at one or more legitimate alternatives to RSA and ECC, NIST has created its Post-Quantum Cryptography project. The project is designed to motivate and coordinate the efforts of academia and industry to identify and vet potential next-generation cryptographic schemes with an eye toward arriving at one or more algorithms that are reliably demonstrated to be safe from defeat by advances in quantum computing.

NIST divided its Post-Quantum Cryptography project into phases, or “Rounds:”

Round 1 focused on information gathering. The equivalent of a community brainstorm, Round 1 collected as many potential cryptographic candidates as the community could muster. Round 1 received 82 submissions, which, in December 2017, NIST culled down to 69 that it deemed “complete and proper.”

NIST divided these candidates into four groups based on their fundamental approach: Lattice-based, code-based, multivariate, symmetric-based, and “other.” NIST suggested the merger of similar candidate algorithms where it appeared that teams could profitably work together to integrate the best parts of their approaches, dropping the number of candidates to 26. These were announced in January 2019 at the beginning of Round 2.

Round 2 concentrated on testing the Round 1 candidates for cryptographic viability. In particular, candidates had to prove at least as hard to break for both binary and quantum computers as AES128, AES192, and SHA256 are. This phase concluded in August 2019.

NIST has announced the results of Round 2, with more than 20 candidates having met the requirements. NIST describes these candidates as being “quite good, and quite diverse,” and states that there is no obvious best choice.

NIST has suggested that more research and dialog are needed, including an examination of the relative importance of success criteria. The institute predicts that this examination will require two-to-three years and targets 2022 for publication of a new standard.

NIST is not the only effort in this regard. The appropriately skilled individuals at universities and think tanks continue to put cycles against these questions, and IT industry providers like Sectigo are placing a strong emphasis on the tools and services necessary for the rapid adoption of new algorithms when they are ready.

Do I need to worry about this now, or can I wait and address this later?

Quantum computers are definitely coming, and they will render the digital world’s cryptographic underpinnings insecure. It is not a matter of if, but when. Though the exact timing of the Quantum Apocalypse is not — and cannot be — known, by any reasonable estimate, we need to be focused on finding and deploying new cryptographic alternatives as soon as possible.

Leaders in research, government, and industry are all putting their weight behind the effort to investigate, select, and roll out new cryptographic standards in time to prevent damage to the world’s digital economy. It won’t be a quick or easy process, but it is a vital one.

What do I need to be doing now to future-proof my systems?

In August 2019, NIST suggested that the academic community needs two-to-three years to vet candidate algorithms to replace RSA and ECC. Once this step is complete, we can begin looking at deployment options. However, most projections of the progress in quantum computing assume that research and manufacturing methods remain similar to what they are today. They do not account for the possibility of breakthrough “Eureka” moments in either the production of quantum computers or the methods of using them to attack these cyphers.

To future-proof your systems, you need to understand the lifetime of the systems you are utilizing and how long data produced by these systems needs to remain safe. For systems that will be in use for more than 8-10 years (based on current projections of the date of the quantum apocalypse) and systems that produce data that must remain safe for more than 8-10 years, you need to begin planning to migrate to quantum-safe encryption algorithms. You can begin implementing solutions that automate certificate management and that support crypto agility, allowing you to more easily move to post-quantum crypto algorithms as they become available.