Preparing for the day quantum computing cracks public-key cryptography: What to do now
- 08 August, 2018 19:56
We don’t know when, but it will happen: Quantum computers will become so powerful that all existing public-key cryptography protections will be quickly crackable. According to Dr. Mark Jackson of Cambridge Quantum Computing, it could be as soon as five years from now.
The question is: Will we be prepared for that cryptographic day of reckoning?
When will quantum computing break cryptography?
Lawrence Gasman, president of IQT Research/Inside Quantum Technology, wrote this: “The timing of the quantum threat is not just uncertain because we don't know how fast the technology will develop, but because we don't even know how fast it has developed already. For all we know, there may be 100 Qubit quantum computers in Virginia, Beijing, Moscow or GCHQ that no one talks about and that can break common encryption schemes right now.”
A few scenarios are likely.
A long, orderly transition to a quantum break
The first is a slow, gradual, well publicized and documented plod toward the quantum crypto break. We have a good idea how this would go from the recent proactive move from SHA-1 hashes to SHA-2.
Although Google revealed the first publicly known SHA-1 collision in February 2017, SHA-2 had been recommended to replace the weaker SHA-1 hash algorithm since at least 2011. Successful attacks weakening SHA-1 had been appearing since 2005. Nearly all cryptographic vendors had been trying to move their customers since at least 2015.
This is the way we like our crypto transitions to play out— a decade or more of notice and gradual, public weakenings along the way. That gives vendors and customers years to prepare and change. Even with more than a decade to prepare, there was a last-minute rush for many vendors and customers to get moved over in time. SHA-1 to SHA-2 migrations was a vast majority of work I did for Microsoft and its customers between 2014 and 2017.
In aggregate, it was mostly a smooth transition. To my knowledge, no one’s critical secrets were revealed. No malware was signed by a valid SHA-1 signed certificate due to a SHA-1 flaw. The world moved from SHA-1 to SHA-2 with enough forethought that our cryptographic protections held.
A sudden quantum break
As with any cryptographic standard, no one really knows if a party hasn’t privately made the necessary cryptographic progress to reveal the world’s secrets. If a private company or government were able to make a significant cryptographic break, it is believed they would keep the secret to themselves as long as possible so they could read other people’s protected secrets. So, there is no way to know if quantum computers haven’t already broken traditional public-key crypto.
It’s also possible that quantum computer scientists will quickly reach the necessary number of “perfect” qubits to render public-key crypto obsolete in the next few years, as Dr. Jackson believes. Although many quantum researchers disagree with Dr. Jackson’s timeline, it’s not an impossible scenario. If the break happens in the next few years, society is woefully unprepared. It would be a bit of chaos.
A short and risky transition to a quantum break
A third possible scenario is something in between the orderly transition and the sudden break in which the quantum break is announced, but how it was done is a closely held secret. At least 44 companies are working toward that quantum break, but it is likely that only will be successful with maybe a few closely following competitors. Even if the way the quantum crack was achieved is known, it’s not likely those wishing to learn secrets can immediately access and use quantum computers to do so.
When to prepare for the quantum break of public-key cryptography
NIST and other quantum crypto scientists are saying now is the time to begin preparing. Just like with the SHA-1 to SHA-2 transition, customers and vendors begin preparing however they can.
Industry luminary Bruce Schneier believes we have time to prepare, writing “Major unforeseen technological advances are the stuff of fiction. In the real world, we can see technologies coming long before they get here. Today, cryptographers see the potential for quantum computation and are already creating and evaluating quantum resistant algorithms. The NSA has announced that it will move to these algorithms in the coming years. This is all according to plan. By the time quantum computers become a thing to worry about, there'll be algorithms to be put into standards, and standards to be put into products. Right now, the only work needed to be done is by the cryptographers.”
Regardless of how soon the break happens, it’s unlikely that everyone in the world will have immediate access to quantum computers. Expect most of the world’s largest corporations, militaries, universities, and governments to end up with quantum computers in due time. If you or your company can’t afford your own quantum computer, many of the places that do have them will be glad to rent temporary access.
That is one of the biggest unknowns: How fast do we move from the first publicly announced quantum break to a place where almost anyone can utilize them? If history is any guide, SHA-1 breaks went from the realm of many millions of dollars in cost to only a few thousand dollars in just a few years. So, when the quantum break happens, or is announced, expect, at best, only a few years to move to more quantum-resistant protections.
That’s if you shouldn’t already be doing it now. Most quantum computing observers think that most of the world’s biggest secret collectors (e.g., NSA, FBI and nation-states) already collect and store as many public-key crypto secrets as they can, waiting for the quantum break to occur. Then, they will use the quantum advancements to learn what they can about their adversaries and competitors.
6 steps to prepare now for the quantum break
1. Educate and communicate
All stakeholders in your environment, including other organizations you exchange secrets with, should be aware of the forthcoming quantum break. I guarantee that most don’t know how soon it could happen, so start with education and communication.
2. Assess the value of your secrets
Next, calculate the risk to your environment if all public-key crypto secrets were revealed. How many of the secrets are valuable to other people? How many adversaries and competitors do you have that want those secrets? How long will those secrets be valuable? I would ask how many of my secrets would be worthwhile to anyone, say, five years from now. Most public-key protected secrets would be worthless or close to worthless five years from now.
For example, most HTTPS-protected secrets aren’t valuable a day later. HTTPS is used for many things, including VPNs, but its biggest use is in authenticating websites to end-users. In the vast majority of cases, the end-user isn’t protecting any valuable secrets. They just want to be reassured that the websites they were connecting to are the websites they meant to connect to. Even if they are communicating real secrets, such as an account logon authenticator or bank account number, that information might not be the same five years from now or might appeal to only a certain level of criminal. Most nation-states aren’t going to be stealing money from individual bank accounts.
Do a full public-key crypto secret analysis. What secrets does your organization pass around on networks that adversaries could eavesdrop on, and how long do you need to really keep them secret? Not every secret is valuable and most significantly degrade in value over time. Start asking the right questions so when the time comes you are prepared.
3. Decide what should be physically separated
If you have critical, valuable secrets you need to protect, consider preventing others from eavesdropping on them even in protected form. A physical barrier of some type is the best way to prevent others from eavesdropping. You certainly shouldn’t be transmitting your most valuable secrets across the internet, especially using traditional public-key crypto.
A host of companies offer secure network transmissions that don’t rely on public key crypto. You can insert a network card or special network device at one location and securely transmit your secrets to another location using the same setup. Governments have been using these technologies for half a century. Today, such equipment is expensive but within the reach of many companies. Just make sure that the solution doesn’t rely on public-key crypto for its protective capabilities.
4. Use larger symmetric key sizes
Although public key crypto is susceptible to quantum computing, symmetric key encryption isn’t. Quantum computers are likely to be much more powerful than traditional binary computers, but today’s trusted symmetric algorithms don’t rely on the difficulty of factoring large prime number equations for their security. Hence, quantum computers are expected to have a “backdoor” into factoring symmetric keys beyond their pure processing power. “A 256-bit key is as strong against a quantum computer as a 128-bit key is against a conventional computer,” wrote Schneier.
Unfortunately, public-key crypto is often used to securely move otherwise unencrypted symmetric keys between source and destination. When public-key crypto is broken, the previously protected symmetric keys will no longer be secured.
If you use larger symmetric keys and don’t rely on public-key crypto to protect them, then you probably have a quantum-resistant solution. You might need to start doubling your symmetric key sizes now, though. Remember, if an adversary can eavesdrop on your information today, it can store and decode it later.
Start moving your symmetric keys from 128-bit to something larger, at least for protecting your critical, crown-jewel information. Perhaps continue to use traditional 128-bit symmetric keys on the secrets you don’t care about beyond today and use 256-bit keys on information you need to keep secret for a decade or longer. Begin that process today!
Assume that when traditional public-key crypto is broken, any symmetric keys you transmit using it are likely to be broken. If you use public-key crypto to protect symmetric keys that would otherwise be seen in plaintext, doubling the symmetric key size alone does you no good. The eavesdropper can just break the public-key crypto protecting the symmetric keys and see your new, bigger symmetric keys. We need new, quantum-resistant algorithms to securely protect transmitted symmetric keys. Unfortunately, no quantum-resistant public-key crypto standards are available yet.
It’s not like it hasn’t been done. Schneier writes, “In the 1980s, Kerberos was an all-symmetric-cryptography log-in and encryption system. More recently, the GSM cellular standard does both authentication and key distribution at scale with only symmetric cryptography. Yes, those systems have centralized points of failure, but it's possible to use both secret splitting and secret sharing to minimize that risk.”
5. Pressure vendors to be more quantum resistant
Customers had to forces many vendors using SHA-1 to address the coming crypto changes. It wasn’t easy or pretty. Some vendors were clueless. Other vendors used the SHA-1 to SHA-2 transition as a way to force customers to upgrade. In many cases, when enough customers felt aggrieved, vendors gave in and offered free SHA-2-enabling updates.
Customers, ask your vendors what they are doing to be quantum-resistant. Start pressuring them now. If they ask why, point them to the NSA/NIST document saying the time to begin preparing is now.
6. Become crypto-agile
Crypto-agility is the ability of you and especially your cryptographic-using products to move from one cryptographic algorithm to another. This was most recently highlighted by the SHA-1 to SHA-2 transition, but it has been a necessary process each time any popular crypto standard (e.g., DSS, DES, or MD5) is broken.
In the past, most devices and software (and hence, users) have not been very crypto-agile. A change from one standard to another often couldn’t be done without a big update or even product replacement. The quantum break is coming. How easy is it going to be for you, your software, and your devices, to make the jump to quantum-resistant cryptography? You’ve got time to prepare, start asking and testing.
So far, I’ve discussed what you can do to prepare for a quantum break. What can you do once the post-quantum world is here?
First, hopefully you’ve done your secret analysis, and have determined what needs to be better protected, what has been quantum-resistant protected, what still needs to be protected, and how.
Traditional talking points include using quantum-resistant cryptography and using quantum cryptography. The former seems commonsense. If you’re being attacked by quantum computing, use technologies and algorithms that are resistant to it. No national or world quantum-resistant standards exist, but there are at least six possible solutions.
Another possibility is to use quantum encryption and quantum key distribution to fight back against quantum breaking. In theory, it’s readily understandable. Quantum mechanics says that if “Eve,” the eavesdropper, tries to eavesdrop on quantum-protected communications, then that protection will change the communications so it can’t be eavesdropped on. That’s great...in theory. In practice, every “unhackable” solution has been implemented weakly enough that it ends up susceptible to hacking. Humans just aren’t great at implementing theory.
Sometimes even the theories say there are weaknesses. Schneier pointed me to a 2016 whitepaper discussing the weaknesses in quantum key distribution (QKD). I don’t know if it is good or bad that even our quantum theories have weaknesses, but at least no one is saying we have something unhackable to replace traditional public-key crypto.
Now is the time to start preparing for a post-quantum break world. Gasman says, “Data center managers must prepare for the inevitable right now and should educate themselves about what the options are: QKD? Post-quantum encryption encryption? Even those who think quantum computers are a long way off should take the trouble to protect data that is going to be stored for a long time. Ten years is not that long in the archiving world."
Don’t wait for the government and other standards bodies to tell you what you need to do. Be prepared for when that happens. As Schneier wrote me, “These things go slowly, but standards processes go even slower.”
Fight the good fight!