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) |
The following highly-technical information will only prove interesting to readers who want to know how RSA works.
Please click here to move ahead if this does not interest you.
An asymmetric key is actually made up of a public key and a private key. The best-known form of this type of encryption is RSA, which works because of an unusual aspect of multiplication that requires calculated public and private keys.
An encrypted value can be determined by multiplying a character value by itself RSA public key number of times, making sure to roll over the resulting value to remain within the range of the original character value. A character has a numeric range of 0 to 255. Repeat for every character in the message.
Repeat the same process using the RSA private key value to decrypt the encrypted message.
This process requires choosing two prime values. A prime value is one that is only divisible by 1 and itself. The first prime value is 2. All subsequent prime values are odd numbers. Any multiple of a prime is not a prime, such as 3 x 3, which equals 9.
RSA proper uses huge prime numbers. We will use small prime numbers (7 and 13) to keep the math light.
Multiply the prime values (7 x 13) to determine a maximum value of 91.
Multiply each prime number less one ((7-1) x (13-1)) to arrive at Ø, which equals 72.
Choose a value e where the greatest common denominator (GCD) of Ø and that value equals 1. This e value must be less than the maximum value of 91. We will use 5 for this example. Several values below 91 will return a GCD of 1 when combined with 72. You can try it using Excel with this function: +GCD(72,5)
The following values will result in a GCD of 1 when used with 72.
1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89
This equation will produce a private key:
ex + Øy = gcd(e, Ø) = 1
This means (e multiplied by x) plus (Ø multiplied by y) equals 1.
This calculation relies on the Extended Euclidian Algorithm. This algorithm is used to calculate large RSA keys.
For our example, we can state that x = 29 and y = -2 where 5(29) + 72(-2) = 1
The public key is e, which equals 5, and the private key is x, which equals 29.
To make this clear, 5 times 29 equals 145. We need to multiply 72 by a value that will equal -144, so that when we add the two values together, the result will be 1. 72 times 2 equals 144, thus -2 times 72 equals -144.
Time to encrypt some data using RSA. Let’s state that the first message byte equals 47.
Calculate that value to the power of the public key, rolled to be within the range of 0 to 255 by using a modulus of 256.
47 to the power of 5 equals 229,345,007, where that value rolled using a modulus of 256 equals an encrypted value of 239.
| Power | Value | Value modulus 256 |
|---|---|---|
| 1 | 47 | 47 |
| 2 | 2,209 | 161 |
| 3 | 103,823 | 143 |
| 4 | 4,879,681 | 65 |
| 5 | 229,345,007 | 239 |
You can calculate this with Excel by using this formula: +MOD(POWER(47,5),256))
If you calculate the final encrypted value of 239 to the power of 29 times (private key value), modulus 256, then the decrypted message byte will equal 47 (the original plaintext byte value).
| 239 | 33 | 207 | 65 | 175 | 97 | 143 | 129 | 111 | 161 |
| 79 | 193 | 47 | 225 | 15 | 1 | 239 | 33 | 207 | 65 |
| 175 | 97 | 143 | 129 | 111 | 161 | 79 | 193 | 47 |
As you can see, this unusual process results in a relatively clean way to encrypt and decrypt messages by using public and private keys. What you can also see is that if really large keys are used, then encrypting and decrypting message bytes would be extremely slow, especially for large messages. Breaking a large public key to determine the private key requires a process called factoring that is considered too slow and difficult for all but extremely powerful computers.
Asymmetric encryption techniques are too cumbersome to be used to encrypt and decrypt large amounts of data.
The asymmetric public key is not used to decrypt a message encrypted with the asymmetric private key. Instead, it is used to verify the signature of a message that has been signed with the private key. Decryption is done with the private key, following encryption with the public key.
Encrypting something with an asymmetric private key is always called signing.
Encrypting something with a public key is always called encrypting.
It is possible to factor RSA public keys to determine the private keys. We will use the Unix/Linux bc utility during this exercise to perform calculations. While it is possible to use applications such as Excel for mathematical calculations, Excel’s accuracy breaks down when large numbers are used where bc remains accurate. If a large value is calculated using bc, then pasted into an Excel cell, Excel will convert the value to an internal format that permanently loses accuracy. Please use bc for accuracy.
We’ll use a simple example to explain how to break RSA keys. We will use OpenSSL to create 96-bit RSA keys to make it easy to break the keys. RSA keys are normally much larger in size, and far more difficult to break without using extremely powerful hardware and specialized techniques. You would also never have access to the private key to verify the break.
openssl genrsa -out key96.pem 96
The key will contain information such as this:
-----BEGIN RSA PRIVATE KEY----- MFECAQACDQC+MFOxbSHYSmlsJzcCAwEAAQIMcRyK2g39t2nIpH2BAgcA+r2K8aBB AgcAwi2gYGl3AgcAzOPv0uxBAgZuLLc/nPcCBwD2MTuqYxA= -----END RSA PRIVATE KEY-----
The key is in PEM format where base64 public and private key data are wrapped between BEGIN and END lines.
We extract the PEM file data using OpenSSL:
openssl rsa –in key96.pem –text >key96.txt
This is the pertinent result:
Private-Key: (96 bit)
modulus:
00:be:30:53:b1:6d:21:d8:4a:69:6c:27:37
publicExponent: 65537 (0x10001)
privateExponent:
71:1c:8a:da:0d:fd:b7:69:c8:a4:7d:81
prime1: 275691986853953 (0xfabd8af1a041)
prime2: 213501219989879 (0xc22da0606977)
exponent1: 225279353220161 (0xcce3efd2ec41)
exponent2: 121138332015863 (0x6e2cb73f9cf7)
coefficient: 270691314852624 (0xf6313baa6310)
The default OpenSSL public encryption exponent (e) is 65537, which equals 216+1
The modulus and privateExponent are in hexadecimal format where each hex byte value is separated by a colon. Colons must be removed before converting into decimal format. Values are sequenced from high on the left to low on the right. These values can easily be converted into two bc chain calculations by using the following PHP program:
<?php
$modulus = 'be3053b16d21d84a696c2737';
$privateExponent = '711c8ada0dfdb769c8a47d81';
showBC('modulus', strlen($modulus), $modulus);
showBC('privateExponent', strlen($privateExponent), $privateExponent);
function showBC($id, $sz, $data)
{
echo $id, "\n";
$power = 0;
for ($o = 0, $i = $sz-1; $o < $sz; $o+=2, $i-=2) {
$de = base_convert($data[$i-1] . $data[$i], 16, 10);
echo '((2^', $power, ')*', $de, ')';
echo ($o+2 >= $sz) ? "\n" : '+';
$power += 8;
}
}
?>
modulus ((2^0)*55)+((2^8)*39)+((2^16)*108)+((2^24)*105)+((2^32)*74)+((2^40)*216)+((2^48)*33)+((2^56)*109)+((2^64)*177)+((2^72)*83)+((2^80)*48)+((2^88)*190) privateExponent ((2^0)*129)+((2^8)*125)+((2^16)*164)+((2^24)*200)+((2^32)*105)+((2^40)*183)+((2^48)*253)+((2^56)*13)+((2^64)*218)+((2^72)*138)+((2^80)*28)+((2^88)*113)
In bc, execute both chain calculations to get the following decimal values:
modulus: 58860575534752648723711141687 privateExponent: 35006311741734210019080306049
Here are all associated values that will be used to break the RSA private key:
| ID | Field | Decimal value |
|---|---|---|
| 1 | Modulus | 58860575534752648723711141687 |
| d | privateExponent | 35006311741734210019080306049 |
| e | publicExponent | 65537 |
| p | prime1 | 275691986853953 |
| q | prime2 | 213501219989879 |
| exponent1 | 225279353220161 | |
| exponent2 | 121138332015863 | |
| coefficient | 270691314852624 |
We verify that the modulus is correct by calculating n = pq using bc, which is the product of prime1 and prime2:
275691986853953*213501219989879
The product equals the modulus:
58860575534752648723711141687
We’ll use bc to check that ed = 1 mod (p1-)(q-1)
e = 65537 d = 35006311741734210019080306049 p = 275691986853953 q = 213501219989879 e*d%((p-1)*(q-1)) 1
The result must equal 1. You can type quit to exit bc at any time.
The modulus can be factored into the prime values from the Unix/Linux command line:
factor 58860575534752648723711141687
This returns:
58860575534752648723711141687: 213501219989879 275691986853953
Factoring returns prime values that equal p and q, which breaks RSA.
The factor command uses Pollard’s rho algorithm. It is not suitable for factoring the product of two large prime values. There are several other applications, such as msieve, that are better suited for factoring larger prime values.
We now calculate a decryption key d, knowing e, p-1 and q-1.
For this we need an implementation of the extended Euclidian algorithm. We’ll use Python this time:
#!/usr/local/bin/python
import sys
sys.setrecursionlimit(1000000)
# return (g, x, y) a*x + b*y = gcd(x, y)
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)
e = 65537
p = 275691986853953
q = 213501219989879
a = e
b = (p-1)*(q-1)
print egcd(a, b)
Calling this script will return a triple in the form of (g, x, y):
(1L, -23854263793017949511423991807L, 26560L) g=1 x=-23854263793017949511423991807 y=26560
g is the greatest common divisor of a and b, and x and y are solutions to g = ax + by.
The privateExponent (d) must be positive, and must satisfy 1 = de + (p-1)(q-1)y
The x value returned satisfied the second part, but can be negative. If negative, we must add (p-1)(q-1) to get a positive value, which is congruent mod (p-1)(q-1)
The x value is -23854263793017949511423991807
Using bc:
p = 275691986853953 q = 213501219989879 b = (p-1)*(q-1) -23854263793017949511423991807+b
Returns:
35006311741734210019080306049
The returned value equals d that we started with. As shown, it is not very difficult to crack RSA keys providing the keys are small. Large keys used today are too complex to factor within a reasonable amount of time.
At a basic level, the generation of RSA private keys require randomly drawing two potentially large prime values that can be multiplied together to create a public key. Factoring the public key into the original private keys requires finding two prime values that will equal the public key when multiplied together. This has been detailed earlier.
If an RSA public key has a maximum size of 2048 bits, then the private key values can range from 2 to the final prime value that is less than 21024. This is because 21024 multiplied by 21024 equals 22048.
Mathematical calculations performed by computer software is usually limited by the size of natural data types. For 64-bit operating systems, the largest non-decimal data type is a 64-bit integer. The maximum value of an unsigned 64-bit integer is 264 - 1, which is far less than needed to calculate 21024 prime values that are used to create a 22048 public key. Performing mathematical calculations at these levels requires use of software to calculate values using an array of natural data types that combine to the desired bit size where programmed modulus rounding is applied to keep calculated values within range.
We believe that it would prove illogical to manage an array of natural data types that exceed 21024 when attempting to factor a 22048 public key. While general-purpose software is most likely used that can calculate far larger values, it would appear logical to discard out of range prime values while factoring.
Please contact us if you have information that proves this statement to be untrue. If so, then the following information will also prove to be invalid.
If our contention is valid, then the design of working with two identical large prime ranges to create a public key makes it easier to factor. If we removed predictability out of the equation, then factoring the public key into two prime values will prove more difficult and time consuming.
A byte would first be randomly drawn to use as a Boolean flag to determine which method of prime generation was used
We will use a 2048 bit public key for our example.
This technique will increase the factoring time of public keys when the technique used to create prime pairs is randomly determined. This is because the numeric range of each prime value will prove unknown to the attacker. If the choice of approach to generate the primes is random, and the minimum and maximum ranges are random, then factoring ranges must allow for the largest prime value to be outside of the standard range for the key size.
Our logic traces back to probability of patterns found in 1024 bit random private keys. We generated 232 (4,294,967,296) random 1024 bit (128 byte) keys while calculating occurences of identical byte sequences within the generated keys. We generated a total of 549,755,813,888 random bytes for our test.
2 byte identical sets had an average count of 31,754.46 within the random sample. Each byte within the range of 0 to 255 was represented, where the highest count was 32,184 and lowest count was 31,308.
3 byte identical sets had an average count of 123.68 within the random sample. Each byte within the range of 0 to 255 was represented, where the highest count was 154 and lowest count was 89.
4 byte identical sets had an average count of 0.4219 within the random sample. Only 93 of 256 byte values were represented, where the highest count was 3 and lowest count was 0.
We tested for identical sets of byte values that ranged from 2 bytes to 16 bytes in sequence. There were no counts beyond 4 byte sets. The results matched our expectations for the sample size and are largely reflective of what would be found for 1024 bit prime values where all prime values beyond 2 are odd.
We have provided this information to demonstrate that it would be ridiculous for any factoring algorithm to be designed to focus on finding low value prime values when factoring a 2048 bit public key. With each prime key made up of 128 bytes, even if the high key bytes contained 2, 3 or even 4 byte sequences of low value bytes, the actual prime key value would remain extremely large. If the technique outlined above was used to generate a small prime value and an extremely large prime value, then factoring algorithms would fail for lack of consideration of discovering a low prime value.
Please contact us if you can prove that the method outlined above would not increase the time needed to factor an RSA public key.
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.
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 (48), not asymmetric encryption such as RSA or Elliptic-Curve Cryptography (ECC). (49) 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 (50) that briefly details Grover's algorithm and Shor's algorithm, then ends with use of Lattice encryption (51) 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 (52), 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
[52] Reducing the Time to Break Symmetric Keys
© Richard Evers
Published 4-March-2019, Last Update 21-June-2019 @ 3:30 PM EST