Quantum Cryptography for Risk Managers or Shor, Grover, and the Crypto-Apocalypse

By David Gamey - 23 Sep 2021.

According to some, quantum cryptography will revolutionize cryptography, kill our current ciphers, and reveal all our secrets. But if you're a risk manager, you're likely turned-off by claims of an impending crypto-apocalypse. You want to get past the hyperbole to something you can work with. You will want to know how likely this is, how to sort out facts from spin, what kinds of resources are available, how long you've got to prepare, and what preparation and planning do you need to do. You need to understand that quantum isn't just one thing, one risk, or the only risk. Join us as we break it all down for you.

Image Credit: Copyright Intel Corporation

Before we dig in, quantum computing isn’t the only driver of cryptographic change. Regardless of the eventual impact of quantum computing, organizations will still have to manage cryptographic changes. Or put another way, even if workable scalable quantum computers never happen, organizations will need to manage cryptographic change and should be looking at building cryptographic-agility programs.

Quantum Computers have tremendous potential and impact when, and if, we can get them working, overcoming technical challenges, and making them practical. In truth, we don't know when this will happen. We also don't know if we will encounter insurmountable obstacles or if there will be some new breakthrough that will make this happen sooner. However, uncertainty isn’t license for inaction. If we are going to address this pragmatically, we need to understand the playing field and start planning. There are a few things we can say:

  • Quantum cryptography is actually based on several different technologies and some of them are here today. We need to understand these broadly to respond appropriately. The old way to change crypto is slow, expensive, and disruptive. We need to do better.
  • We can't wait until there is a practical quantum computer able to break our ciphers to change our algorithms. We need to change them sooner. We need a plan that addresses our data retention debt. If we wait too long our old cryptograms will be broken and our secrets revealed.
  • Quantum technology is not the only risk to cryptography. Non-quantum cryptanalysis is improving the methods used to attack ciphers and protocols. We need to learn from the last two decades as cryptography will continue to evolve.
  • Cryptographic change happens and in order to adapt it we need to understand both what assets we are protecting and how those assets are protected with cryptography.
  • We want to manage the change, not panic the change. We will need to know where, what, and when changes are needed well in advance.

Generally speaking, quantum computers are misunderstood and some of the cutting edge research is strange to say the least. Understanding something of the technology behind quantum computing is helpful to understanding its impact. However, for our purposes, we don’t want to get too far off the beaten path where quantum computing is entangled with physics and philosophy. Some of the Quantum Computing in Perspective references (below) may help. For a cryptographic perspective, Schneier makes a number of valid points but basically concludes that there is no quantum cryptography crisis and important work is being done to avoid one. Aaronson tackles explaining quantum computing, problem spaces, and enough physics and philosophy to put it all together and provide a glimpse of where this is going. There are some takeaways from all of this:

  • Quantum computers are very specific beasts, they aren’t supercomputer replacements, and they aren’t general purpose or universal.
  • They provide ways to implement specific algorithms. The chandelier-like computers we see in articles are often wired for specific problems. Not all machines can implement all algorithms.
  • The idea of superposed states has been badly explained, the idea of trying everything at once isn’t how it works. There are some fascinating details such as quantum states cancelling each other out and the necessity to rewind, or un-compute, states in a calculation. But for now, we are content to wait for better explanations and observe the results.
  • Quantum algorithms are powerful because they operate in a different problem space than classical computers. In classical computer science, there are discussions of NP complete and Polynomial problem spaces, basically how hard the problem is to solve and how it scales. Introducing quantum effects means that there’s a much larger collection of these problem spaces like BPP and BQP. In the end, quantum computing just scales better – that is, if we can actually make it work at scale.

Many organizations try to exploit marketing buzz and hype with terminology like quantum, AI, ML, blockchain, etc. to gain attention, investors, and opportunities. Additionally, the science of quantum computing is advancing steadily. Consequently, it can be difficult to cut through the noise to get to the relevant information. Below, we break down specific applications of quantum technology that impact cryptography. Hopefully this will help your risk management teams put quantum cryptography into perspective and follow the developments.

Cryptographic-Agility

In simplest terms, cryptographic-agility is the ability to manage risk and quickly deal with cryptographic change regardless if these are due to quantum computing or more conventional advances. Risk managers concerned with the impact of quantum computing will want to ensure they have a mature crypto-agility program that monitors areas of potential change including post-quantum cryptography and advancements in quantum computing.

Existing Asymmetric (i.e. Public Key) Cryptography (e.g. RSA, ECC)

The ultimate quantum cryptanalysis boogeyman is Shor's algorithm. Shor’s has the potential to crush public-key ciphers like RSA and ECC. Estimates in 2019 put a break time on 2048-bit RSA at 8 hours! Of course, the really BIG IF, is building a reliable enough quantum computer. Current machines not only fall dramatically short in qubits but they also can't keep it together long enough to complete the computations. Even if IBM builds their 1000 physical qubit machine in 2023, it will be far short of the 4096 logical qubits or 2M-25M physical qubits required to crack RSA-2048.

Even without quantum cryptanalysis, RSA is eventually doomed. As we move to longer and longer symmetric keys, RSA keys grow exponentially in length. With AES-128 commonly in use, RSA keys require 3072 bits for equivalent strength. AES-256 requires a whopping 15k bit long RSA key for equivalent strength. A paper described quantum resistant RSA with insanely long keys (the same paper also suggested a central key generation authority and created a bit of a controversy in the process).

ECC keys scale linearly but the cipher is still vulnerable to Shor’s algorithm. We could see ECC as an interim algorithm.

Symmetric Key Cryptography (e.g. AES)

Quantum cryptanalysis will also have a major impact on symmetric cryptography. Grover's algorithm provides a huge advance but it's nowhere near the boogeyman that is Shor's. A practical implementation of Grover's means our AES-128 is no harder to break than a 64-bit key basically setting us back over 2 decades. Like Shor’s, Grover’s algorithm also requires a large number of logical qubits (2,953 for AES-128) and that 2 decade reset may not happen for a decade or more. Organizations worried about the long-term viability of 128-bit cryptography should get off AES-128 (and TDEA) as soon as possible. Standards bodies could easily deprecate 128-bit keys. AES-256 will remain as solid post quantum as AES-128 is today. If new 512-bit ciphers are needed, they could be developed going forward.

Grover’s algorithm also impacts pre-image and collision attacks on MACs and Hashes in the same way as ciphers like AES. However, there are already a number of good non-quantum reasons to reconsider many hashing use-cases (See Crypto-Agility).

If Grover’s is as good as it gets, we should not be worried. Of course, cryptographic-agility programs will need to move to stronger symmetric algorithms and pay attention to the retention of old cryptograms derived from shorter keys.

Post Quantum or Quantum Resistant Cryptography

Cryptographers and standards bodies aren't waiting for practical large scale quantum computing to become reality. Work is proceeding to replace the Public-Key encryption and digital signature algorithms are impacted by Shor's algorithm. As noted, symmetric key encryption is not considered at risk.

  • NIST has sponsored a Post-Quantum Cryptography Challenge to select a standard quantum resistant algorithm. This effort has progressed to the third round with 9 Public-Key Encryption candidates and 6 Digital Signatures candidates. The field is further divided into finalists and alternatives. NIST is currently favoring structured lattice schemes. There candidate algorithms have a wide range of key sizes and equivalent key strengths have yet to be documented. Draft standards are expected between 2022-2024.
  • Microsoft and Google have run experiments with HSM vendors.
  • Cloudflare has run experimental pilots to test out different algorithms.
  • The Open Quantum Safe (OQS) project provides an open-source C library for PQC cryptography and also integrates with OpenSSL.
  • The PCI Security Council actively monitors developments in this area for impact on payment systems through their Encryption Task Force and other working groups. The PCI ETF can be reached for questions at ETF@PCISecurityStandards.org.

Key Distribution

Quantum key distribution (QKD) is here today. It provides a method of remotely agreeing keys that provably cannot be eavesdropped without detection. It's very interesting and serves some niche applications. But how practical is it? Where does it fit?

While the keys may be agreed securely, can they be held and used securely? A challenge to the general use of this technology is that the keys are still available to classical technologies. And if the keys are used for classical ciphers, is there any real advantage in general use cases? Most organizations aren’t going to have QKD kit any time soon.

We can also, foresee potential jurisdictional and cross-border issues arising once this technology can be made to work at really long range.

Quantum Key Generation

A recent and interesting development is the use of quantum computers for random key generation. While we haven’t seen a lot on this it’s worth noting that we already have random sources that outperform pseudo-random-number-generators. And as some of the challenges to using this for general applications are similar to QKD, it’s hard to see this as more than fitting a special use-case.

Marketing Buzz and Spin vs. Reliability

Cryptography is not the only application for quantum technologies and there other interesting uses. As with any new technology (e.g. artificial intelligence, machine learning, blockchain) the interest in quantum also generates it's share of spin, hype, and misleading or false claims. Fortunately, the field of quantum cryptography gets a lot of scrutiny and reliable answers are available.

Learn More

Our annotated references broken down by topic. Many of the referenced articles have been covered in our weekly [In]Security News summaries https://controlgap.com/blog?tab=insecurity

Cybersecurity can be difficult, why not let Control Gap guide you. We are the largest dedicated PCI compliance company in Canada.
today and learn more about how we can help you: Get Compliant. Stay Compliant.