The processing power of quantum computers is set to outstrip the capabilities of today’s supercomputers. According to a report, Google’s fledgling quantum computer performed a calculation in three minutes and 20 seconds that it would have taken today’s fastest supercomputer, IBM’s Summit, 10,000 years to complete. Let’s look at the capabilities of quantum computing and what kind of post-quantum public-key encryption and key exchange algorithms will be strong enough to resist the power of quantum computers.
Quantum computers are becoming a reality, making our claims about the impracticality of cracking encryption much weaker. Quantum technology makes computer processing so much faster than several encryption methods are no longer effective. In other cases, key size reviews are necessary. Organizations must prepare now while quantum computers are still in development.
Current Computer Speed and Encryption Cracking
Symmetric and asymmetric encryption have different purposes and work in different ways. It is essential to understand these differences before looking at the impact of quantum attacks.
Symmetric Encryption
Today’s approaches to encryption and hashing depend on the inability of current computing power to crack keys and prime numbers in less than the lifetime of an attacker. Standardized encryption methods like AES are too strong to crack unless an attacker knows the key.
Figure 1 shows graphic models of AES (Advanced Encryption Standard). AES, a sample of symmetric encryption, is very strong. The use of 128- and 256-bit keys makes it impervious to cracking. Contrary to movies and TV, The only way to get unauthorized access to AES encrypted information is to steal or guess the key. Guessing is impractical due to the size of the key spaces (the number of possible keys). A 128-bit key has 2128 possible keys or 3.4028236692094 x 1038. The AES-256 keyspace is far larger at 1.1579208923732 x 1077.
Figure 1: AES Model (Source: Wikipedia)
Ubiq Security describesOpens a new window the length of time it would take with today’s technology to guess the keys for AES-128 and AES-256. Using the combined power of Bitcoin farmer networks, it could take about 70,000,000,000,000,000,000,000,000 years to guess an AES-128 key.Â
The critical takeaway for symmetric encryption is that the size of the key determines the power and time an attacker would need to guess an AES key. There is no other known way to crack the encryption.
Learn More: What Is Cloud Encryption? Definition, Importance, Methods, and Best PracticesÂ
Asymmetric Encryption
Asymmetric encryption, or public-key encryption, is used for digital signatures and key exchange during TLS setup. It is used by anyone connecting to a secure website, which is most sites today.
Asymmetric encryption relies on the inability of computers to factor large numbers of prime numbers within a workable period. With today’s computing power, this is a strong assumption. For example, Andreas Baumhof, writing for Quintessence Labs, claimsOpens a new window that it would take about 300 trillion years to break an RSA-2048 bit encryption key.
The effort needed to crack encryption changes when a quantum computer does key guessing and prime number factoring.
What is Quantum Computing?
Martin Giles, writing for the MIT Technology ReviewOpens a new window , asserts that “a quantum computer harnesses some of the almost mystical phenomena of quantum mechanics to deliver huge leaps forward in processing power.†The processing power of quantum computers is set to outstrip the capabilities of today’s supercomputers.
According to Giles, quantum computing replaces current computer technology’s 1’s and 0’s (binary bits) with qubits, which are subatomic particles. They possess quantum properties that allow using a connected group of them to provide much more processing power than the same number of bits.A group of qubits can “represent numbers combinations of 1 and 0 at the same time.â€
The use of quantum mechanics for computing provides speeds magnitudes greater than those of today’s fastest supercomputers. Madhumita Mugia and Richard Waters, in an article in the Financial Times, reportedOpens a new window that Google’s fledgling quantum computer performed a calculation in three minutes and 20 seconds that it would have taken today’s fastest supercomputer, IBM’s Summit, 10,000 years to complete. This reported result is based on the claims of Google’s researchers.
Although quantum computer prototypes exist, they face substantial challenges. Scott Pakin and Patrick Coles writeOpens a new window in Scientific American that “quantum computers are extremely difficult to engineer, build and program.†A significant challenge is preventing decoherence: the decay of qubit quantum behavior. Vibrations, temperature fluctuations, and electromagnetic waves are just some of the things that can cause decoherence.
Practical use of quantum computing is still a few years away, but now is an excellent time to prepare for the impact this power will have on cryptography.
Learn More: The Encryption Elephant in the Room: Getting to Secure Encrypted Traffic
How Capable is Quantum Computing?
There have been many articles and blogs about the death of encryption because of quantum computing. This is half true. Figure 2 provides a general picture of how encryption standards are affected.
Figure 2: Impact of Quantum Computing (from MicrosoftOpens a new window )
The significant impact is on asymmetric encryption. Using Shor’s algorithm, shown in Figure 3, quantum computing breaks all public-key cryptography. Public-key solutions like RSA, Diffie-Hellman, and ECC will all need replacements. Among other things, this has a severe effect on key exchanges for TLS.
Figure 3: Shor’s Algorithm (from Lane WagnerOpens a new window )
While Grover’s algorithm can reduce the time necessary to guess symmetric keys, widely accepted solutions with sufficient key size are believed to be quantum-resistant. Lane Wagner, writingOpens a new window for Qvault, reports that Grover’s algorithm can effectively reduce the attack time against AES-128 to achieve reasonably successful key guessing once quantum computers reach the necessary power levels. However, the AES-256 keyspace is sufficiently large to remain resistant to quantum-enabled attacks.
One thing to remember is that user-entered passwords protect many encryption keys. Quantum computers will be able to crack today’s strong passwords in days instead of years or centuries.Â
Learn More: 5 Things You Should Know About Quantum Computing
Post Quantum Cryptography
There isn’t much organizations can do today to replace their asymmetric encryption solutions. However, the U.S. National Institute of Standards and Technology (NIST) began its call for submissions for post-quantum asymmetric encryption needs in 2016. NIST has listedOpens a new window its round three finalists for public-key encryption and key exchange algorithms, including
- Classic McEliece
- CRYSTALS-KYBER
- FALCON
- RAINBOW
Microsoft writesOpens a new window that it is working to strengthen the following four algorithms integrated into the PQ Crypto fork of OpenSSL.
- FrodoKEM
- SIKE
- Picnic
- qTESLA
Writing for Sectigo, Alan Grau blogsOpens a new window that the NIST will make its final selection within the 2022-2024 timeframe. Based on where quantum computer technology is today, this should be before organizations have to worry about quantum attacks. Sara Castellanos reportedOpens a new window for The Wall Street Journal that Google does not plan to produce a commercial quantum computer big enough to cause encryption headaches until 2029.Â
The large window between now and the uselessness of current asymmetric algorithms should not prevent organizations from changing to new quantum-resistant algorithms once they are considered sufficiently tested. After a new algorithm is selected, it will take time to change existing PKI systems and other solutions that use public-key encryption.Â
Symmetric encryption is mainly safe from quantum computing attacks. Key sizes might increase, but solutions like AES-256 are sufficient to resist key guessing. Therefore, organizations using AES-128 should move to AES-256. All new encryption implementations should use the 256-bit key format. It is all about the key size when using a standardized symmetric encryption algorithm.
Finally, organizations should move to two-factor authentication to access keys. The use of strong passwords is no longer considered a viable option by itself, even without the looming threat of quantum computing.Â
Final Thoughts
While we need to be concerned about quantum computing and encryption, quantum computers big enough to be a real problem are several years away. Baumhauf writesOpens a new window that the necessary power to break RSA-2048 keys is about 4099 qubits. Google’s Bristlecone quantum computer is only 72 qubits. However, this does not mean organizations and vendors should wait until the first commercial quantum computer is available to fix what we expect to be broken.
Organizations must assume quantum attacks are a real possibility. Increased interest by big players in this technology (e.g., Google, IBM, and Azure Quantum) is quickly moving quantum technology forward. Consequently, it is necessary to include this threat when conducting risk assessments for systems that have long-term encryption requirements.
Do you think quantum computing could pose a serious threat to modern encryption standards in the coming years? Comment below or let us know on LinkedInOpens a new window , TwitterOpens a new window , or FacebookOpens a new window . We would love to hear from you!