The Rise of Quantum Computers – The Current State of Cryptographic Affairs

Quantum computing is highly desired by the supercomputing community for solving a wide range of problems that are extremely difficult (if not impossible) to solve today. One example of a hard problem that will become much easier due to quantum computing is factoring large prime numbers. This hard problem forms the basis of much of the cryptographic protections in use today. So what happens when this “hard” problem becomes an “easy” problem due to quantum computing? How critical is this issue? Learn more about how quantum computing affects our security future in this guest article from Lee Wilson of Security Innovation.

Guest blogger – Lee Wilson, Security Innovation – www.securityinnovation.com

May 30, 2016

What happened? Why have quantum computers and their impact on cryptography suddenly come to the forefront as a real issue that product developers, standards bodies and governments must address ASAP?

As pointed out in the IBM Center for Applied Insights. “A Quantum of Possibilities: The Business Advantages of Taking the Quantum Leap,” the following areas will be deeply impacted by quantum computers:

• Cryptography
  “The potential impact is enormous. Everything we are encrypting today that is stored somewhere will be decrypted by quantum computers when we have them.” Ray Laflamme, University of Waterloo
• Optimization
  “There will potentially be a big impact on optimization problems in bioinformatics, such as gene sequence alignment, metabolic networks and other areas from quantum devices. This also, of course, means business opportunities.” Alan Aspuru-Guzik, Harvard University
• Measurement
  “A role for quantum technology could be in metrology for the problem of sensing and measuring accurately very small quantities of things or very minute amounts of energy. That’s a promising area where there could be commercial development on the early end of the scale, earlier than 10 years.” David DiVincenzo, Aachen University
• Chemistry
  “It’s going to be a disruptive paradigm shift the moment we are able to actually perform meaningful quantum chemistry simulations with a quantum computer. Because in that moment, quantum computing becomes a predictive tool for chemistry.” Alan Aspuru-Guzik, Harvard University
• Materials science
  “If we improve materials science that would affect many industries. Also there are technologies related to quantum computing, like sensing or better clocks, that could be practically useful.” Aram Harrow, MIT

The technical impediments to achieving a general purpose quantum computer are falling away very rapidly. In 2015, key advances were achieved in quantum computing. The first qubits were fabricated in silicon paving the way for quantum computers built from common and widely available processes. According to team leader Andrew Dzurak, Scientia Professor and Director of the Australian National Fabrication Facility at UNSW:

“We’ve demonstrated a two-qubit logic gate – the central building block of a quantum computer – and, significantly, done it in silicon. Because we use essentially the same device technology as existing computer chips, we believe it will be much easier to manufacture a full-scale processor chip than for any of the leading designs, which rely on more exotic technologies.”

Google and UCSB had an essential breakthrough in how to make quantum computers more stable and find and fix errors. In particular, they have figured out how to stabilize an array of nine qubits. An important insight that this experiment revealed is that a group of qubits becomes more stable the more qubits you connect. That means that huge arrays made of thousands or even tens of thousands of qubits might actually yield a successful quantum computer some day:

“MIT physicist Scott Aaronsen pointed out in his article that this experiment can be considered as completing 3.5 of the 7 steps needed to build a working quantum computer. In other words, we’re half way there.”

From 2016, the Harvard Business Review says:

“While you won’t be able to buy a quantum computer in 2016, it’s a trend worth watching. Researchers at IBM’s experimental quantum computing group have begun to unlock difficult problems in quantum computing, such as detecting errors. Recently, D-Wave Systems announced that it broke the 1,000 qubit barrier, which (if true) would make it the most powerful computer on the planet. Now, IBM, Microsoft, Hewlett-Packard and Google, as well as D-Wave, are trying to figure out how to advance and commercialize the technology.”

In a certain sense, this Harvard Business Review article – as optimistic as it is on quantum computing – has already been shown to be too conservative. IBM just announced that they have a small (five qubit) quantum computer available as a cloud service. As the following quote from Techtarget.com indicates, IBM doesn’t have to scale it up very far to rival today’s supercomputers.

“There are limitations to IBM’s quantum computing cloud service. It still runs on only five qubits, which are the quantum computing counterparts to traditional, binary bits. Experts estimate that it could take a device running between 50 and 100 qubits to surpass the capabilities of today’s fastest super computers.”

One of the areas identified in the IBM report to be deeply impacted by quantum computing was cryptography. General purpose quantum computers with several hundred qubits will be able to break today’s asymmetric cryptography with almost no effort. That means that everything using our current “classic” public/private key cryptography (RSA, ECC, Diffie-Hellman….) will be catastrophically broken. Of all the potential capabilities of quantum computers, the cryptography-breaking capabilities of general purpose quantum computers have gotten the greatest attention. Michele Mosca, Chairman of the Institute for Quantum Computing, says:

“Harnessing the power of quantum mechanics in large-scale quantum computers will allow us to solve many valuable problems for humanity, but we must first take the catastrophic impact of breaking cybersecurity off the table by developing and deploying a suite of quantum-safe cryptographic tools before quantum computers arrive.”

In recognition of this emerging reality, the Kaspersky Security Bulletin 2015 announced that “The Cryptopocalypse is Nigh.” Our job as security professionals is not to stop the cryptopocalypse. Rather, it is to make all of our cybersecurity quantum-safe so we can weather the security hurricane that quantum computing represents.

How do quantum computers break “classic” cryptography? What are the attack vectors on my communications? What are the attack vectors on my key management?

There are two quantum algorithms that directly impact the strength of classic cryptography in use today:

• Grover’s algorithm is a quantum speed up of the search algorithms run on classical computers today. Quantum computers running “Grover’s Search Algorithm” will effectively cut the cryptographic bit strength of symmetric cryptographic algorithms in half.
• Quantum computers running “Shor’s Algorithm” will be able to break today’s asymmetric (public/private key) cryptography. Shor’s algorithm is a combination of a classic computer algorithm with a quantum algorithm.

The data from the IQC shown in this chart sums up the net impact to cryptographic security posed by full-scale, general-purpose quantum computers.

As you can see, the impact of Shor’s algorithm is devastating, perhaps unbelievable. A basic understanding of quantum computing makes the impact of Shor’s algorithm less of a mental leap.

The basic components of classical and quantum computers, cbits (classic bits), qubits (quantum bits) and gates, are most easily understood when we put them in the same common, underlying mathematical framework. The next diagram shows how we can represent classical bits (and pairs of bits) in quantum computing notation.

Our “0”b and “1”b used in today’s computers are identical to the |0> and |1> states in a quantum computer. Those bits (or single bit states) can also be expressed in a 2×1 matrix. The first bit of the two bit vector is the probability that the state of the cbit is “0”b. The second bit is the probability that the state of the cbit is “1”b.

Examples are also given for how we write states and matrices for pairs of bits |00>, |01>, |10> and |11>.

If you are familiar with the logic gates used in today’s computers, those same logic gates can be expressed as matrices as shown in the diagram. Notice in the “AND” example how the operation can ultimately be expressed as the multiplication of the vector representing the input state with the matrix representing the AND gate.

Single bits and pairs of bits are shown in this example. This can be scaled up to qunibbles (4 bits), qubytes (8 bits), quwords (32 bits). The expression of all of these as vectors is often a confusing hurdle for those new to quantum computing. A single qubit (or cbit) is represented by a two bit vector, a pair of qubits as a four bit vector, a qunibble as a sixteen bit vector, etc.

In summary, all of the logic we do in classic computers today can also be fully expressed using linear algebra as shown. In quantum computers, this is the notation we’ll use. An n-bit long qubit (or cbit) vector is expressed as a vector of 2ⁿ  In a cbit vector, one of the elements will be a 1 and all the others will be 0’s since there are no probabilities involved other than 1 or 0.   |01> will always be [0 1 0 0] in a classical computer. |11> will always be [0 0 0 1] in a classical computer. In a quantum computer, where we are expressing qubits, all the elements of the qubit vector end up being probabilities. These vectors will finally reduce to vectors that look like what we see in the world of cbits when the computation is done and the result is measured.

In this diagram, we take this same notation and expand it to become a quantum qubit, ├ |ψ⟩, which is able to assume values other than 1 and 0 during computation. This, in part, is how quantum computers achieve their effective massive parallelism. For classic computing, the elements of the 2×1 matrix shown, c0 and c1, can only be 0 or 1.  In a quantum qubit, they can assume many values.  ├ |ψ⟩ can take on any of the values on the Bloch Sphere – not just |0> and |1>. When you initially load the quantum computer and you read out the result at the end of the quantum operation, the Bloch Spheres will be |0> or |1> – you’ll never read out or write in ├ |ψ⟩ with a quantum computer.   But when the quantum algorithm is running and you haven’t read the result yet, the qubits really are ├ |ψ⟩. This is where the quantum “spookiness” (in the words of Albert Einstein) comes in.

This diagram shows some of the very basic quantum gates that operate on one qubit. Notice that the one bit gates effectively cause rotations of the Bloch Sphere to accomplish the desired changes in the qubits. If you rotate a qubit π radians (1800) around the x-axis of the Bloch Sphere – you invert the value of the qubit.  Also, notice that the logic gates are expressed as matrices.

With swap gates you can exchange qubits without changing them.   Quantum control gates allow you to do the quantum equivalent of the well-known classical programming “if-then” statement. Many more gates can be realized (just like in a classical computer). As an example of such additional gates, a QFT gate (Quantum Fourier Transform) will be needed for Shor’s Algorithm.

Now we understand qubits and quantum gates a bit (no pun intended), but we still haven’t answered how this vast quantum “speed up” occurs which causes very hard problems to be solved in record time. This diagram provides a basic description for part of that answer.  Qubits provide a very dense storage of all the possible states of n bits. The quantum algorithm also works using the principle of superposition. We’ll discuss this concept next as we explain Shor’s algorithm.

Now, we’re ready for Shor’s algorithm. Given what we’ve learned,
you can get a sense of what it is doing and how it is combined with classic computation to achieve its goal. In the quantum computer portion of Shor’s algorithm, the QFT (Quantum Fourier Transform) does the hard work. The “measurement” gates shown in this diagram are symbols for the function of reading out qubits.  This act of measuring the quantum computer turns the qubits into their final values comprised of 1’s and 0’s. Before that measurement is taken – the quantum computer is basically the very famous “Schrodinger’s Cat.” To understand this, we can do a thought experiment where the quantum computer is solving the problem of a cat in a quantum mechanical box. The answer we are trying to determine is whether the cat is dead or alive. During the computation of the problem, the cat exists as a superposition – while in the closed box, the cat is in both states at once – both dead and alive. When we finally make our measurement (open the box), this superposition will collapse into the answer that either “the cat is alive” or “the cat is dead,” but not both.

What are some of the attack vectors that a hacker with access to a quantum-computer can employ? Here are a few:

• Today’s classic signing algorithms are based on asymmetric cryptography (RSA, ECC, etc.). Shor’s algorithm running on a quantum computer will allow an attacker to derive your signing keys.

The attacker can sign forged documents and no one will be able to tell they are not from a legitimate source. The attacker can create malicious code and send it to your customers as a trusted code update. Attackers can sign certificates as if they are a legitimate Certificate Authority (CA). Certificates are fundamental to how we authenticate and they will be completely compromised.

We need to re-tool our PKI (Public Key Infrastructure – certificates, certificate authorities, etc.) to quantum-safety as quickly as possible.   This is a VERY serious attack.  We effectively won’t be able to authenticate – at least not in the fashion we are accustomed to – in a post-quantum world if we don’t re-tool to quantum-safe cryptography.

• The RSA, ECC or Diffie-Hellman negotiations used by SSL, TLS, SSH, etc. in your secure communications will be broken exposing the symmetric keys.

For many protocols and applications, there will be no need to crack the symmetric cryptography used for privacy on the bulk data being transferred or stored. The attacker will decrypt the asymmetric cryptography that negotiates the symmetric key being used to encrypt the bulk data and get the key in the clear. That negotiation is often part of the overall transfer of the bulk encrypted data.

• If recorded and data-vaulted, any TLS/SSL communications performed without quantum-safe cryptography will be easily deciphered.

There are many secrets being sent over the public network today that are already in danger of being decrypted by quantum computers. Many of these secrets are expected to remain private for 20, 30, 40 or more years. Here are some examples of information that needs to remain secret for a long time:

– Medical records
– Financial records, money transfers, equity trading, bank-to-bank transactions…
– Biometric, biographical and current information  used to authenticate individuals
– Corporate secrets
– Government secrets
– Personal correspondence
– Cryptographic key material

We know that the NSA is data-vaulting selected communications today. It is believed that such data-vaulting is widespread and the advent of quantum computing makes data-vaulting attacks even more attractive since there is now the real prospect that the stored data can be decrypted with quantum computers and then data mined.

The loss of data secrecy due to quantum attacks on data-vaulted information may be a substantial legal liability for companies that have not taken appropriate steps against quantum computing threats in the present. In a recent article on healthnetsecurity.com, information was given on a recent report by the “Information Governance Initiative” (IGI) discussing the full extent of this problem and the major exposure it represents:

“New research has revealed that the majority of organizations do not have a coherent long-term strategy for their vital digital information even though virtually all of them (98%) are required to keep information for ten years or longer.”

“While 97% of information professionals understand the need for a specialized approach to these assets, only 11% are storing them in systems specifically designed to ensure long-term protection and access. This gap has economic, legal, and business competitiveness implications.”

• Key management software in many cases is also using these asymmetric cryptographic algorithms to keep keys private.

Many key management protocols use asymmetric cryptography. If your key management protocols are running over a public network, an attacker can record those transactions for decryption by a quantum computer.

What does all of this do to the authentication schemes I’m using? How does this affect electronic signatures? What does this do to software distribution and other things that I sign?

All “classic” signing algorithms are based on their kindred asymmetric cryptographic algorithms. They’ll be broken by quantum computers – and your private key will be exposed – in fifteen minutes or so according to the previous observations cited from Airbus. Certificates will be forge-able. The world’s PKI will be broken. The PKI and the certificates that are part of it are essential to our most prevalent authentication schemes. Such attacks would depend on hackers having broad access to quantum computers. Hackers will be able to buy quantum computer access as a cloud service. Bill Gates predicts the availability of quantum computers as a cloud service:

“Microsoft and others are working on quantum computing. It isn’t clear when it will work or become mainstream. There is a chance that within 6-10 years that cloud computing will offer super-computation by using quantum.”

IBM is already providing free cloud access to a small quantum computer today. So, in some sense Gates prediction has already come true. Most of the fundamental research has now been done, quantum computers have largely made the move from research to development. Going forward, the challenges are just scaling these machines up. Bottomline: Our most prevalent signing and PKI-based authentication systems will be obsolete and dangerously exposed if they are not re-tooled for quantum-safety.

How does this affect my hardware, my systems management, my storage, my PKI?

Hardware Security Modules (HSMs) and Trusted Platform Modules (TPMs) do not support quantum-safe cryptography today. You’ll either need to buy new HSMs (with new supporting software) or get upgrades to your existing HSMs – if such field upgrades are possible. If your asymmetric cryptography is embedded in your other hardware and cannot be updated to quantum-safe algorithms, you’ll need new hardware. Systems management and storage use “classic” cryptography that will be broken catastrophically.

All your software and PKI will need to be updated to remove the classic asymmetric cryptography and replace it with quantum-safe cryptography. Your data encrypted with symmetric algorithms will need to re-keyed with double the key bit-strength.

What is the impact on Internet of Things (IoT)?

The issues are the same for IoT as they are for mobile devices, embedded devices, clients, servers, etc. IoT vendors in many cases do not have a large security legacy and can move to quantum-safe cryptography early in their product cycles.

Industrial IoT vendors need to be especially conscious of the post-quantum era cryptography problem. These devices often have to be survivable for up to 30 years with only software updates. They often support critical infrastructure or pose significant safety risks if compromised. Moving these devices to quantum-safe cryptography ASAP is well advised.

How big and how fast does a general purpose quantum computer have to be to break today’s crypto? How can you be sure the crypto breaking will even work if quantum computers don’t yet exist?

Cryptography is based on an underlying hard mathematical problem called security reductions. Figuring out the security reduction for today’s “classic” asymmetric algorithms will be breathtakingly fast for quantum computers. The simplest way to describe it is that quantum computers achieve a sort of complete parallelism on certain problems. They don’t have to have a large number of machines looping for massive periods of time. They don’t have a cycle time. If you have enough qubits and they can be initialized, configured and read correctly, the quantum computer instantaneously computes the answer.

“A fully configured quantum computer would be able to crack today’s most sophisticated encryption in about 15 minutes. To do the same task it would take all the normal computers in the world working together for longer than the universe has existed.”
– Paolo Bianco, Airbus Group’s Manager for Global Research Co-operation

This still sounds pretty “researchy.” Why should I focus on this now? What are the most realistic assessments on when general purpose quantum computers that can attack cryptography will arrive?

Members of the Microsoft quantum computer team stated in 2015 that “Recent improvements in control of quantum systems make it seem feasible to finally build a quantum computer within a decade.”

In Australia, the University of New South Wales began fabricating quantum computer components in silicon and announcing associated large scale quantum computer architectures last year. This work in silicon presages an uncomfortably close time frame when easily fabricated and easily deployed quantum computing devices become available. The UNSW assertion is that the fabrication techniques, fundamental building blocks and large scale computer architecture needed to begin engineering commercially viable general purpose quantum computers are now in place.

The following chart has the nearer term and somewhat longer term projections of when crypto cracking quantum computers will appear. The nearer term projections come from announcements made in 4Q 2015. The projections out further on the time line were made from data provided in 1H 2015. The rate of perceived progress in the creation of quantum computers is clearly accelerating. Prominent security experts such as Bruce Schneier are now reassessing the threat to cybersecurity from quantum computers:

“I do not stand by my 30-40-year prediction. The NSA is acting like practical quantum computers will exist long before then, and I am deferring to their expertise.”
– Bruce Schneier, Aug 2015

The red line represents projections made by Microsoft and others predicting general purpose quantum computers will be present in about ten years. The green line represents a more conservative estimate done by the Institute for Quantum Computing (IQC). The quantum risk analysis, security standards work, hardware/software retooling and re-deployment of all quantum-safe cybersecurity should be done before large general purpose quantum computers become a possibility. If they exist, and you are not re-tooled to quantum-safe cybersecurity, the cyber-attacks that can be mounted against you are potentially devastating. In the near future, you will only be cyber-safe if you are quantum-safe. That’s an enormous amount of work to do and the graph demonstrates that the probability of such machines existing starts in the early 2020’s and grows rapidly. DWave has 1000 qubit quantum computers today, but they are not general purpose architectures at this point.

All I have to do is make my keys bigger and the current cryptographic algorithms will be fine.

This argument/misunderstanding comes up a lot and is a source of much confusion, so it is worth reiterating with some clarification.

Increasing the size of asymmetric cryptographic keys will not provide you any reliable defense against quantum computers. The success of a quantum computer attack against asymmetric cryptography using Shor’s algorithm is not reduced in an appreciable way with the key size.

The complexity of Grover’s Algorithm against symmetric cryptography (3DES, AES, etc.) does scale with key size, but since asymmetric cryptography is typically used to establish and negotiate symmetric keys “the point is moot.” Please don’t fall prey to this misconception. You want to double the key size (re-keying your current data) on your symmetric cryptography, but if your key management protocols and key negotiation protocols have not been re-tooled for quantum-safety you probably aren’t solving your post-quantum security problems.

What does this do to FIPS 140-2 and SP800-131a? What is the IETF doing?

Currently, FIPS 140-2, NIST SP800-131a, the IETF TLS Specification, etc. do not specify any quantum-safe cryptographic algorithms. To fix the PKI (Public Key Infrastructure), these (and other) standards must be updated. Given the recent sprints in quantum computer advancement those activities are moving more slowly than is needed. The Institute for Quantum Computing (IQC) has already pointed out that quantum computers are going to arrive before the retooling to quantum-safety is complete.

For those who wish to protect themselves in the short-term, take heart. There are some hybrid techniques which can be used now to retain FIPS compliance and achieve quantum-safety. The following excerpt from Microsoft explains this:

“Does turning the FIPS bit on mean all encryption will use only FIPS 140-2 validated algorithms?
In some cases, noncompliant algorithms or processes are allowed in a FIPS 140-2-compliant application. For example, data may be encrypted by using a noncompliant algorithm if, in this encrypted form, the data remains within the application, that is, the data is not exported in this form, or if the data is further encrypted (wrapped) using a FIPS-compliant algorithm.”

FIPS 140-2 does allow you to mix quantum-safe algorithms with FIPS 140-2 approved algorithms without losing FIPS 140-2 compliance. The IETF has Internet Drafts available for a quantum-safe hybrid approach for modifying the TLS handshake to make it unbreakable by a quantum computer. This technique will protect the privacy of keys used in communications sessions from quantum attacks.

How are post-quantum cryptographic algorithms different? How do you know they can’t be broken too?

“Computer Science is no more about computers than astronomy is about telescopes.”
– E. W. Dijkstra

The computer science and mathematics of quantum computing is actually very mature. Shor’s algorithm has been around since 1994. The computer scientists have been waiting for the hardware community to build them a machine that will implement their computer science. Will it continue to advance? Sure. But, the mathematics and computer science of quantum computing has been with us almost twenty five years. It is a separate and much more mature topic compared to the art of how we actually engineer a computer to achieve that architecture.

Here’s a little light reading if you’d like to gain a better understanding of the computer science of quantum computing:  Noson S. Yanofsky, Mirco A. Mannucci. (2008). Quantum Computing for Computer Scientists. Cambridge University Press.

Thanks Lee for sharing these insights about the advances in quantum computing and possible impacts on security. It is becoming apparent that some of the security infrastructure that we have come to rely on will be changing in the face of advances in quantum computing. And thanks for checking out ActiveCyber.net! Please give us your feedback because we’d love to know some topics you’d like to hear about in the area of active cyber defenses. Also, email marketing@activecyber.net if you’re interested in interviewing, guest blogging, or advertising with us at ActiveCyber.