Post-quantum cryptography in mobile networks
Work on cryptography in cellular networks technologies, such as 5G, is driven both in 3GPP and in IETF. Post-quantum cryptography is one important field in this area. Ericsson actively participates in this work, and we recently presented a well-received paper in 3GPP describing the impact of quantum computers and how they affect cellular networks.
This blog post is a slightly revised reproduction of the paper.
Cryptographic algorithms and security protocols are a very active area with rapid changes in research, standardization, and deployments. Timely deprecation of weak algorithms requires early introduction of strong mandatory-to-implement algorithms. Even without any surprising attacks, cryptographic algorithm profiling requires long-term planning.
This discussion paper describes the impact of quantum computers and how they affect 3GPP. Required mid- and long-term actions are described. No short-term actions are identified.
Background and Analysis
A number of recent research breakthroughs in quantum computers have significantly raised the interest in quantum computing and post-quantum cryptography (PQC). Although the construction of quantum computers is still in its infancy, even a relatively small quantum computer would utterly break all currently used public-key cryptography, and quantum computers are now seen as a realistic threat by governments, researchers, and enterprises.
Because of their fundamentally different constitution with qubits (quantum bits) and the use of superposition and entanglement, quantum computers have different capabilities than classical computers. Quantum computers have been studied theoretically for a long time and some algorithms have already been invented. Quantum computers can solve some specific problems much faster than classical computers, but would for general problems be both slower and more expensive. Unfortunately, two problems that quantum computers solve faster than classical computers are integer factorization and discrete logarithm, the problems that today’s public key cryptography is based on.
Shor’s algorithm will practically break all currently standardized public-key algorithms, including RSA, Elliptic-Curve Cryptography (ECC), Diffie-Hellman, and pairing-based crypto, as discussed in the paper Shor's discrete logarithm quantum algorithm for elliptic curves. With Shor’s algorithm, today’s public-key algorithms lose almost all security, and increasing the key length does not help much. Using a quantum computer, recovering the private key in RSA-2048 can be done in 235 operations. While early results pointed to RSA being slightly harder to break on quantum computers than ECC (at the same classical security level), recent research – listed here by IETF – taking reversibility into account, shows that breaking 160-bit ECC ends up requiring more qubits and more quantum operations than RSA-1024.
Fortunately, there exist several cryptographic schemes built on different hard problems in areas such as coding theory, lattices, hash functions, multivariate equations, and supersingular elliptic curves. The interest from governments and industry to standardize and deploy new schemes will likely spawn proposals for new asymmetric algorithms. And while the new schemes will most likely not have as good properties as ECC, ECC speed combined with RSA key and signature sizes seem within reach.
In their Report on Post-Quantum Cryptography, the US National Institute of Standards and Technology (NIST) estimates that quantum computers capable of breaking current public-key cryptography in a matter of hours can be built by 2030 for a budget of about a billion dollars. The most urgent matter is to protect information that needs to be confidential longer than this, as well as protecting software and firmware upgrades in long-lived hardware nodes. For governments wanting 50 years of confidentiality, it’s likely already too late and information encrypted today may only get 15–20 years of confidentiality. For most other use cases, there is no reason to panic, and the best option is to wait until publicly evaluated algorithms have been standardized. The US government has announced that they will transition to quantum-resistant algorithms in a not too distant future, and NIST has announced a call for proposals on quantum-resistant cryptographic algorithms such as public key encryption, digital signature schemes, and key exchange protocols.
Quantum computers would also have a theoretical impact on symmetric cryptography. Grover’s algorithm can invert any function using only 𝒪(N1/2) evaluations, where N is the number of possible inputs, e.g. cryptographic keys. Using a quantum computer, key recovery of AES-128 could be done in 286 operations. But Grover’s algorithm cannot be effectively parallelized, and together with the higher cost and lower clock rates, this means that a cluster of classical computers will likely remain the most cost-efficient way to break symmetrical crypto. It is unknown if Grover’s algorithm will ever be relevant for practical cryptanalysis.
When will quantum computers emerge?
Small quantum computers have already been built. In the above mentioned report, NIST writes that: “researchers working on building a quantum computer have estimated that it is likely that a quantum computer capable of breaking 2000-bit RSA in a matter of hours could be built by 2030 for a budget of about a billion dollars”. This is a serious long-term threat to public-key cryptosystems, but also means that the quantum computers built 2030 are estimated to cost 106 times more and have 103 times slower clock rate than today’s classical computers.
What can quantum attackers do?
An attacker running Shor’s algorithm on a large enough quantum computer can break all currently used public-key cryptography and could therefore:
- Passively decrypt communication where RSA, ECC, DH, or pairing-based cryptography was used for key exchange. This also applies to old recorded communication.
- Find private keys and forge certificates, enabling an attacker to authenticate or sign as a chosen user or node.
- Install fraudulent firmware and software, taking complete control of the software in a node.
How fast can quantum attackers break RSA, DH, ECC, and pairing-based cryptography?
NIST estimates that a quantum attacker running Shor’s algorithm by 2030 can break RSA-2048 in a matter of hours. All currently used key sizes in DH, ECC, and pairing-based cryptography would have similar complexities and would also be broken in a matter of hours or a few days.
Does increasing the size of the public key help?
In general no. The running time of Shor’s algorithm is 𝒪(n3) and the required number of qubits is 𝒪(n), so doubling the key length only makes key recovery require 8 times more operations and requires 2 times as many qubits. Achieving the same security level as AES-128 would require RSA keys lengths of several hundred million bits. Increasing the key length is therefore not a practical solution and all RSA, ECC, DH and pairing-based cryptography should be deprecated well in advance of the arrival of quantum computers (estimated to be around 2030).
Is RSA and MODP groups less affected than elliptic curve cryptography?
No, while early results pointed to RSA being slightly harder to break on quantum computers than ECC, recent research taking reversibility into account shows that breaking ECC ends up requiring more qubits and more quantum operations than RSA (at the same classical security level). Quantum computers are not a reason to prefer RSA to ECC.
What is pairing-based cryptography?
Pairing-based cryptography is the basis for all current Identity Based Encryption (IBE) and Attribute Based Encryption schemes. Examples of pairing-based cryptography are MIKEY-SAKKE and ECCSI.
Which 3GPP systems are affected?
All systems using public-key cryptography such as RSA, DH, ECDSA, ECDH or pairing-based cryptography for authentication or key-exchange. This includes all systems using TLS, DTLS, IKEv2, certificates, and MIKEY-SAKKE. Symmetric algorithms such as AKA authentication and the radio encryption and integrity algorithms are not affected.
Does 3GPP need to replace all public-key algorithms?
Yes, even if the time estimates for quantum computers are uncertain, the threat is real, and 3GPP needs to be prepared. Government and industry transition will force also a 3GPP transition to quantum resistant public-key cryptography.
Should 3GPP introduce quantum cryptography?
No, even if quantum key exchange and quantum encryption are interesting theoretical research topics, they have little practical use. Quantum cryptography still has to rely on classical cryptography for authentication, and for any practical uses, encryption. Quantum cryptography is not cost-effective and does not solve any practical security problems.
Can quantum attackers break AES-128?
No. NIST estimates that a quantum computer breaking RSA-2048 in a matter of hours could be built by 2030 for about a billion dollars. This means that NIST estimates early quantum computers to have a clock rate of a few MHz. Such a quantum computer (a single 20 MHz quantum core) running Grover’s algorithm would need 1011 years (a hundred billion years) to break AES-128. Even a cluster of 109 quantum cores (the world's largest public classical supercomputer has 107 cores) with a clock rate of 2 THz would need 106 years (a million years) to break AES-128.
Will symmetric algorithms with 128-bit security be affected?
No, all 128-bit algorithms such as A5/4, GEA4, GIA4, GEA5, GIA5, UEA1, UIA1, UEA2, UIA2, EEA1, EIA1, EEA2, EIA2, EEA3, EIA3, MILENAGE, TUAK, AES-128, and SHA-256 will still offer sufficient security, quantum computers will not change this. NIST plans to define their 128-bit algorithms AES-128 and SHA-256 as quantum safe.
Will symmetric algorithms with 64-bit security be affected?
No, all 64-bit algorithms such as A5/1, A5/2, A5/3, GEA1, GEA2, GEA3, COMP-128-1, COMP-128-2, and COMP-128-3 are already weak because of their very short key size, quantum computers will not change this.
Should 3GPP move to 256-bit algorithms for encryption and integrity?
Introducing symmetric 256-bit algorithms such as AES-256 may be a good idea as it is mandated by many governments (e.g. US government) and the processing overhead compared to 128-bit security is relatively small. However, Quantum computers mostly have theoretical impact on symmetric cryptography and NIST estimates that quantum computers will not reduce the lifetime of AES-128 and SHA-256. NIST plans to define both algorithms quantum safe. There are no practical needs to introduce 256-bit crypto because of quantum computers.
What should 3GPP do?
3GPP should wait until publicly evaluated PQC algorithms have been standardized. Introducing algorithms that has not been publically evaluated for many years introduces more risks than it eliminates. 3GPP should mandate implementation of post-quantum cryptography as soon as public evaluated algorithms have been standardized. Actions should be aligned with IETF standardization of TLS, IKEv2, and X.509. 3GPP should aim to deprecate non-quantum safe algorithms before large enough quantum computers emerge. Timely introduction of post-quantum cryptography enables this.
The original paper, The Impact of Quantum Computers and Post Quantum Cryptography, can be downloaded from the 3GPP web site.