Don't throw the (cryptographic) baby out with the bathwater

Recent advances in quantum computing have shortened the timeline for breaking RSA encryption to within five years, prompting Google to call for accelerated adoption of Post-Quantum Cryptography (PQC) by 2029. The risk stems from Shor's Algorithm, which can factor large integers using fewer qubits than previously estimated, potentially enabling state actors to decrypt captured traffic before 2035.

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 https://en.wikipedia.org/wiki/RSA cryptosystem . Up until recently, the working assumption held by many was that cryptographically relevant quantum computers would be available by 2035 https://nvlpubs.nist.gov/nistpubs/ir/2024/NIST.IR.8547.ipd.pdf . 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 https://arxiv.org/abs/2603.28846 , and Google thinks we need to accelerate the pace of PQC adoption so that we finish before 2029 https://blog.google/innovation-and-ai/technology/safety-security/cryptography-migration-timeline/ . 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’ https://en.wikipedia.org/wiki/Shor%27s 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’ https://en.wikipedia.org/wiki/Grover%27s 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 /?p=395 applies to this blog.