Predicting Q-Day and the impact of breaking RSA2048

Quantum computing represents a significant leap forward in computational power, with significant implications for cybersecurity and cryptography. Unlike classical computers, which process information in binary bits, quantum computers use quantum bits or qubits. These qubits can exist in multiple states simultaneously, enabling quantum computers to solve certain complex problems much faster than classical computers. This potential for dramatically increased computational power poses a serious challenge to the cryptographic algorithms that currently secure our digital communications.

One of the most widely used cryptographic algorithms is RSA2048, named after its creators (Rivest, Shamir, and Adleman) and its 2048-bit key length. RSA2048 is fundamental to securing online transactions, emails, and other forms of digital communication. It relies on the difficulty of factoring large prime numbers-a task that is currently infeasible for classical computers due to the enormous amount of time it would take. However, quantum computers, with their advanced processing capabilities, could potentially solve this problem much more quickly, rendering RSA2048 encryption vulnerable to decryption.

The implications of compromising RSA2048 are far-reaching and potentially devastating for global security. If quantum computers can break RSA2048 encryption, encrypted communications and data currently considered secure could be exposed, leading to widespread breaches of privacy and security. The vulnerability is that any collected encrypted traffic would become readable. This would affect everything from financial transactions and government communications to personal emails and corporate data. The ability of malicious actors, including nation states, to decrypt previously secure information could lead to significant economic, political, and social disruptions, highlighting the urgent need for advancements in quantum-resistant cryptographic solutions.

Figure 1: Estimates of Q-Day Across Research Organizations (Sources Listed Below)

Unpredictable algorithm developments

All of the Q-Day timeline predictions in Figure 1 are based on various estimates for the expected rate of progression in quantum computing. In comparison to classical computing, quantum computing is in its infancy. While the theory behind quantum computing has been around since the 1980s, the first small-scale demonstrations emerged in 1998, based on a system with only 2 qubits. Since then, the quantum computing industry has invented itself from the ground up, making scientific and engineering breakthroughs at an ever-increasing pace. Despite this progress, many of the most dramatic speed-ups that quantum computing is expected to offer for a host of computational problems are still out of reach for even the most advanced quantum computers that are available today. The ability to break encryption is a good example of that.

The process of estimating how powerful a quantum computer needs to be in order to run a target application is referred to as resource estimation. This estimate depends entirely on the structure and implementation of the envisioned algorithm. While there is little doubt about the mathematical validity of these quantum algorithms, it nevertheless presents a challenge to predict future advancements in quantum algorithm development. With advances in quantum hardware, commonly predicted timelines for Q-Day might be accelerated with little notice.

A good example of this type of algorithmic breakthrough has recently been demonstrated. In a UK publication, an example was shown that reduced a complex material simulation algorithm requiring 1.5 trillion quantum gate operations down to only 410,000. That's a factor of 4 million times improvement, putting a promising algorithm that was considered out of reach into the realm of a near-term achievable goal in a single discovery.

These types of breakthroughs are happening constantly and are accelerated by the advances created by quantum computing researchers. This progress is unpredictable and often cannot be "forced," but the more attention is paid to an attractive target, the more likely it is that new innovative ideas will trigger breakthroughs, with highly consequential implications.

Importance of Having an Estimate

• The role of these estimates in preparing and planning cybersecurity strategies.

• How businesses and governments can use this timeline to prioritize investment in quantum-safe technologies.

Having some estimate for Q-Day is foundational to preparedness; all systems, niche or ubiquitous, have transitional inertia that will require planning, coordination, and iteration to overcome. The White House's guidance on US Q-Day readiness illustrates the problem: before any strategy can be developed, much work must be done to catalog the data at risk, the systems that interact with them, and any other systems which may also be affected by these changes. After taking this inventory, planning and then managing migration will take more time. This has the cumulative effect of bringing Q-Day forward. The problem to be solved is not when will Q-Day be, but when does Q-Day preparation need to begin. Working backwards from a credible estimate helps answer this question.

Once a Q-Day timeline has been established, businesses can then begin to prioritize investment in quantum-safe technologies based on the sensitivity/value of data on certain systems, as well as which will present softer targets for bad actors. Systems that involve frequent transmission of potentially valuable information like communications platforms or collaboration tools are examples of good places to start; sensitive information passes between employees on a daily basis, and moving to a quantum-safe platform requires relatively less investment and time than other systems.

Nation States Collecting Information Now to Decrypt Later

Nation states are increasingly employing a strategy known as "harvest now, decrypt later," where they collect and store vast amounts of encrypted data with the anticipation that future advancements in quantum computing will enable them to decrypt this information. This approach hinges on the belief that quantum computers will eventually surpass classical computers in their ability to solve complex mathematical problems that underlie modern encryption techniques. By accumulating encrypted data now, nation states aim to unlock sensitive information in the future, potentially gaining access to classified communications, financial transactions, and personal data once quantum decryption capabilities become available.

The risks associated with the "harvest now, decrypt later" strategy are material. Data that is secure today could become vulnerable in the near future, exposing critical information to unauthorized parties. This threat looms particularly large for sensitive data that remains valuable over time, such as military secrets, diplomatic communications, and intellectual property. The potential for quantum computers to break current encryption standards means that any data intercepted and stored today could be at risk, leading to significant breaches of privacy, loss of competitive advantage, and compromised national security. Organizations and governments must recognize this emerging threat and take proactive steps to mitigate the potential fallout from future quantum decryption capabilities.

How to React to the Quantum Threat

Preparing for a post-quantum world involves taking measured steps to transition to quantum-resistant algorithms, ensuring that sensitive data remains secure in the future. It is prudent for organizations to start exploring quantum-resistant algorithms now, while recognizing that the urgency varies depending on the timeline one considers. A balanced approach involves conducting a thorough assessment of current cryptographic practices and gradually integrating post-quantum cryptographic solutions. This transition should be part of a longer-term strategy that allows for updates and adjustments as quantum computing technology evolves and clearer timelines emerge.

Early adoption of quantum-resistant algorithms offers several advantages, including the ability to test and refine these solutions before quantum threats become imminent. However, there is no immediate need to overhaul systems overnight. By steadily incorporating quantum-resistant measures, organizations can ensure they are prepared without causing disruption to their current operations. Monitoring developments in quantum computing and staying informed about advancements in post-quantum cryptography will help organizations make informed decisions and remain secure in the face of future technological changes.

Quantum-Safe Encryption Initiatives by Major Companies

Established players in the messaging space have taken early action to introduce quantum-resistant encryption. In March of 2024, Apple introduced its PQ3 protocol, which by the end of the year will add quantum encryption to key exchange and ongoing message streams. This is an encouraging move by a large consumer-oriented player but highlights some of the challenges presented by introducing quantum resistance into contemporary systems. Apple's protocol will not rotate keys with every message, limiting its post-compromise and forward secrecy. Additionally, the company has opted not to digitally sign its messages, presumably to reduce overhead, thus removing another safeguard for its messages.

Signal has also moved to introduce PQC into its messaging protocol, and has similarly had to find new solutions to cope with the additional challenges and overhead that comes with PQC. Notably, in group settings, Signal uses pairwise key distribution in the formation of groups, but then switches to shared group secrets within sessions, relaxing some of the hallmark protections that the company's one-to-one messaging is known for.

The Power of Quantum Computing and Its Impact on Security

Before diving into the positive impact of quantum computing, it's important to acknowledge the risks it poses to existing security protocols, as previously discussed. The immense computational power of quantum machines threatens to break widely used encryption methods, prompting companies to explore quantum-resistant solutions. However, while these risks are pressing, quantum computing also opens up significant opportunities to revolutionize security strategies. Below are key ways in which quantum computing can enhance a company's security posture and better protect against evolving cyber threats.

1. Advanced Threat Detection and Analysis

Quantum computing will revolutionize threat detection by processing massive datasets in parallel, enabling the rapid identification of complex threats like zero-day vulnerabilities and advanced persistent threats. This will significantly reduce the time attackers have to exploit weaknesses.

2. Optimization of Security Protocols

Quantum algorithms will dynamically optimize cybersecurity defenses, allowing for real-time adjustments to security measures based on evolving threats. This ensures that organizations maintain the strongest possible defenses at all times.

3. AI-Enhanced Threat Prediction

Quantum-enhanced AI models will process vast amounts of threat intelligence data at unprecedented speeds, enabling more accurate predictions of emerging cyber threats. This will lead to faster, more proactive responses, reducing the impact of potential attacks.

4. Automated Code Bug Discovery and Repair

Quantum computing will enable the instant identification and automatic repair of software vulnerabilities. This rapid cycle of detection and patching will greatly reduce the risk of exploitation, enhancing overall software security.

5. Accelerated Vulnerability Scanning

Quantum computers will enable security teams to scan and identify vulnerabilities across entire networks at unprecedented speeds. This rapid detection will allow for immediate mitigation, reducing the window of opportunity for attackers.

6. Enhanced Credential Harvesting Defense

Quantum algorithms will fortify defenses against credential harvesting by enabling the development of ultra-secure, quantum-resistant encryption methods. This will protect sensitive data and authentication mechanisms from even the most advanced attacks.

7. Ransomware Prevention and Response

Quantum computing will empower organizations to quickly detect and neutralize ransomware threats by analyzing encryption patterns in real-time. Additionally, quantum capabilities will facilitate the rapid development of decryption methods, minimizing the impact of ransomware attacks.

---

Figure 1 Sources:

Mosca, M. & Piani, M. (2023). Quantum threat timeline report. Global Risk Institute. https://globalriskinstitute.org/publication/2023-quantum-threat-timeline-report/

Susnjara, S. & Smalley, I. (2024). What is quantum-safe cryptography? IBM. https://www.ibm.com/topics/quantum-safe-cryptography

Lohrmann, D. (2023). Quantum computers: What is Q-Day? And what's the solution? Government Technology. https://www.govtech.com/blogs/lohrmann-on-cybersecurity/quantum-computers-what-is-q-day-and-whats-the-solution

Kozloski, M. (2023). The countdown to Q-day: A major concern for the modern CIO. Winslow Technology Group. https://winslowtg.com/the-countdown-to-q-day-a-major-concern-for-the-modern-cio/

(2022). Post-quantum cryptography. QuSecure. https://www.qusecure.com/post-quantum-cryptography/

Chen, L., Jordan S., Liu, Y., Moody, D., Peralta, R., Perlner, R., & Smith-Tone, D. (2016). Report on post-quantum cryptography. National Institute of Standards and Technology. https://nvlpubs.nist.gov/nistpubs/ir/2016/nist.ir.8105.pdf

Baumgartner, L., Klein, B., Mohr, N., Pflanzer, A., & Soller, H. (2022). When-and how-to prepare for post-quantum cryptography. McKinsey Digital. https://www.mckinsey.com/capabilities/mckinsey-digital/our-insights/when-and-how-to-prepare-for-post-quantum-cryptography

(March 2023). Information Security Manual. Australia Cyber Security Centre. https://www.cyber.gov.au/sites/default/files/2023-03/Information%20Security%20Manual%20-%20%28March%202023%29.pdf

Soutar, C., Barmes, I., & Stap, C. (2023). Don't let drivers for quantum cyber readiness take a back seat! Deloitte. https://www.deloitte.com/global/en/services/risk-advisory/services/quantum-cyber-readiness.html

Vermeer, M. & Peet, E. (2020). Securing communications in the quantum computing age: Managing the risks to encryption. Rand Corporation (Security 2040). https://www.rand.org/content/dam/rand/pubs/research_reports/RR3100/RR3102/RAND_RR3102.pdf

Schmieg, S., Kolbl, S., & Endignoux, G. (2024). Google's threat model for post-quantum cryptography. Google Bug Hunters. https://bughunters.google.com/blog/5108747984306176/google-s-threat-model-for-post-quantum-cryptography

Harishankar, R., Muppidi, S., Osborne, M., Rjaibi, W., & Schaefer, J. (2022). Security in the quantum computing era. IBM. https://www.ibm.com/downloads/documents/us-en/10a99803f92fda69

Public link

Please use the above public link if you want to share this noodl on another website.