It is easy for most people to believe in the beliefs of experts. The problem is that many experts parrot the thoughts of others instead of taking on the difficult job of determining the truth.
This paper addresses two current beliefs about encryption.
The hard truth is that wide-spread beliefs about security and encryption may prove to be based on fantasy rather than fact.
Many people have claimed that quantum computers will be able to “crack most types of encryption.” (1)(2)
This statement is misleading at best, and false at worst.
There are two strains of conventional encryption:
Symmetric means the same, where the prefix of ‘a’ in asymmetric changes the word to mean not the same.
Symmetric encryption requires use of an identical private key to encrypt and decrypt data.
Asymmetric encryption requires a public and a private key, where each can be used to encrypt and decrypt data.
Let's look at how encryption currently works on the Web.
When you use a web browser to visit a secure web site, the site provides the browser with access to a digital certificate that will provide a great deal of information related to encryption. While the certificate may state Secure Sockets Layer (SSL), SSL has been replaced by Transport Layer Security (TLS). Both are protocols that provide data encryption and authentication between client applications and servers in scenarios where that data is being sent across in an insecure manner.
If you visit a site such as https://kryptera.ca, the browser uses the site certificate to determine how to securely communicate with the web site. (3)(4)
The browser can determine from the certificate what asymmetric encryption is used (usually RSA), and what the public key is. The browser uses the public key to encrypt a Handshake message then sends it to the site. This message includes the Coordinated Universal Time (UTC) in the Unix epoch format, several random bytes, and a high to low list of encryption algorithms that are supported by the browser.
The server decrypts the message using its private key, retains the message data for the session, creates an encrypted handshake response using the private key and sends it back to the caller. This message includes the Coordinated Universal Time (UTC) in the Unix epoch format, several random bytes, a session id made up of 32 random bytes, the chosen symmetric encryption to be used, and additional information.
After this exchange, the browser will create a symmetric private key. Once created, the browser encrypts a ‘Finished’ message with the symmetric key using the public key, and then transfers the encrypted data to the server. The server decrypts the data using the private key, then subsequently uses the passed symmetric private key to encrypt and decrypt data packets that pass between the web site and the web browser using the chosen symmetric encryption algorithm, such as AES. This process is known as an Authenticated Key Agreement (AKA). (5)
There are several points within this process that could be compromised.
RSA public/private key pairs are generated using very large prime numbers. It is critical for the large prime numbers to be randomly generated. Security issues have been found that relate to the quality of random selection of large prime values used to generate RSA public keys. The faults usually trace down to hardware and software implementation issues that cause widespread security issues worldwide. (6)(7)(8)(9)(10)
According to ROCA: Vulnerable RSA generation (CVE-2017-15361):
|
The difficulty of the factorization attack is not the same for all key lengths and is NOT strictly increasing (some longer keys may take less time to factorize than other shorter ones). The following key length ranges are now considered practically factorizable (time complexity between hours to 1000 CPU years at maximum): 512 to 704 bits, 992 to 1216 bits and 1984 to 2144 bits. Note that 4096-bit RSA key is not practically factorizable now, but may become so, if the attack is improved. The time complexity and cost for the selected key lengths (Intel E5-2650 v3@3GHz Q2/2014):
The vulnerability was found by a close inspection of a large number of RSA keys generated and exported from the manufacturer smartcards by researchers at CroCS laboratory, Masaryk University, Enigma Bridge and Ca' Foscari University. The full results were presented at an academic ACM Conference on Computer and Communications Security (ACM CCS '17) in November 2017. (10) |
We removed a complex portion of this section to improve the likelihood of people reading the entire paper.
If you believe that reading about:
... would prove interesting then click this link to access the original version of this paper at the section that has been removed.
Client applications such as web browsers can also be compromised.
A web browser must be designed to fully protect itself from exposing any data that it encrypts and decrypts using the asymmetric public key, and encrypts and decrypts using the symmetric private key. If any data can be accessed in original form then there is no guarantee of creating a secure connection or passing data in a secure manner. The fault will not lie with the encryption process. If there is a problem then it will most likely relate to internal storage of the symmetric key. Without a full security audit of all web browser software used today, there is no way to determine if any browser is secure now, and ongoing as features are added.
A web browser must generate a high-quality random symmetric key that will be used to encrypt and decrypt all data packets that flow between the site and the web browser. Products that use symmetric-key encryption can create symmetric keys in many ways that include using the RDRAND instruction provided by Intel for use with AES-NI. If the symmetric key is generated in a predictable, pseudo-random fashion, then it is possible for all traffic to be broken. Without a full security audit of all web browser software used today, with specific emphasis on the Authenticated Key Agreement (11), there can be no way to determine if any web browser is secure now, and ongoing as features are added.
Data that passes between a web browser and a web site, or between any other forms of client-server communications, is usually encrypted and decrypted using AES. Intel, AMD, Broadwell and other CPU manufacturers have incorporated support for AES into their CPUs (AES-NI) to speed up encryption and decryption. This has made it possible to greatly increase the speed of secure network communications.
Note: Everything disclosed in the following two paragraphs does not prove that AES-NI has been compromised.
Intel has incorporated a backdoor into all of their CPUs. It is called the Intel Management Engine (ME) 11, and it is connected with the U.S. government's High Assurance Platform (HAP) program. Vulnerabilities have been discovered in Intel Active Management Technology (AMT), which is based on Intel ME. There are too many security flaws surrounding Intel CPUs to determine if using AES-NI to encrypt data, or using Intel CPUs in general, can be considered secure. (12)(13)(14)(15)(16)(17)(18)(19)(20)(21).
A paper was released on March 1, 2019, entitled, "SPOILER: Speculative Load Hazards Boost Rowhammer and Cache Attacks." (22) It was picked up by The Register on March 5, 2019. (23) The SPOILER security flaw found in all Intel CPUs relates to "Exploiting the DRAM rowhammer bug to gain kernel privileges" (24) and Cache Timing Attacks on AES (21). The Register also picked up on the Rowhammer attack on March 10, 2015 (25).
If there are security flaws relating to AES-NI, they will most likely take the form of predictable symmetric key generation, retention of symmetric keys, or something else that relates to symmetric keys.
The AES algorithm and NIST approved implementations have been proven to be secure. The AES-NI implementions of AES, which have a total of six core instructions, was first released in 2006. The design and implementation was vetted prior to release to ensure that it was correct. A complete security audit of all CPU design and implementation details must occur to determine if use of AES-NI is secure.
In addition, two forms of encryption are used in client-server communications because of speed. Using an asymmetric encryption algorithm such as RSA to encrypt and decrypt all data that passes between a web browser and a web site would be extremely slow and inefficient. That is why the site and the browser switch to using symmetric encryption (such as AES) so quickly. Symmetric encryption can be extremely fast, and more secure than asymmetric encryption. The problem is that if the TLS communication channel is insecure, the symmetric key used to encrypt and decrypt data between site and browser is also insecure because the key could be captured and decrypted when first transmitted by the browser to the site. Several government security agencies capture all forms of communications that pass across networks. If any component of a secure communications protocol has become compromised, it provides these agencies with an opportunity to compromise the remainder of related traffic.
If a quantum computer can break all forms of conventional encryption then all forms of conventional encryption must be enhanced or replaced.
In the quantum realm, Shor’s algorithm (26)(27) will be used to break asymmetric encryption such as RSA, where Grover’s algorithm (28) will be used to break symmetric encryption such as AES.
Current thinking is that using Shor’s algorithm to factor out RSA private keys from a public key will require twice as many quantum logical qubits as the length of the RSA key in bits. One logical qubit is measured as a single qubit, but includes an additional 500 to 6300 times as many qubits to handle error detection and correction. This means that a 2048-bit RSA key may be broken by a quantum computer that has 4,096 or more logical qubits (2,052,096 to 25,808,896 qubits in total). Increasing the RSA key size to 4,096 bits would require a quantum computer with 8,192 or more logical qubits (4,104,192 to 51,617,792 qubits in total) to break it. Efforts are being made to reduce the number of logical qubits required to factor an RSA public key, and also reduce the number of qubits needed for error detection and correction.(29)(30)
In 1996, Lov Grover (31) introduced Grover’s algorithm to efficiently perform database searches across unsorted databases using a quantum computer. His algorithm can also be used to determine random symmetric encryption keys with a high degree of probability. Grover’s algorithm performs successive evaluations of the state being searched over a quantum-entangled state, interleaved with quantum operations on that state. After about Π/4√N iterations, a measurement of that state will provide the value being searched with a probability of 2/3. Repeating a search will increase the probability of success.
Grover’s algorithm does not parallelize well and cannot be used to break symmetric private keys within a reasonable amount of time.
According to Scott Fluhrer in Reassessing Grover’s Algorithm:
|
Because of this algorithm, it has been commonly accepted that (for example) we need to double the size of our symmetric keys in order to maintain the security level against a Quantum Computer. For example, to obtain "128 bit quantum security", that is, require the attacker to perform circa 2128 quantum operations to successfully attack the system, we need a symmetric cipher with a 256 bit key. And, yes, if the attacker has a Quantum Computer that can issue circa 2128 successive evaluations to our encryption function, they could find the key with high probability. However, in this attack model, even a 160 bit key (which would require circa 280 successive evaluations), would be secure for all practical purposes. Even if we assume that the quantum computer could evaluate the encryption function in the absurdly fast time of 1 picosecond, the total of 280 successive evaluations would require over 30,000 years to complete. Any realistic security policy is not concerned with an attack that takes that long to perform. (32) |
Grover’s algorithm must run on a quantum computer supporting logical qubits with error detection and correction that can be controlled in superposition states (33). It has been calculated (34) that it will require thousands of logical qubits with error detection and correction to create quantum circuits for implementing an exhaustive key search for AES using Grover’s algorithm:
There is no quantum computer available today that can be used in this manner to attempt to break AES keys. Even at the current rate of evolution of gated quantum computers, it will take at least several decades before any quantum computer has sufficient logical qubits with error detection and correction to run Grover's algorithm in a way that can attempt to break AES encrypted files. Even then, the probability of failure remains too high, and the period of time that will be required to break a key using this technique will prove too large to justify the effort. Using larger symmetric keys to encrypt files will completely negate the possibility of breakage using a quantum computer.
D-Wave (35) has created annealing quantum computers that have high numbers of qubits where other major manufacturers of gated quantum computers such as IBM have far lower numbers of qubits, all without error detection and correction.
The difference is that D-Wave relies on quantum annealing and tunnelling (36)(37)(38)(39) to work, which has a major problem of decoherence. (40)(41)(42) This is the loss of a qubit’s quantum state, which causes errors in quantum computing.
A few articles have been published that discuss use of D-Wave 'noisy' quantum computers to speed up factoring of RSA keys without use of Shor's algorith. (52)(53)(54)(55). Factoring would need "just 20 million qubits" to factor a 2048-bit RSA public key in about eight hours. Time will tell whether "noisy" quantum computers can be enhanced to provide 20 million qubits. By then, RSA keys may no longer be in use, or the public key size will be far larger than we use to today. The only given is that cryptographers will never throw up their hands and surrender without a fight.
According to Brian Wang in Interview on 5000 qubit quantum system and paths to general purpose quantum computers:
|
D-Wave does not have error correction and neither will the current generation of quantum gate systems.(45) |
To understand why error correction is important requires knowing what error detection and correction means in a quantum context.
A commercial quantum computer must contain qubits in a zero movement environment that is very close to absolute zero (0° Kelvin, -273.15° Celsius, -459.67° Fahrenheit) to remain operational during a calculation. Additionally, error detection and correction must be designed into each qubit to make them fault-tolerant or logical. Any direct viewing of a calculating qubit will immediately corrupt calculation. The design of the quantum computer must entangle (43) additional qubits with a computing qubit. The quantum computer can view an entangled qubit to determine the state of a calculating qubit state. If error detection indicates a problem with the computing qubit, it is possible to correct the calcuating qubit state to allow completion of the calculation.
Without error detection and correction, quantum computers cannot be used to break symmetric encryption keys using Grover's algorithm without providing a large multiple of the needed number of qubits to make each calculating qubit a logical qubit. (44)(45)
According to Brian Wang in Interview on 5000 qubit quantum system and paths to general purpose quantum computers:
|
There are two major approaches to quantum computing systems – annealing and the gate model. Gate model systems actually require longer coherence times, more qubit control, etc. than D-Wave does. D-Wave forces the quantum states into a digital state with each annealing cycle, some 5000 – 10,000 times per second. Currently IBM, Google and Rigetti have created or are creating about 50 qubit gate systems with no error correction. They are not universal quantum computing systems but approximate gate model systems. These system may be good at one or two applications, that’s unknown so far. Error correction for quantum systems is a thousand times harder than non-error correcting. D-Wave does not have error correction and neither will the current generation of quantum gate systems. D-Wave repeatedly solves problems to get around the lack of error correction. 1000 problem runs generates a distribution of solutions. Those solutions are easily checked to see which is the best solution. Classical digital systems get by with one error correct bit for every 8 bits. Research on quantum error correction suggests that for 2000 qubits one would need 1 million error correcting qubits and another paper said for 1000 qubits one would need 6.3 million error correcting qubits. The vast number of qubits needed for an error corrected system is why no error correcting system has been implemented for any quantum gate. (45) |
A gate model quantum computer using Shor’s algorithm to factor a common 2,048 bit RSA key will require between 2,052,096 and 25,808,896 total qubits, and will require between 4,104,192 and 51,617,792 total qubits to factor a more recent 4,096 bit RSA key.
A gate model quantum computer using Grover’s algorithm to halve the bit complexity of a 128 bit AES key will require between 1,479,453 and 18,606,853 total qubits, and will require between 3,347,181 and 42,096,981 total qubits to halve the bit complexity of a 256 bit AES key. Halving the bit complexity of a larger symmetric key leaves far too much bit complexity to break the key within a reasonable amount of time.
Understandably, there has been a concentrated global effort to solve the problem of quantum error detection and correction. (46) We believe this effort will eventually result in reduced overhead. Once that occurs, it may prove feasible to create quantum computers with sufficient logical qubits to reliably run Shor's and Grover's algorithms, although not necessarily to break current key lengths. Unfortunately, no one really knows what will happen in the future. Within the quantum realm, subjective truth has often been used in place of objective truth by people who gain by spreading unjustified fear about quantum computers. After many years of concentrated development, gate model quantum computers remain extremely limited, and have no error detection and correction qubits. Fear-mongering about the false threat of quantum computers breaking all or some forms of conventional encryption should not be permitted to direct policy.
Take, for example, the following statement made by Arvind Krishna, director of IBM Research, in May 2018 as reported by Tom Foremsk for ZDNet.
|
Quantum computers will be able to instantly break the encryption of sensitive data protected by today's strongest security, warns the head of IBM Research. This could happen in a little more than five years because of advances in quantum computer technologies. "Anyone that wants to make sure that their data is protected for longer than 10 years should move to alternate forms of encryption now," said Arvind Krishna, director of IBM Research. (2) |
Note the use of the weasel word (47), "could", instead of "will" or "shall." The author's statement is invalid because it is too vague. Also, almost all sensitive data is protected by symmetric encryption such as AES or Kryptera, not asymmetric encryption such as RSA or Elliptic-Curve Cryptography (ECC). (48) The earliest stages of opening a secure connection relies on public-private key (asymmetric) encryption. Each subsequent data packet that passes between client and server is encrypted using symmetric key encryption, while files are also encrypted using symmetric key encryption. Symmetric key encryption is the most widely used form of encryption.
If you read the article, (2) you will find that it provides a link to an article published in 2016 on IBM's site (49) that briefly details Grover's algorithm and Shor's algorithm, then ends with use of Lattice encryption (50) as a solution to the problem. Note that Lattice is a replacement for asymmetric encryption, not symmetric. There was no reason to mention Grover's algorithm in the article.
Whenever you come across anyone claiming that all forms of encryption will be broken by quantum computers, try to discover if they are qualified to make that statement. If so, then question if they will gain by making false prophesies. While conventional forms of asymmetric encryption will eventually be replaced by quantum secure forms of asymmetric encryption, conventional forms of symmetric encryption will not be replaced as long as it remains far too time consuming for a quantum computer to iterate and test keys against cyphertext for breakage. If symmetric key size proves to be too small to be remain secure well into the future, then software can be altered to use larger symmetric keys without needing to greatly alter the underlying algorithms. Symmetric forms of encryption can remain inherently secure and invulnerable to quantum attacks without too much difficulty.
We have read many articles and interviews, and watched several interviews and lectures, that centred around quantum computers being able to break conventional forms of encryption. The quantum physicists often qualify their statements to mean that asymmetric encryption will be placed at risk by quantum computers in the future. The media types appear to fail to understand the qualifier, and declare that all forms of conventional encryption will be placed at risk by quantum computers. We have yet to come across a quantum physicist who has publicly corrected this falsehood. Symmetric forms of encryption can easily be made quantum secure by increasing the key length.
In a former paper (51), we describe how to greatly reduce the time needed to break symmetric keys by using 1-n randomly generated test keys across a local or wide area network of dedicated computers such as those found in crypto currency mining farms. Because each symmetric test key is randomly generated, there is no need of central control to generate the keys, where every CPU or GPU thread can generate as many tests keys as possible to try to break a subset of a shared encrypted file. The techniques that we developed will work with conventional computers, and super computers, but will prove too demanding for quantum computers.
So we have the reality of quantum computers not being able to break asymmetric and symmetric keys, and the promoted perception of quantum computers being able to do it.
This is where we have a real problem with articles that state that Grover's algorithm will reduce symmetric key complexity to half the bit value. The caveat is that these gains can only be achieved by using far more powerful quantum computers that may not be available for many decades to come, if ever. Even then, it will prove easy to alter software to increase the size of symmetric keys.
Contact Information
Richard Evers
Contact via Email
https://kryptera.ca
Alastair Sweeny
Contact via Email
https://kryptera.ca
[1] NSA seeks to build quantum computer that could crack most types of encryption
[2] IBM warns of instant breaking of encryption by quantum computers: 'Move your data today'
[3] How does HTTPS actually work?
[4] The First Few Milliseconds of an HTTPS Connection
[5] Authenticated Key Agreement Protocols: A Comparative Study
[6] Infineon RSA library does not properly generate RSA key pairs
[7] The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli
[8] 2017.11.05: Reconstructing ROCA
[10] ROCA: Vulnerable RSA generation (CVE-2017-15361)
[13] Intel's remote AMT vulnerability, May 1, 2017
[14] Intel's Management Engine is a security hazard, and users need a way to disable it, May 8, 2017
[15] Disabling Intel ME 11 via undocumented mode, August 28, 2017
[17] Sakaki's EFI Install Guide/Disabling the Intel Management Engine, Nov 2, 2017
[18] Everything You Need to Know About Intel's CPUs Getting Hacked, Nov 17, 2017
[19] Intel Q3’17 ME 11.x, SPS 4.0, and TXE 3.0 Security Review Cumulative Update, Nov 22, 2017
[20] TEMPEST attacks against AES: Covertly stealing keys for €200
[21] Cache-timing attacks on AES, by Daniel J. Bernstein
[22] SPOILER: Speculative Load Hazards Boost Rowhammer and Cache Attacks
[24] Project Zero: Exploiting the DRAM rowhammer bug to gain kernel privileges
[26] Shor's Algorithm for Quantum Factorization
[27] Shor's algorithm - Wikipedia
[30] Quantum Computing and Cryptography Their impact on cryptographic practice
[32] Reassessing Grover’s Algorithm
[34] Applying Grover’s algorithm to AES: quantum resource estimates
[37] What’s the difference between quantum annealing and universal gate quantum computers?
[40] Explaining the upside and downside of D-Wave’s new quantum computer
[42] What is quantum decoherence?
[44] Quantum Circuits Opens Lab for Modular Quantum Computers
[45] Interview on 5000 qubit quantum system and paths to general purpose quantum computers
[46] Better Qubits versus More Efficient Error Correction
[48] Elliptic-curve cryptography
[49] Preparing for the Next Era of Computing With Quantum-Safe Cryptography
[50] Lattice-based cryptography
[51] Reducing the Time to Break Symmetric Keys
[53] Breaking RSA Encryption – an Update on the State-of-the-Art
[54] How a quantum computer could break 2048-bit RSA encryption in 8 hours
[55] How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
© Richard Evers
Published 4-March-2019, Last Update 12-October-2020 @ 13:52 PM EST