Recently, there has been a surge in progress in quantum computing that has shortened the hypothetical timeline on which quantum computers can ‘break’ traditional public-key cryptography that uses the RSA scheme.
Up until recently, the working assumption held by many was that cryptographically relevant quantum computers would be available by 2035. Post-Quantum Cryptography (PQC) schemes — resistant to the attack methods quantum computing exposes — needed to be designed and deployed before then.
Well, those timelines have become significantly shorter, and Google thinks we need to accelerate the pace of PQC adoption so that we finish before 2029. The pace of quantum hardware development, quantum error correction, and quantum factoring resource estimates puts the feasibility of breaking the current RSA scheme within five years.
Asymmetric and symmetric keying #
The thing is, secure connections on the web depend on both public-key (asymmetric) and shared-key (symmetric) cryptography. Public-key schemes like RSA and Elliptic Curve Cryptography (ECC) are used in Transport Layer Security (TLS) to start secure connections. The data exchanged over those connections is encrypted and decrypted using a symmetric scheme like AES, with a shared key that both parties either already have or can agree on.
Why do we continue to use shared keys? Because asymmetric key methods are too slow and computationally expensive to use for the routine encryption of every packet. They are used to encrypt the least data possible, which includes the value of the shared key used to protect everything else.
When we say ‘protected by RSA Public Key Infrastructure (PKI)’, what we really mean is:
- The sharing of the symmetric secret key is protected by RSA
- The rest of our packets are protected by the symmetric shared key scheme.
- That shared key is being continuously changed or ‘re-keyed’ across the life of the connection.
The risk to asymmetric keys #
The big risk is if the ‘bad guys’ are able to see or capture your traffic, and are also able to break the RSA keys to reveal the symmetric key used to encrypt that traffic, they’d be able to decrypt all the traffic and access your data. But that’s a big ‘if’, given we are moving to adopt quantum cryptography-resistant methods.
The risk for RSA and ECC is contained in a method of using a quantum computer called ‘Shor’s Algorithm’. You can make a leaderboard tracking the efforts toward stable, workable quantum computers based on how well they implement this algorithm to ‘factor’ a given RSA key size. Current implementations of Shor’s Algorithm are effective against highly insecure RSA keys with numerical values like 35, a number expressed in only 6 bits of binary value. ‘Real’ RSA uses numbers expressed in 2048 or 4096 bits of value, which are 256 and 512 bytes, respectively.
Improvements in the effectiveness of Shor’s Algorithm relate to reductions in the number of stable, reliable quantum bits (qubits) required to factor large integers.
Without a quantum computer, searching for the correct value in 4,096 bits worth of possible key values would take longer than the estimated life of the universe. Early QC research suggested that about one million qubits were needed to implement a search in a short, human-usable period of time. This has recently been revised down to under 100,000 reliable qubits, and we are getting better at implementing qubits and quantum error correction.
It is now foreseeable that a QC with a sufficient number of qubits will be available to state actors before 2035. We therefore believe we are inside ten years of breaking RSA, and that anything captured and held offline before now, and onward, can be decoded in under ten years.
Not so much symmetric keys #
If we stop using RSA the way we currently do, are the shared keys used to encrypt and decrypt our data at risk? Not if we cannot use PQ methods to unpack them.
If those shared keys are protected, can symmetric algorithms be broken using a QC? The answer is more mixed, [but probably still no](https://words.filippo.io/128-bits/) — less trustworthy RSA does not automatically mean that symmetric keys are broken. The key exchange mechanism might be, but we can improve that, and adopt a PQC method to share those keys.
I am not a cryptographer, but I pay attention to what cryptographers say online, and this quotation is worth reading and remembering:
AES-128 is safe against quantum computers. SHA-256 is safe against quantum computers. No symmetric key sizes have to change as part of the post-quantum transition.This is a near-consensus opinion amongst experts and standardization bodies and it needs to propagate to the rest of the IT community.[Fillipo Valsorda]
Shor’s algorithm does NOT break symmetric keying, and the other QC algorithm called ‘Grover’s Algorithm’ is both less of an advance on classical pre-quantum methods, and still highly theoretical — it hasn’t yet been shown to be feasible.
It’s important to remember that there is probably no ‘unbreakable’ encryption system, given enough time and resources.
It is also important not to ‘throw the baby out with the bathwater’, and think that because Shor’s algorithm may be becoming easier to implement, Grover’s Algorithm must also now be more feasible, or that we cannot trust our symmetric shared keys any more.
The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.