Quantum Cryptography for Risk Managers or Shor, Grover, and the Crypto-Apocalypse
Posted by David Gamey on 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.
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.
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.
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.
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
- Cryptographic-Agility (2021) https://controlgap.com/blog/Cryptographic-Agility
Quantum Computing in Perspective:
- Scott Aaronson Talks About What Makes Quantum Computing So Hard to Explain and Why Your Expectations are probably wrong (2021) https://www.quantamagazine.org/why-is-quantum-computing-so-hard-to-explain-20210608/
- NSA Quantum Computing FAQ including discussion of CRQC - “Cryptographically Relevant Quantum Computers” (2021) https://media.defense.gov/2021/Aug/04/2002821837/-1/-1/1/Quantum_FAQs_20210804.PDF
- Quantum computers will not cause all forms of conventional encryption to become insecure (2019) https://kryptera.ca/paper/2019-03/
- Quantum Computing Since Democritus; Aaronson; Cambridge University Press (2013) https://www.cambridge.org/core/books/quantum-computing-since-democritus/197A4CD13738E10AAD787DBB78D8E92C
- Why it might be impossible to build a practical quantum computer (2021) https://www.newscientist.com/article/mg25133493-200-why-it-might-be-impossible-to-build-a-practical-quantum-computer/
- Cryptography after the Aliens Land (2018) – a future looking essay on the cryptography and the impact of quantum technologies https://www.schneier.com/essays/archives/2018/09/cryptography_after_t.html
- Quantum Cryptography: As Awesome As It Is Pointless (2008) – an essay on why quantum computing was (and is) still a long way off https://www.schneier.com/essays/archives/2008/10/quantum_cryptography.html
- Explanation of Shor's from IBM covering quantum modular multiplication, circuits, and quantum composer tool (undated) https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm
- Another explanation and example from the Qiskit open-source SDK (undated) https://qiskit.org/textbook/ch-algorithms/shor.html
- Shor’s algorithm is implemented using five trapped ions (2016) https://physicsworld.com/a/shors-algorithm-is-implemented-using-five-trapped-ions/
- How a Quantum Computer could break RSA-2048 in 8 hours (2019) https://www.technologyreview.com/2019/05/30/65724/how-a-quantum-computer-could-break-2048-bit-rsa-encryption-in-8-hours/
Grover's Unstructured Search Algorithm:
- Explanation of Grover's from IBM covering the oracle and the amplitude amplification procedure, circuits and quantum composer (undated) https://quantum-computing.ibm.com/composer/docs/iqx/guide/grovers-algorithm
- Qiskit example (undated) https://qiskit.org/textbook/ch-algorithms/grover.html
- Another explanation (undated) https://www.quantum-inspire.com/kbase/grover-algorithm/
Post-Quantum (Quantum Resistant) Cryptography:
- Post-quantum cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
- NIST Post-Quantum Cryptography (PQC) Project (2016-2021) https://csrc.nist.gov/projects/post-quantum-cryptography
- Open Quantum Safe project (2017-2021) https://openquantumsafe.org/
- Post-Quantum Cryptography: Current state and quantum mitigation (2021) https://www.enisa.europa.eu/publications/post-quantum-cryptography-current-state-and-quantum-mitigation
- NISTIR 8309 Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process (2020) https://doi.org/10.6028/NIST.IR.8309
- Attack Beyond-Birthday-Bound MACs in Quantum Setting (2020) https://eprint.iacr.org/2020/1595
- IBM demonstrates CRYSTAL a quantum resistant public key cipher and NIST candidate (also has good explanations of the limitations of quantum computing) (2019) https://www.scientificamerican.com/article/new-encryption-system-protects-data-from-quantum-computers/
- The results of a TLS post-quantum experiment are in and the ostrich outperformed the turkey (2019) results https://blog.cloudflare.com/the-tls-post-quantum-experiment/ and introduction https://blog.cloudflare.com/towards-post-quantum-cryptography-in-tls/
- More on NIST’s Post-Quantum Cryptography (2020) https://www.schneier.com/blog/archives/2020/09/more_on_nists_p.html
- NIST Announces 3rd Round Post-Quantum Cryptography (PQC) Standardization Candidates (2020) https://content.govdelivery.com/accounts/USNIST/bulletins/296eed6 and https://www.schneier.com/blog/archives/2020/07/update_on_nists.html
- PQDH: A Quantum-Safe Replacement for Diffie-Hellman based on SIDH (2019) https://eprint.iacr.org/2019/730
- Quantum resistant RSA (2017) – limited utility and controversial – very long keys and suggestions of using a central key generation authority. RSA is based on n=p*q, today n is 4096 bits, to make it work post quantum the primes p & q each have 4096 bits each. To use a symmetric key analogy this is a bit like split keys by using key halves vs. full length key parts. Link and discussion at https://www.schneier.com/blog/archives/2017/05/post-quantum_rs.html
Quantum Key Distribution:
- Wikipedia https://en.m.wikipedia.org/wiki/Quantum_key_distribution
- Quantum Key Distribution: Is it as secure as claimed and what can it offer the enterprise? (2021) https://www.theregister.com/2021/07/06/quantum_key_distribution/
- Scientists Have Made a Quantum Key Distribution Encryptor 1,000 Times Smaller Than What Came Before (2019) http://www.sciencealert.com/scientists-have-made-a-quantum-chip-that-s-1-000-times-smaller-than-before
- Vulnerabilities in Quantum Key Distribution Protocols (2003) https://csrc.nist.gov/publications/detail/nistir/6977/final
Quantum Key Generation:
- AWS researcher merges the power of two quantum computers to help make cryptography keys stronger (2021) https://www.zdnet.com/article/aws-researcher-merges-the-power-of-two-quantum-computers-to-help-make-cryptography-keys-stronger/
- And then there is this (2021) https://physicsworld.com/a/fast-quantum-random-number-generator-fits-on-a-fingertip/
- Example of strong non-quantum random keys using a Geiger counter and some statistics (2017) http://poseidon2.feld.cvut.cz/conf/poster/poster2017/proceedings/Poster_2017/Section_EI/EI_040_Ruschen.pdf
- List of Quantum processors https://en.m.wikipedia.org/wiki/List_of_quantum_processors
- Not all Qubits are equal (Physical vs. Logical) https://en.m.wikipedia.org/wiki/Physical_and_logical_qubits
- Scientists Just Simulated Quantum Technology on Classical Computing Hardware (2021) – the Quantum Approximate Optimization Algorithm (QAOA) for the MAX-CUT problem https://www.sciencealert.com/quantum-circuits-simulated-on-classical-computers-test-the-limits-of-future-technology, https://www.nature.com/articles/s41534-021-00440-z, and https://en.wikipedia.org/wiki/Maximum_cut
- Google tries out error correction on its quantum processor (2021) https://arstechnica.com/science/2021/07/google-tries-out-error-correction-on-its-quantum-processor/
- Record-Breaking Chinese Supercomputer Marks New Quantum Supremacy Milestone (2021, 66 Qubits) https://www.sciencealert.com/china-s-latest-56-qubit-computer-marks-another-quantum-milestone
- Scientists Achieve 'Transformational' Breakthrough in Scaling Quantum Computers (2021) https://www.sciencealert.com/scientists-achieve-transformational-breakthrough-in-scaling-up-quantum-computers and https://www.independent.co.uk/life-style/gadgets-and-tech/quantum-computing-microsoft-research-qubit-record-b1797144.html
- IBM Just Committed to Having a Functioning 1,000 Qubit Quantum Computer by 2023 (2020) https://www.sciencealert.com/ibm-thinks-it-ll-have-a-1-000-qubit-quantum-computer-running-within-three-years
- Chinese Scientists Claim Breakthrough in Quantum Computing Race (2020) https://www.bloomberg.com/news/articles/2020-12-04/chinese-scientists-claim-breakthrough-in-quantum-computing-race
- How Many Qubits Are Needed for Quantum Supremacy? (2020) https://spectrum.ieee.org/tech-talk/computing/hardware/qubit-supremacy
- How a Quantum Physicist Invented New Code to Achieve What Many Thought Was Impossible (2020) https://scitechdaily.com/how-a-quantum-physicist-invented-new-code-to-achieve-what-many-thought-was-impossible/
- IBM throws some Quantum shade at Google's leaked supremacy paper (2019) https://www.wired.com/story/ibm-googles-quantum-leap-quantum-flop/
- Last month's leaked paper is out - Google AI Blog: Quantum Supremacy Using a Programmable Superconducting Processor (2019) http://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html
- Google may have just passed the Quantum Supremacy milestone but it isn’t a practical application (2019) https://www.wired.com/story/why-googles-quantum-computing-victory-is-a-huge-deal-and-a-letdown/
- Decoherence is a major problem that must be solved before quantum computers can be effective (2019) https://blogs.scientificamerican.com/observations/the-problem-with-quantum-computers/
- Qutrit's are a more powerful alternative to qubits, now researchers demonstrate new path to reliable quantum computation (2019) https://phys.org/news/2019-06-path-reliable-quantum.html. Note, ternary has been used in computers before https://en-academic.com/dic.nsf/enwiki/1425638
- D-wave can't run Shor (2017) https://arstechnica.com/science/2017/01/explaining-the-upside-and-downside-of-d-waves-new-quantum-computer/
Some are other “quantum technologies” not covered nor directly relevant to this article: