Security Experts:

Mitigating Threats to Encryption From Quantum and Bad Random

The Threat to Encryption from Quantum and Bad Random, and How to Solve it

Encryption is under threat from two sides. The first we can call bad actors, which comprises criminals and nation states. The second is bad encryption, which comprises poor systems and bad random. These two threats already combine to make common encryption less secure than we like to believe ‒ and with the power of quantum computing, it will only get worse.

Bad actors

Bad actors comprise nation states and criminals. Nation states often subcontract their work to criminals, so it is better to differentiate them by intent. Nation states seek to gain national security or economic advantage; criminals seek financial gain. 

The two most important bad nation state actors are Russia and China. Russia is the biggest immediate threat while China is the bigger long term threat (although long term is already a misnomer). Jeremy Fleming, director of GCHQ commented in April 2021, “Russia is affecting the weather, while China is shaping the climate.”

China is seeking world technological dominance. It believes that quantum computing and the enormous leap in data processing it will bring is the key. It has invested $10 billion in building a new dedicated quantum research center with an aggressive agenda. 

Pan Jianwei, China’s lead quantum scientist is reported as saying, “Our plan is that by 2020, or maybe as soon as next year, we achieve ‘quantum supremacy’ with calculation power one million times to all existing computers around the world combined.” If China has achieved that, China could already be decrypting the billions of records they have harvested over the last decade — and if they haven’t yet achieved it, it is clearly their intention to do so as soon as possible.

We need to digress. It is thought that around the time of the OPM breach, China changed its cyber policy from stealing technology to stealing personal data on a massive scale ‒ known as data harvesting. China has been storing this data and the data stolen in similar harvesting attacks around the world, waiting for the time it could decrypt that data with the power of quantum computers. 

If China doesn’t already have this ability, it will not be long before it does. This is because of a quantum algorithm developed by Peter Shor, now a professor of applied mathematics at MIT, in 1994. Shor’s algorithm can use quantum computing to factor large RSA numbers exponentially faster than any other method ‒ and it doesn’t require a full-scale general purpose quantum computer. In other words, if not here now, it will be very soon ‒ and every harvested message by any nation state going back a decade or more will be decrypted and read by some government agency in one or more countries.

Russia will also be working on quantum computing, but Russian criminals are not waiting for it. In October 2019, Kaspersky described a newly found malware it called Reductor, which it attributed to Turla. Turla is thought to be associated with the Russian government, so it might be more accurate to call Reductor a nation state attack.

Reductor works by compromising the random number generator within the browser. It installs rogue certificates and patches the TLS PRNG, making it possible to decrypt the subsequent key, and read messages without the owner knowing. “We didn’t observe any MitM functionality in the analyzed malware samples,” wrote Kaspersky. “However, Reductor is able to install digital certificates and mark the targets’ TLS traffic. It uses infected installers for initial infection through HTTP downloads from warez websites. The fact the original files on these sites are not infected also points to evidence of subsequent traffic manipulation.” In short, Reductor compromises the generation of the random number used in the RSA key generation so that it can use that compromise to easily decrypt messages harvested from the infected device.

Bad random

Russia isn’t waiting for quantum computers to decrypt encrypted messages. The key is the random number. If it isn’t genuinely random ‒ and unique ‒ it will be recoverable. Uniqueness is a separate but similar problem. 

Encrypted DataIn December 2019, Keyfactor’s Jonathan Kilgallin analyzed millions of certificates. He found that 1 in every 172 certificates had duplicate keys. “If the prime numbers used to create the public keys are not truly random,” he wrote, “it is possible there could be a duplicate. And if two public keys share a common factor, it takes nothing more than a few microseconds of computation and simple mathematics to find the other factors, and compromise both keys.” The majority, but certainly not all, the duplicates come from IoT devices that do not have sufficient onboard resources to do good random number generation.

One of the earliest thefts of bitcoin was an exploitation of bad random in Android’s random number generator. Arstechnica reported in August 2013, “The Android apps that were exploited in the recent Bitcoin thefts may have signed multiple transactions using an identical number the apps presumed was random, Symantec researchers said in their blog post. ‘Since transactions are public on the Bitcoin network, attackers scanned the transaction block chain looking for these particular transactions to retrieve the private key and transfer funds from the Bitcoin wallet without the owner’s consent.’”

So far, we have learned that the security of RSA and existing encryption is already not absolute, but with the power of Shor’s algorithm and a quantum computer, it will be obsolete. The key is the random number ‒ if it is not absolutely random, it is breakable. The power of quantum computers and Shor’s algorithm will make it breakable at scale and speed.

The only mathematically provably secure solution is a genuinely random number generator for key generation, and a true one-time pad for encryption of data at rest. There will be occasions when the one-time pad will be superseded by a compliance requirement for a specific quantum proof encryption, perhaps lattice based; but the OTP remains the best solution. The true random number generator can itself be satisfied by the application of quantum mechanics in a quantum random number generator (QRNG).

The solution

QRNGs exist today. Perhaps the best known is IronBridge from Cambridge Quantum Computers (CQC). It can produce verifiable quantum randomness from a small quantum processor. “This is the essential seed for keys that are non-deterministic,” says the CQC website, “and can therefore not be hacked and [are] certified by the laws of quantum mechanics.”

Duncan Jones, head of quantum cybersecurity at CQC, told SecurityWeek, “Our initial focus is on a cloud-based software as a service solution, and that’s what we’re selling today. So, we use the quantum computers to generate the raw material we need. We then process that in a protective environment, something like a hardware security module. That’s where the keys are actually born, and that’s how we make sure they’re not exposed to the outside world. 

“We then distribute the keys to where they need to go. Customers typically would have a hardware security module at their end, and that’s where the key ultimately needs to reside, so that it can be used by their applications. We’re not initially focused on producing hardware ‒ however, we are doing work in the field of quantum optics, and last year we shared some information that we’re working with the National Physical Laboratory in London. We’re also looking into generating quantum entropy with photonic devices, but our primary focus right now is delivering quantum keys in a SaaS platform.”

Quantum key distribution is often performed in the U.S., via dark fiber (this is existing fiber cables that are otherwise not used). The problem is it is limited in availability, basically point-to-point, expensive, and not viable for a cloud-based SaaS operation.

Jones described CQC’s approach to key distribution: “Quantum computers will break asymmetric cryptography, like RSA. But they don’t really threaten symmetric algorithms like AES. So, we use AES to send the keys across.”

On June 8, 2019, CQC announced an agreement that it will combine with Honeywell Quantum Solutions. “The combination,” says the company announcement, “will form a new company that is extremely well-positioned to lead the quantum computing industry by offering advanced, fully integrated hardware and software solutions at an unprecedented pace, scale and level of performance to large high-growth markets worldwide.”

An alternative solution is available from the U.S. company Qrypt, which emerged from stealth mode on June 9, 2021. Qrypt was founded by Kevin Chalker (CEO) and Denis Mandich (CTO). Both are former CIA operatives who moved on with an ambition to democratize the level of privacy afforded within the CIA. They concluded it had to be encryption based on quantum random keys and the one-time pad.

Qrypt uses four different mechanisms to produce its random numbers. Chalker described the simplest. “Imagine a laser,” he said. “A laser is a true quantum device, there’s no such thing as a classical laser. So, the moment a laser pulses one of its sine waves, the phase is absolute quantum-random ‒ meaning there is no way to predict the phase as it comes out. Now, if you combine that sine wave with a known pulse sine wave - a continuous wave laser, where you know exactly the phase of it 100% of the time ‒ and you now combine those 2 waves, you’ll generate a signal that’s a series of random valleys and peaks. 

“Like two overlapping water waves, from 2 boats in the water, sometimes they constructively interfere, and sometimes they destructively interfere. It looks like it’s either a flat piece of water, or a very high piece of water, bigger than the two original waves. Each one of those, we would consider a random 0 or 1. It sounds in principle quite easy to do with lasers, but the engineering that goes into making that work and eliminating anything that’s electronic noise, is a very hard problem.” 

The result, however, is a genuinely random number that can be used to generate a quantum-proof key. The key is not generated in the cloud and there is no key distribution problem to solve. Qrypt simultaneously generates the keys from the random numbers at the respective endpoints. The keys are not distributed over the internet and therefore cannot be intercepted ‒ and Qrypt itself doesn’t see them.

Interestingly, however, you can use the process to first generate a key, and then use the same process to generate enough random numbers to create a one-time pad from the key and stream of new random numbers. This would be a genuine one-time pad comprising a truly random key. The result would be a quantum-proof and mathematically provable encryption that can never be hacked.

Going forward

Any encrypted data that has ever been stolen and is being stored by our larger adversaries ‒ especially Russia and China ‒ should be considered lost. It either has been, is being, or will soon be decrypted through the power of quantum computing. RSA is the most immediately at risk because relatively small quantum computers will be built specifically to run Shor’s algorithm.

Even if you are a quantum denier who doesn’t believe we’ll have quantum computers for another 20 years, the argument is the same. Harvested encrypted data will become readable data. We cannot change this. The best we can do is ensure that future data harvesting will yield unbreakable content.

The only way we can do that is to change to quantum proof quantum-generated keys, sooner rather than later.

Related: The United States and China - A Different Kind of Cyberwar

Related: Quantum Computing's Threat to Public-key Cryptosystems

Related: The Promise and Threat of Quantum Computing

Related: Quantum Loop: US Unveils Blueprint for 'Virtually Unhackable' Internet

view counter
Kevin Townsend is a Senior Contributor at SecurityWeek. He has been writing about high tech issues since before the birth of Microsoft. For the last 15 years he has specialized in information security; and has had many thousands of articles published in dozens of different magazines – from The Times and the Financial Times to current and long-gone computer magazines.