Quantum Computing & Post-Quantum Algorithms
Businesses and organizations often ask which algorithms are safe to use and which are worth retiring. For over 25 years, the Secure Shell Protocol (SSH) has protected businesses and personal workspaces from privacy breaches by supporting viable encryption key algorithms. But as we usher in the quantum computing age, this question has become increasingly difficult to answer.
Current algorithms will be vulnerable regardless of the protocol used, and won’t be able to thwart breaches from quantum computers, which can process complex, nonlinear computations at an unimaginable speed. And although these quantum machines lack the efficiency to inflict damage today, their potential lies in the near future.
In this article, we will cover what quantum computing is, why and how it is a threat to cybersecurity, what it means for your existing classic algorithms, and how the hybrid quantum-safe algorithms can ensure optimal cybersecurity for your enterprise.
You can find more information in this guide to quantum computing and quantum-safe cryptography.
What is Quantum Computing?
Quantum computing involves solving problems with an unknown amount of variables and answers using quantum mechanics. Just like quantum mechanics tries to account for the spontaneous and random behavior of atomic particles, quantum computing accounts for the “what-ifs” of every possible scenario and outcome by analyzing and experimenting with qubits, or simple units of quantum data.
To put it in comparison, the problems our computers can solve today resemble a multi-step ladder, where the only correct answer lies at the top. Quantum computers, on the other hand, can solve problems that resemble a web surrounded by a multitude of possible solutions that can shift at the introduction or omission of a single factor.
Additionally, quantum computers work significantly faster than our current computers. In 2019, Google’s Sycamore quantum computer solved a problem in under four minutes, while it would have taken the world’s greatest supercomputer, IBM’s Summit, 10,000 years to do — that’s 158 million times faster.
As a result, the potential for advances in big data analysis, the medical industry, and battery technologies is huge. But as always, there are risks.
Why is Quantum Computing a Threat to Cybersecurity?
To understand the full threat of quantum computing, it’s essential to highlight the security processes at risk, specifically those needed for public-key cryptography (PKC). PKC is the most widely used security protocol for online browsing, data storage, and server connection. It requires a key and sometimes a signature, which are used to verify users, authenticate access, and provide confidentiality to a server. Think of it as a proverbial lock and key system.
The authentication process can unfold in two ways: symmetrically and asymmetrically. Symmetric encryption occurs when the same key is used for decryption and encryption — this is commonly used for data storage (for example, a shared USB device, laptop, or desktop computer) and to protect payment information on secure websites.
Asymmetric encryption is a lengthier process and uses a private and a public key pair to decrypt and encrypt sensitive data and/or to sign and verify a signature in authentication. It is used for session keys to protect data in transit, for example between your browser and this TLS protected website, in SSH (Secure Shell) and IPsec (IP Security) that form the bedrock of secure connections. Asymmetric key pairs are also used for server and often also user authentication, for example in Secure Shell, as well as in all digital certificate-based authentication.
Although keys are composed of lengthy numerical values that are hard to crack, quantum computing makes them easy to uncover. Two specific quantum algorithms form this quantum threat: Grover’s algorithm, which can target Symmetric Key Crypto systems, and Shor’s algorithm, which can quickly decode the integer factorization process used to generate asymmetric key pairs used in PKC.
As of now, quantum computing is too early in development to factor numbers higher than 21 with Shor's algorithm — but that doesn’t mean cybersecurity measures should relax. Protecting long-term secrets with systems that rely on Public Key Cryptography for session keys with classic algorithms is no longer sufficient as data can be recorded already now and decrypted later when cryptographically relevant quantum computer becomes available. At that point, anyone with the help of a quantum computer who has recorded classically secured data, for example while in transit over the internet or any network, will be able to access everything enterprises and users have been striving to protect and secure.
What Does This Mean for Classic Algorithms?
Because quantum computing can process and solve multidimensional problems within mere minutes, large-scale mathematical factorization algorithms responsible for generating keys are highly vulnerable. Such algorithms — like the Rivest-Shamir-Adleman (RSA), Diffie-Hellman, and Elliptic Curve PKC algorithms — are not considered “quantum-safe”, even with keys of almost 1,000 decimal digits in length. Shor’s algorithm solves these algorithms too quickly and accurately.
As a result, we must restructure how asymmetric encryption algorithms mathematically work. Here’s a closer look at how each algorithm functions and the flaws that make them vulnerable to quantum intrusion:
- Diffie-Hellman: A generating number is shared between two parties, with a private number kept secret to each party. When both parties communicate, they each multiply their private number with the generating number to create a public number. They then exchange that number with each other and raise it to the power of their original private number, ultimately giving them the same result through proof of factorization and, as such, the same shared secret in the form of a hashed moduli. Shor’s algorithm breaks the difficult problem of factoring numbers in a constant time, while previously — in classical computing — breaking such cryptosystems has been exponentially tied with the length of the secret.
- RSA: A public and a private key are generated by multiplying huge prime numbers, which makes it difficult to trace backward from the resulting number. Digital signatures are often used to further safeguard and authenticate the use of keys. However, RSA algorithms are only as strong as the length of their keys and shorter key-lengths even suffer against classical computing, so they won’t stand a chance against quantum computers.
- Elliptic Curve: Unlike the previous two algorithms, elliptic curve algorithms leverage characteristics of mathematical functions that produce curved graphs, making them significantly more tricky to solve. This allows for smaller keys for smaller processing power — however, quantum computers can still figure out the patterns that support elliptic curve cryptography, and smaller keys make the process quicker to solve.
It may seem impossible to conceive of ways to combat quantum threats, but the good news is that we still have time to smoothly transition to more robust and dependable algorithms, and production-ready PQC solutions already exist, that will outsmart what’s to come.
When Is It Time to Say Goodbye to Classic Algorithms?
If there are long-term secrets that need to remain secret also in a few years from now, the time to act is now. Even if we had solid quantum-safe alternatives to our classic algorithms for all use cases, it wouldn't be in your best interest to completely wipe the slate clean of existing protocols and implement something new just to stay several steps ahead quantum threats in the future. However, enterprises should make the move towards a safe, impenetrable, and widely applicable security protocol system that can full-fill the two requirements for post-quantum cryptography:
- it is secure against decryption attempts using a quantum computer or classical computer and
- it can interoperate with existing communications protocols and networks.
The question is, how to prioritise?
It depends on the use case
Systems protecting long-term secrets that rely on Public Key Cryptography (PKC) for session keys, need to be prioritised and upgraded to a quantum-safe solution first because existing data can be recorded already now and decrypted later.
The authentication keys based on Public Key Cryptography can wait longer, as sufficiently long Elliptic Curve and RSA keys can be used for authentication until day one when cryptographically relevant quantum computer becomes available.
Symmetric ciphers relying on AES likely survive even longer in the post-quantum world unless new attack vectors are discovered.
In practice, many applications such as most TLS for HTTPS web connections, SSH for file transfers and administrative access, most RDP and VPN remote access utilise both asymmetric key agreement and authentication keys as well as symmetric ciphers so it is also important to ensure easy upgradability of the system with new quantum-resilient algorithms going forward.
Different PQC algorithms needed for the various use cases to replace for example Classic Diffie-Hellman, RSA and Elliptic Curve algorithms reach maturity in different stages during this pre-quantum era, and just like for classic algorithms, there won’t be a one-size-fits-all quantum-safe algorithm or solution.
Cryptography must also be certified, tested, and verified before being deployed with confidence and used by enterprises and households worldwide. This means incremental process that will take a substantial amount of time before we can rely on a completely quantum-safe algorithmic bedrock.
Let go of classic algorithms when breach costs drop
A good key metric to use to determine when to give up an algorithm for good and fully adopt a stronger quantum-safe option is how much it costs to break the classic algorithm. If an institution or government entity has the financial means, it can pay to acquire the resources needed to breach an algorithm.
For instance, a cost of just a few million dollars may be acceptable enough for a government with significant resources and a strong incentive to successfully conduct a breach. As time passes and technology evolves, breaking an algorithm costs less. Therefore, once an algorithm is given an affordable price tag, it’s best to consider it defunct.
Follow industry authorities for insights
Following updates from top-tier industry officials will clue you in on when you should drop a specific algorithm. Once an algorithm becomes vulnerable, the National Institute of Standards and Technology (NIST), the National Cyber Security Centre (NCSC), and the European Telecommunications Standards Institute (ETSI) will flag it and begin devising solutions. All three organizations continually seek expert opinions and alert the public on emerging cybersecurity threats and trends.
In the face of quantum computing, NIST (US) and ETSI are workshopping alternatives, while NCSC is publishing information surrounding any innovations that come from these efforts. NIST has been working with cryptography researchers and experts since 2015 to thoroughly evaluate and test run algorithms that could be deemed quantum-safe. Discussions, webinars, and panels are conducted and published online to keep ideas circulating, with standards for post-quantum cryptography set to be established between 2022 and 2024.
The NIST post-quantum cryptography program has already selected CRYSTALS-Kyber for general encryption along with several signature algorithms, and are now in final fourth round considering alternatives. Both the availability and requirement for standardized quantum-safe algorithms for both encryption and digital signatures is likely a reality in just a few years.
Why Adopt a Hybrid Approach?
It’s common for there to be oversights in cryptographic designs, especially for newer algorithmic breeds that will have to outsmart quantum computing. The best route to take as we move towards a post-quantum future is a hybrid approach whenever possible. This allows your enterprise to utilize existing algorithms concurrently with quantum-safe algorithms to forge a two-step, fail-safe solution, such as the Hybrid Key Exchange for Secure Shell (SSH) or TLS. If weaknesses are discovered in a quantum-safe algorithm itself or in its implementation, the classic algorithms already in place will protect confidential data instead of leaving it exposed and decrypted.
Developing and implementing quantum-safe algorithms will also cost a hefty amount of time and money, especially for legacy software and hardware that may not be entirely compatible with new algorithms that emerge in the coming years. The hybrid approach enables you to make a smooth transition and spread the cost, with minimal risk to your return on investment. Systems that support hybrid algorithms can provide migration path when high priority assets are protected first with PQC hybrid algorithms, and while the migration process in the environment is in progress, low priority assets can continue to use classic algorithms without service interruptions.
Quantum-Proof Your Cybersecurity with SSH
Within the next decade, quantum computers will become a notable threat — fortunately, there’s time before then to fortify your cryptography and cybersecurity protocols to keep your data protected.
SSH’s Tectia packages work seamlessly with Windows, Linux, UNIX, and macOS, and support OpenSSH and SSHv2-compliant protocols for smooth interoperability. Also IBM z/OS mainframes are a supported environment. With quantum-safe cryptography, Tectia works hand-in-hand with the traditional protocols you rely on to prevent and defend against the breaches of today and tomorrow.
The U.S. Department of Commerce's National Institute of Standards and Technology (NIST) has chosen the first group of encryption tools for the first stage of standardizing quantum-resilient algorithms.
As for now, only one algorithm, CRYSTALS-Kyber, is in the category of key exchange. This algorithm is included in Tectia Quantum Safe Edition which was released in June 2022. This subscription-based Tectia edition supports the possibility of changing the algorithms easily when the standards evolve.
NQX, SSH’s post-quantum encryption software solution for data transport, includes Quantum Safe Cryptography (QSC) key exchange and authentication methods, together with strong encryption, to ensure your data will stay safe over time — even after the emergence of the quantum threat.