Is your data safe from harvest and decrypt?
Universal quantum computers will have devastating implications for cryptography. Simply put, the hard math problems that current asymmetric algorithms are based on will not withstand attack.
Not all algorithms are the same
There are two main types of cryptographic algorithms: symmetric and asymmetric. Symmetric algorithms, like block and stream ciphers, are used for bulk data encryption, with a secret key encrypting on the sender’s side and decrypting on the receiver’s side. Asymmetric (public key) algorithms are used for authentication and establishing a secret encryption key. They use different but mathematically linked (public and private) keys, where the public key is sent openly and anyone can encrypt data using it, but only the matching private key owner can decrypt the data.
With Grover’s algorithm running on a universal quantum computer, an attacker can gain up to a quadratic root speed advantage and affect a brute-force attack. This reduces the key space, for example from 2256 to 2128, effectively making the original 256-bit key, 128-bit strong under the quantum threat. By increasing the symmetric key size, we can retain sufficiently strong protection.
A universal quantum computer attack could break classical public key cryptography using Shor’s algorithm. Most of the algorithms in public-key cryptography rely on the hardness of factoring integers or the difficulty of calculating discrete logarithms. An attacker can intercept a public key and easily derive the matching private key. To mitigate this threat, we have two options: we can use symmetric cryptography or replace the current public key algorithms with the quantum-safe equivalents. These new algorithms are still being evaluated.
What is harvest and decrypt?
With replacements not yet available, we still need to act now to mitigate the present threat. Encrypted information sent now over public networks is vulnerable to harvest and decrypt attacks. An adversary can download, and store intercepted encrypted information and then wait until they have access to a universal quantum computer to break the encryption.
An encrypted communication session consists of a handshake part and bulk data encryption part. During handshake, communicating parties are authenticated and the secret encryption key is established. When an attacker breaks the encryption, the focus in not on bulk encryption but on key establishment. With symmetric algorithms for encryption and with sufficiently large key sizes (256-bit) they can withstand the best-known attack using Grover’s algorithm. It is, however, much easier to break the key establishment, that typically relies on asymmetric algorithms, and just recover the secret symmetric encryption key using Shor’s algorithm.
What can be done now?
Two options are available to us currently to mitigate this threat. One option is to use pre-shared symmetric keys for key establishment. This option is 100% effective against a quantum-enabled adversary and is recommended by various governments and standards bodies.
Sometimes, we still need to rely on public key cryptography. Because the current asymmetric algorithms are vulnerable to attack and quantum-safe replacements are not ready, we need to use hybrid methods. While not ideal, it is better than just waiting for quantum-safe replacements.
In hybrid key establishment, a combination of classic and quantum-safe candidate algorithms is used. All algorithms used will need to be broken to recover the established key. The classic algorithm provides security against classic computers today and the quantum-safe candidate algorithms enhance the security against quantum computers. Because we do not have 100% confidence in the current quantum-safe candidates, it is best to rely on more than one hard math problem here. In the example above, if the Lattice-based Kyber algorithm is broken we can still rely on Supersingular Isogenies-based SIKE algorithm to protect the mechanism against quantum enabled attacks. Once the evaluation and standardization process are completed, we will not have to hedge our bets and just pick a single quantum-safe algorithm.
Conclusion
Even before universal quantum computers are built, the threat of a harvest and decrypt attack is relevant for long term data safety. Although the standardization of quantum-safe cryptographic algorithms will take several years, we can use pre-shared symmetric key or hybrid key establishment mechanisms to mitigate this threat today. Nokia secure transport solutions use key management relying on the most secure option available: pre-shared, symmetric keys to provide certified, standardized protection against quantum computer attack today. This solution is embodied in our 1830 SMS secure management server, supporting quantum-safe AES-256 encryption in optical and microwave transport links.
The US NSA suggests publicly that, “classified national security information with a long intelligence life should begin implementing a layer of quantum resistant protection. Such protection may be implemented today through the use of large symmetric keys.” We agree. Learn more at https://www.nokia.com/networks/solutions/secure-optical-transport/
