Whether it’s breaking Enigma or factoring large primes to attack Soviet naval codes, cryptography has historically dragged computing kicking and screaming into major advances in algorithms and the hardware necessary to run them.
Quantum computing is no exception. Computing math using qubits, spinning sub-atomic particles that can theoretically hold infinitely more states compared to the 2 states held in digital transistors used in modern computers, has become an exciting next chapter in the story of applying computer science towards solving hard problems in areas like artificial intelligence and scientific analysis.
But while recent excitement has been building around using quantum computers to simulate random walks down Wall Street or run millions of simulations to teach computer vision systems to recognize whether or not something is a hot dog, quantum computing’s initial application (and the driving impetus for its funding from the US) is cryptography and code-breaking.
“Mathematics is Truth” — RZA, Wu-Tang Clan
Most of the encryption used by modern cryptography is protected by computationally difficult math problems.
For example, the popular OpenSSL suite protects against the compromise of internet traffic shuttled through its protocol by using ephemeral session keys.
These session keys ensure that the key being used for a “conversation” between a client and a server can’t be intercepted and later, with access to the server’s long term certification credentials, be decrypted.
This practice is called Perfect Forward Secrecy or PFS. And while PFS was originally formulated at the end of the Cold War to respond to the dramatically-increasing power of computer systems and the infancy of hacking, perfect forward secrecy is an absolutely critical aspect of modern information security given the surging rise of data breaches over the last five years.
Data breaches like those that struck Target and Home Depot could lead to the theft of a server’s credentials, and it is critical to enforce PFS on secure communication between clients and servers in order to ensure that a successful attack doesn’t yield sensitive client data like health records or credit card numbers.
Ephemeral session keys in OpenSSL tend to enforce PFS by using the Epehemeral Diffie-Hellman algorithm, or EDH. EDH works by having two authenticated parties generate a series of random numbers and raise a publicly-known value to the power of each’s randomly chosen number.
To establish the session key, both parties then exchange their resulting value and multiply them together. By the Laws of Exponents, the resulting value each would get would be the same. This is their ephemeral session key.
There are two ways to attack this cryptography. First, you can attack how the random numbers are generated. Sometimes the methods used to create these numbers can be tampered with, leading to an attacker substituting their own keys in the transaction.
But beyond this attack which avoids the encryption itself (something we call a side-channel attack in cryptology) there’s the “head-on” approach: break the math used to encrypt the session key. In cryptography this is called cryptanalysis, and prior to modern quantum computing it was computationally impossible to employ on EDH.
To cryptanalytically attack EDH, we need to compute something called a discrete logarithm (or simply discrete log). A discrete log is a much more complicated version of the logarithms that many of us learned about in high school algebra; much like normal logarithm it represents the power that one needs to raise a base number to yield a result.
But a discrete log further complicates things by forcing one to take the logarithm of a finite group rather than a single number. In math-speak, this means that we’re taking the discrete log of a set of components used to compute a result. In reference to EDH, this means we’re trying to find the two keys that are used and generated by each party.
Computing a discrete log is computationally intractable. While normal logarithms can be calculated so easily that pocket calculators typically include LOG functions, computing a discrete log requires a computer to arduously search for the set of inputs for the finite group used in the exponent of the base. And given that EDH typically selects large, prime integers (and that there are literally an infinite number of integers), this could take a while.
That is, unless we decide to whip out Shor’s Algorithm.
Break Glass in Case of Discrete Log
Shor’s Algorithm is a quantum computing algorithm that uses a property in quantum mechanics called superposition to dramatically speed up how the search for a set of numbers.
Superposition refers to a peculiar property where a quantum variable can exist in multiple states of existence. In quantum computing, this means that the qubits used by quantum computers can occupy far more than the 2 states used in binary transistors by modern computers.
Shor’s exploits superposition by allowing a quantum computer to search for prime factors orders of magnitude faster than its digital counterparts ever could. This search, when applied to EDH, allows a quantum computer to reduce the time needed to compute a discrete log from “longer than it will take to reach the theoretical heat death of the universe” to potentially days or even hours.
That means that in the very near future an adversary with access to a quantum computer could capture all of your web traffic encrypted over suites like OpenSSL and, using a quantum program that employed Shor’s Algorithm, steal all of your information regardless of your encryption without ever alerting you or the server you were communicating with.
Indistinguishable from Magic
Quantum computing is by no means a purely destructive force in security. In addition to providing new means of breaking existing cryptosystems, it also provides new opportunities in securing and transmitting data.
One of the most exciting opportunities afforded by quantum computing is in quantum encryption. This is a nascent field that looks at using curious properties of quantum mechanics (like how Shor’s Algorithm exploits superposition) in new ways for securing the transmission and storage of sensitive data.
The hottest area in quantum encryption lies in secure communication using quantum entanglement, a property of quantum mechanics where a pair of particles or group of particles are subject to an interaction that results in them all having non-independent states. This means that in order to describe the state of a single particle in the pair/group, you need information from all of its entangled twins.
Even more interesting, the process of entanglement seems to ignore all convention of distance: particles remained entangled (or to use the physics term, remain coherent) regardless of how far away they are in space. This means that a subset of an entangled group could theoretically move an infinite distance away and reflect changes to its counterparts immediately with no time lag or loss of data. Or, as Einstein put it, entangled particles exhibit “spooky action at a distance.”
Such properties are extremely valuable in cryptography. Entanglement provides the opportunity to create a lossless, high performance encrypted communication network that is impervious to compromise and otherwise near impossible to even detect.
While much of this sounds like something from Star Wars (and is literally how instantaneous faster-than-light communication is performed in the video game Mass Effect 2), science is rapidly advancing in quantum mechanics to allow us to reliably wield quantum entanglement as a means of “teleporting” information. Recent studies have confirmed the existence of these once theoretical properties, and scientists have even wielded “spooky action” to “teleport” data remotely and instantaneously across small distances.
Quantum cryptography and quantum “hacking” are some of the most exciting and disruptive topics in cryptography, security, and computing as a whole. But there are serious challenges to overcome before we enter a world where teenagers wielding 100+ qubit quantum computers are stealing everyone’s personal information.
Interacting with any quantum system is tricky. Quantum states are notoriously finicky, as they’re subject to Heisenberg Uncertainty (or simply “uncertainty”). Uncertainly shows that any attempt to interact with or measure a quantum state irrevocably changes it.
As a result, quantum computers have to take extreme steps to work. Quantum computing interactions are typically conducted in secured environments where temperatures are kept close to absolute zero in order to minimize the impact that other variables may have on a quantum system. Conducting the interaction also impacts the state of the system, forcing quantum computers to have to conduct a single operation then immediately wipe the entire array of qubits and start over before moving onto their next step.
Even worse, the output of a quantum operation is far from definitive. Because of uncertainty, there is a high probability that a single output of an operation may not reflect the intended result of the computation. To compensate for this, quantum computers run a gauntlet of computations and tests in order to return a set of results that are probabilistically likely to be correct.
Running a quantum computer is difficult. It’s like running a laptop where, after every instruction in code, you need to smash open the bottom of it with an aluminum bat and install a new motherboard and processor. And even then, the output of what you get isn’t definitively correct. The result you compute is just — after you’ve bought and shredded several US states’ supplies of Intel processors and ASUS motherboards later — decently likely to be the right answer.
But these are problems we’re overcoming surprisingly well. And in the very near future (so close that algorithms like EDH are starting to fall out of favor in lieu of other quantum-resistant means of establishing/exchanging keys) quantum computers are going to redraw much of the landscape for cryptography and information security.
About the Author
Andy Manoske is an Amplifier at Amplify Partners and a product manager at HashiCorp. He currently manages the design, strategy, and product development of Vault, HashiCorp’s secrets management and cryptography suite. Previously he led the design and development of OTX (Open Threat Exchange) at AlienVault and managed cryptography and product security at NetApp.