Quantum Encryption Threat: Accelerated Timeline for Cryptography Cracking by 2030 and Detection Challenges

DEFCONConference

Introduction to Quantum Computing & Cryptography Threats [0:00]

Quantum computing utilizes quantum mechanics phenomena like superposition and entanglement with "qubits" to process information differently from classical computers. While not performing "everything at once," it enables specific algorithms to achieve significant speedups.

Foundational Threats to Cryptography [3:54]

• Public Key Asymmetric Encryption (RSA, ECC): Vulnerable to Shor's algorithm, which can efficiently factor large numbers.
• Symmetric Encryption (AES): Vulnerable to Grover's algorithm, a search algorithm that provides a quadratic speedup for brute-forcing keys, effectively halving the key strength.

  

• Bitcoin and Cryptocurrencies: ECC, fundamental to Bitcoin, requires fewer than 2,500 logical qubits for an attack, potentially plunging its value to zero if private keys can be reversed.

  

Accelerated Timeline for "Q-Day" [7:10]

NIST initially set 2035 as the deadline for migrating to post-quantum cryptography (PQC). However, this timeline is increasingly being challenged by rapid advancements in quantum computing.

The Looming Quantum Era of Uncertainty [9:16]

• NIST's Original Timeline: Federal agencies are currently planning for PQC migration by 2035, with deprecation of vulnerable ciphers by 2030.
• The Speaker's Concern: Evidence suggests that "Q-Day"—the moment quantum computers become powerful enough to break current encryption—could arrive as early as 2030, creating a significant 5-year gap where systems would be unprotected.

  

• Consequences of Unpreparedness: This overlap could lead to widespread financial theft, identity crises, and a breakdown of trust in online systems, reminiscent of a "zero-day" exploit with a known approximate arrival date. The "harvest now, decrypt later" threat is significant for data with a long shelf life.

Shor's Algorithm and its Evolution [11:49]

Shor's algorithm, developed in 1994, is a hybrid classical-quantum algorithm for factoring large numbers, a problem underlying RSA encryption. Its practical implementation has been a major focus of research.

Algorithmic Improvements Reducing Qubit Requirements [14:22]

• Early Estimates: Initial estimates for factoring 2048-bit RSA required billions of physical qubits, making it seem distant.
• Gidney & Ekerå (2019/2021): This paper introduced significant optimizations to modular exponentiation, reducing the requirement to approximately 6,000 logical qubits (equivalent to 20 million noisy physical qubits) to factor 2048-bit RSA in about 8 hours.

  

• Regev (2023/2024): Proposed an "efficient quantum factoring algorithm" using lattices to break down Shor's math into smaller quantum jobs. While offering potential gate count reduction, its practical benefit for 2048-bit RSA is still uncertain and might require too many gates at that scale.
• Gidney [2023]: A breakthrough paper further optimized Shor's algorithm, reducing the logical qubit count for 2048-bit RSA to approximately 1,400 (under 1 million noisy physical qubits), with an estimated runtime of 5 days, achieved through advanced techniques like approximate residue arithmetic and optimized magic state cultivation.

  

  

Grover's Algorithm and Symmetric Encryption Threat [20:06]

Grover's algorithm is a quantum search algorithm that provides a quadratic speedup over classical search methods, making it a significant threat to symmetric encryption.

Weakening Symmetric Keys [21:35]

• Mechanism: Grover's algorithm uses an "oracle" to mark desired solutions and an "amplifier/diffuser" to increase their probability, allowing for efficient discovery of a target key.

  

• Impact on AES-128: For AES-128, Grover's algorithm effectively reduces its security strength to that of AES-64, which is considered highly insecure.
• Qubit Estimates: Cracking AES-128 using Grover's algorithm is estimated to require between 1,000 and 3,000 logical qubits.

  

Quantum Computer Roadmaps: IonQ and IBM [23:36]

Major quantum computing companies are rapidly advancing their hardware, pushing the timeline for cryptographically relevant quantum computers (CRQCs) much closer.

IonQ's Aggressive Projections [23:43]

• Acquisitions and Technology: IonQ's acquisitions, like Oxford Ionics (electronic gates) and LightSync (quantum module interconnect), are key to their rapid scaling.
• Timeline:
  • 2026: 256 physical qubits, 12 logical qubits.
  • 2027: 10,000 physical qubits, 800 logical qubits.
  • 2028: 30,000 physical qubits, 1,600 logical qubits (enabled by LightSync). This milestone is close to the requirements for factoring RSA-2048.
  • 2029: 200,000 physical qubits, 5,000 logical qubits.
  • 2030: 2 million physical qubits, 60,000 logical qubits, enabling the cracking of any current encryption.

    

IBM's Roadmap [26:58]

• Similar Logical Qubit Goal: IBM also projects 12 logical qubits per computing unit for next year.
• Aggressive, but Slower Pace:
  • 2027: Entangling with universal adapters.
  • 2028: Multiple units with magic state distillation.
  • 2029: 200 logical qubits.
  • 2033: 2,000 logical qubits, enough to crack encryption.
• Implication: Both IonQ and IBM's roadmaps indicate that CRQCs capable of breaking current encryption will exist before NIST's 2035 deadline, making the current migration plans insufficient.

  

Detecting Quantum Attacks [29:47]

Detecting quantum attacks presents unique challenges, especially due to the nature of quantum computing and existing cloud service provider policies.

Challenges in Local Detection and Monitoring [29:50]

• No Local Presence: Quantum computers do not physically interact with target networks, making local detection impossible. Attacks typically involve "harvest now, decrypt later" scenarios where encrypted data is exfiltrated and stored for future quantum decryption.
• Points of Detection on the Stack: While direct local detection is difficult, quantum attacks leave distinct patterns at various levels of the quantum computing stack:
  • Code and Circuit Level (Software): Specific routines like Quantum Fourier Transform and modular exponentiation for Shor's, or repeated oracle/diffusion blocks for Grover's, are identifiable.
  • Compiler and Transpiler Level: Circuit graph analysis, gate counts, and specific gate mixes (e.g., C-NOTs, rotation gates) can reveal attack patterns.
  • Pulse Control Level (Hardware Interface): Even at the lowest level of hardware control (e.g., microwave pulses for transmons), pulse sequence analysis could detect characteristic attack patterns.
  • Resource Utilization Metadata (Cloud Management): Unusual resource consumption or API calls on cloud quantum platforms might indicate an attack.

    

    

Cloud Provider Policies and Attackers [32:35]

• Privacy vs. Security: Current cloud quantum providers (e.g., AWS, IonQ) typically pledge not to inspect user content, making it difficult to detect malicious quantum computations. New license agreements or terms of service would be required for effective monitoring.

  

• Primary Attackers: Nation-states and organized crime are the most likely entities to possess or acquire the resources to conduct quantum attacks, aiming for high-value, long-term secrets.
• Moscow's Theorem: This theorem (X + Y > Z) highlights that if the time data must remain secure (X) plus the migration time (Y) is greater than the time until a quantum computer arrives (Z), the data is at risk. Given the accelerated Q-Day, many existing secrets with long shelf lives are vulnerable.

Post-Quantum Cryptography (PQC) Migration Status & Recommendations [36:07]

The migration to PQC is crucial but faces significant challenges due to slow adoption and concerns about current standards.

NIST PQC Standards and Adoption Gap [36:35]

• Approved Standards: NIST has approved lattice-based cryptography (ML-KEM for key encapsulation, ML-DSA for digital signatures) and hash-based signatures (SPHINCS+). Code-based cryptography (HQC) is expected next.

  

• Low Adoption Rates:
  • Less than 20% of internet servers currently support TLS 1.3 (a prerequisite for PQC).
  • Only 6% of OpenSSH installations are on version 10, which supports PQC by default.

    

    

• Critique of AES-128: The speaker strongly disagrees with NIST's continued allowance of 128-bit symmetric encryption, as Grover's algorithm reduces its effective security to 64 bits, which is highly insecure. A minimum of 256-bit symmetric encryption is recommended.

  

Path to Crypto Agility [39:07]

To effectively address the quantum threat, organizations need to embark on a multi-step journey:

1. Manage Your Data: Understand what data needs protection and its required shelf life.
2. Know Your Crypto: Inventory and understand all cryptographic assets in use.
3. Abstract It Out: Implement crypto agility by abstracting cryptographic primitives, making them easier to swap.
4. Become Crypto-Agile: Be prepared to quickly migrate to new "quantum-safe" cryptography as standards evolve and threats emerge.