Preparing Vulnerability Management for the Post-Quantum Era: From Legacy Cryptography Crypto-Agility

Preparing Vulnerability Management for the Post-Quantum Era: From Legacy Cryptography Crypto-Agility

Speakers: Arun Singh, Security Research Engineer, Qualys

Conference: VulnCon

YouTube: https://www.youtube.com/watch?v=3rs1uYn7fe4

Overview

Arun Singh, a Security Research Engineer at Qualys, delivered a critical talk at VulnCon addressing the looming threat of quantum computing to our current cryptographic infrastructure. His presentation, "Preparing Vulnerability Management for the Post-Quantum Era: From Legacy Cryptography Crypto-Agility," emphasized that the transition to Post-Quantum Cryptography (PQC) is not a distant future problem, but an urgent operational challenge demanding immediate attention from vulnerability management teams. Singh argues that waiting for a definitive "quantum breakthrough" date is already too late, framing the challenge as a pressing "timing problem" driven by the concept of "Harvest Now, Decrypt Later" (HNDL) attacks.

The core of Singh's argument is that the pervasive presence of legacy cryptography, combined with the inherently long and complex migration timelines for enterprise PKI systems, creates a dangerous window of vulnerability. Adversaries can already be collecting sensitive, long-lived encrypted data with the intent of decrypting it once sufficiently powerful quantum computers become available. Therefore, preparing for the post-quantum era requires a fundamental shift in vulnerability management strategy, moving beyond simple patch mentalities to embrace comprehensive crypto-agility frameworks that address discovery, prioritization, and systemic change across an organization's entire digital footprint.

Background

▶ Watch: The 'timing problem' of post-quantum migration (0:00)

The talk opens by stressing the immediate relevance of post-quantum cryptography (PQC), framing it not as a future-gazing exercise but as a present-day "timing problem" and an "inventory and sequencing problem." This urgency stems from the observation that legacy cryptography remains alarmingly prevalent across the internet and within enterprise environments. Singh presented data from ZoomEye, an internet data intelligence platform, revealing that systems relying on outdated cryptographic standards are far from hypothetical. Specifically, RSA 1024 was found on 19.3 million assets, TLS 1.0 on 8.6 million assets, and TLS 1.1 on 2.24 million assets. A category breakdown highlighted that web applications, routers, and wireless access points collectively represent a significant portion (up to 64%) of these vulnerable assets.

Further corroborating this issue, anonymous internal data from Qualys's detection workflow showed a similar landscape within enterprise networks. TLS 1.0 was flagged on 34.5 million assets, TLS 1.1 on 25 million assets, and surprisingly, RC4—a cipher deprecated by NIST in 2010—was still active on 13.2 million assets. Weak TLS key exchanges also persist. In stark contrast, early signals for PQC adoption, such as PQC exchange support and PQC signature algorithm support, each registered around 714,000 instances, numbers significantly smaller than the legacy footprint. This disparity underscores that vulnerability management teams are currently grappling with a vast legacy problem while PQC visibility is only just emerging.

Singh then provided a concise overview of how quantum computing fundamentally changes the cryptographic landscape. Unlike classical computers that process information sequentially, quantum computers leverage phenomena like superposition and interference to exploit specific "useful structures" within mathematical problems. For security teams, this distinction is crucial: quantum algorithms don't just make things faster; they render previously infeasible cryptographic problems solvable. The two primary quantum algorithms of concern are Shor's algorithm and Grover's algorithm. Shor's algorithm poses an existential threat to public-key cryptography by efficiently solving the integer factorization problem and discrete logarithm problem. This directly breaks widely used algorithms like RSA, Diffie-Hellman (DH), Elliptic Curve Digital Signature Algorithm (ECDSA), and Elliptic Curve Diffie-Hellman (ECDH). Grover's algorithm, while not outright breaking symmetric cryptography, provides a quadratic speedup for brute-force searches, effectively halving the security strength of symmetric keys and necessitating a doubling of key sizes.

Post-Quantum Cryptography (PQC) is presented as the practical, defensive response: quantum-resistant algorithms designed to run on today's classical hardware. The goal is to deploy these algorithms now, without waiting for the advent of fault-tolerant quantum computers. Key PQC families include lattice-based, code-based, hash-based, and multivariate cryptography. Singh draws parallels to historical cryptographic deprecations, such as the move from TLS 1.0/1.1 and RC4, or SSH RSA and SHA-1. These past transitions offer valuable lessons for PQC migration: the need to accurately identify where cryptography is in use, map ownership, track client and server dependencies, and verify runtime negotiation. However, PQC introduces additional complexity, demanding a more integrated approach to hybrid transport and certificate management.

Key Findings

▶ Watch: Defining Post-Quantum Cryptography (PQC) and its algorithms (8:50)

The talk highlights several critical findings that underscore the urgency and complexity of the post-quantum transition for vulnerability management:

Firstly, the most significant finding is the immediacy of the quantum threat due to the Harvest Now, Decrypt Later (HNDL) attack model. This means that adversaries are not waiting for quantum computers to become fully operational; they are actively collecting encrypted data today, anticipating future decryption capabilities. This transforms quantum risk from a future architectural concern into a present-day "planning problem." Singh introduced the Moskowitz inequality model (X + Y > Z), where X is data confidentiality lifetime, Y is migration duration, and Z is time until break capability. If the sum of X and Y exceeds Z, an organization faces a current planning crisis, particularly for long-lived, high-value data in sectors like health and government.

Secondly, Singh's data analysis revealed the pervasive and persistent nature of legacy cryptography. Both public internet scans (ZoomEye) and internal enterprise vulnerability data (Qualys) demonstrate that outdated algorithms like RSA 1024, TLS 1.0, TLS 1.1, and even RC4 are still widely deployed. This vast "technical debt" in cryptography significantly complicates the PQC transition, as organizations must first address existing vulnerabilities before moving to quantum-resistant solutions. The contrast with the minimal current visibility of PQC signals (around 714K instances) further emphasizes the scale of the challenge.

Thirdly, the talk establishes that PQC migration is fundamentally an inventory and sequencing problem, requiring a comprehensive framework rather than a simplistic "patch mentality." Enterprise Public Key Infrastructure (PKI) is deeply embedded across an organization's entire technology stack, touching trust stores, Hardware Security Modules (HSMs), vendor components, embedded devices, and load balancers. A patch-based approach, merely swapping out a cryptographic library, is insufficient and likely to fail due to these complex interdependencies. A holistic framework is needed for discovery, triage, ownership, and governance.

Fourthly, Singh presented a prototype quantum risk scoring model to help organizations prioritize migration efforts. This model evaluates cryptographic assets based on three key dimensions: Weakness (how severely Shor's or Grover's algorithm impacts the crypto), Impact (confidentiality lifetime, trust boundary exposure), and Migration Effort (organizational maturity, hardware dependencies). This scoring system provides a practical method for determining "what moves first," guiding vulnerability teams to focus on the highest-risk, most critical components. An internet-facing TLS VPN, for example, scored high due to its exposure and susceptibility to Shor's algorithm, coupled with significant migration effort due to hardware dependencies.

Finally, the talk underscored the fragility of PKI dependency order. Singh illustrated how changes to the certificate chain (Root CA, Intermediate CA, Leaf Certificate) must be executed in a precise sequence. Out-of-order changes risk widespread outages, loss of monitoring visibility, and client trust warnings. This highlights that PQC migration is not just a technical upgrade but a complex engineering challenge demanding meticulous planning and execution to maintain operational continuity.

Technical Deep Dive

▶ Watch: PQC migration requires a framework, not just patches (15:00)

The technical depth of the talk centers on understanding the mechanisms of quantum attacks, the practical implications of PQC, and the intricate requirements for a successful migration framework.

At the heart of the quantum threat are Shor's algorithm and Grover's algorithm. Shor's algorithm directly targets the mathematical foundations of modern public-key cryptography. It efficiently solves the integer factorization problem, which underpins RSA, and the discrete logarithm problem, which secures Diffie-Hellman, ECDSA, and ECDH. This means that once a sufficiently powerful quantum computer is built, these widely deployed algorithms will be rendered completely insecure, allowing adversaries to decrypt historical and real-time communications, forge digital signatures, and impersonate entities. Grover's algorithm, while less catastrophic for symmetric cryptography, provides a quadratic speedup for brute-force key searches. This implies that an N-bit symmetric key would effectively offer only N/2 bits of security. The practical implication is that organizations must double their symmetric key sizes (e.g., move from AES-128 to AES-256) to maintain equivalent security levels in a post-quantum world.

Post-Quantum Cryptography (PQC) algorithms are designed to resist these quantum attacks while operating on existing classical hardware. Singh emphasized that PQC is not about waiting for quantum computers to defend against them, but about deploying quantum-resistant algorithms today. The main families of PQC algorithms currently being standardized and researched include lattice-based cryptography (e.g., CRYSTALS-Kyber for key exchange, CRYSTALS-Dilithium for signatures), code-based cryptography (e.g., Classic McEliece), hash-based cryptography (e.g., SPHINCS+), and multivariate polynomial cryptography. These new algorithms have different performance characteristics (key sizes, signature sizes, computational overhead) compared to their classical counterparts, which needs to be factored into system design.

The critical concept of the Moskowitz inequality model (X + Y > Z) provides a mathematical framework for understanding the urgency. X represents the confidentiality lifetime of data (how long it needs to remain secret), Y is the migration duration (the time an organization realistically needs to transition its crypto), and Z is the time until break capability (when a quantum computer can break current crypto). If X + Y > Z, the organization has a present-day planning problem, as data encrypted today could be at risk before the migration is complete. This highlights the particular vulnerability of long-lived strategic data, such as health records or government secrets, which demand indefinite privacy.

Singh detailed that PQC migration requires a comprehensive framework rather than a simple "patch mentality." This framework involves several stages:

1. Detect: Identifying all cryptographic algorithms, protocols, certificate paths, dependencies (e.g., HSMs), and associated assets. The output is an inventory, not a solution.
2. Triage: Product security and security architecture teams assess the detected signals. This involves determining data sensitivity, relevant timelines, and evaluating mitigation options such as direct replacement, temporary mitigations, or time-bounded exceptions.
3. Own: Platform teams validate whether detected cryptography is actively in use in production and take ownership of the remediation.
4. Governance: Establishing policies for deprecating old algorithms, approving exceptions, and rejecting non-compliant implementations. This helps break the "endless backlog" cycle.
5. Tracking: Moving beyond standard patch tickets to richer tracking fields that include asset details, algorithms, protocols, owners, risk tiers, and exception expiry dates.

A significant technical hurdle highlighted is the fragile PKI dependency order. A typical PKI chain involves a Root CA, which signs Intermediate CAs, which in turn sign Leaf Certificates used by clients and servers. This hierarchy means that any change must cascade down the chain. Modifying a Root CA without proper planning for Intermediate and Leaf certificates, or without updating client trust stores and server configurations, will lead to widespread outages. Clients will fail to verify trust chains, servers' API endpoints may be affected, and monitoring systems might lose visibility of encrypted traffic, creating a "blast radius" of operational disruption. This necessitates a sequential, carefully orchestrated migration, often involving hybrid certificates that include both classical and post-quantum public keys to ensure backward compatibility during the transition.

<h2>Demo / Proof of Concept</h2>

While a live software demonstration was not part of the presentation, Arun Singh effectively illustrated the proposed quantum risk scoring model through a scorecard example. This served as a conceptual proof of concept for how organizations can prioritize their cryptographic migration efforts.

The scorecard evaluates assets based on three criteria:

1. Weakness: How susceptible the cryptography is to quantum attacks (e.g., Shor's algorithm for public-key, Grover's for symmetric).
2. Impact: The consequences of a compromise, considering factors like the confidentiality lifetime of the data protected and the exposure level of the device (e.g., internet-facing vs. internal).
3. Migration Effort: The difficulty and resources required for remediation, accounting for hardware dependencies (like HSMs), software changes, and organizational maturity.

Singh provided two concrete examples to demonstrate the scoring:

• Internet-facing TLS VPN: This was assigned a weakness score of 2 (high, as Shor's algorithm directly impacts the public-key cryptography used for key exchange). Its impact score was 3 (highest), due to its exposure at the trust boundary and the high-value sessions it protects. The migration effort was rated 2 (high), as it often involves replacing hardware and significant configuration changes, including HSMs. This combination resulted in a priority tier of 4 (highest), indicating an urgent need for migration.

• Symmetric at control: This example represented internal symmetric cryptography. It received a weakness score of 0 (lowest), as Grover's algorithm does not outright break symmetric keys, only requiring a key size increase. The impact score was 2 (medium), acknowledging that the protected data, while not exposed on the internet, is still valuable. Crucially, the migration effort was only 1 (low), as it primarily involves doubling key sizes through configuration or variable changes, rather than a complete system overhaul. This yielded a priority tier of 1, indicating a lower but still necessary priority.

These examples clearly demonstrated how the scoring system can differentiate between various cryptographic assets, providing a structured approach to allocate resources and plan migration activities effectively.

Defensive Implications

▶ Watch: Understanding fragile PKI dependencies and migration risks (21:20)

The insights from this talk provide a clear mandate for defenders: proactive and comprehensive action is required now to mitigate the impending quantum threat.

1. Act Immediately, Plan Strategically: The "Harvest Now, Decrypt Later" threat means waiting for a quantum breakthrough is too late. Organizations must initiate PQC planning and migration efforts immediately, focusing on long-lived, high-value data whose confidentiality lifetime (X) combined with migration duration (Y) risks exceeding the time until quantum break capability (Z).

1. Comprehensive Cryptographic Inventory: Go beyond simple certificate spreadsheets. Defenders must discover all cryptographic dependencies, including public keys, PKI libraries, HSMs, embedded devices, vendor components, and even legacy "bad workflows." This detailed inventory is the foundation for any effective PQC strategy.

1. Prioritize with a Risk-Based Approach: Implement a risk scoring model (like the one proposed) that considers the quantum weakness of algorithms (Shor's impact on public-key vs. Grover's on symmetric), the impact of compromise (data confidentiality, exposure), and the migration effort. This enables defenders to allocate resources efficiently, focusing on the highest-priority assets first.

1. Adopt a PQC Framework, Not a Patch Mentality: Recognize that PQC migration is a systemic engineering challenge, not a simple technical patch. Develop a robust framework encompassing discovery, triage, ownership, governance, and enriched tracking to manage the complexities of enterprise PKI, which is deeply interwoven with hardware, software, and vendor ecosystems.

1. Engage All Stakeholders: PQC migration is not solely an IT security function. It requires broad collaboration across product security, security architecture, platform teams, operations, procurement, and external vendors. Clear ownership must be assigned for assets and their cryptographic components.

1. Integrate Crypto-Agility into Procurement: Make "crypto-agility" a mandatory buying rule for all new products and services. Organizations must avoid acquiring new systems that lack a clear vendor path for PQC migration, as this introduces new liabilities and extends overall transition timelines.

1. Leverage Existing VM Workflows: Instead of creating entirely new processes, integrate PQC migration tasks into existing vulnerability management, governance, and renewal cycles. This ensures that PQC considerations become a natural part of ongoing security operations.

1. Address PKI Dependencies with Caution: Be acutely aware of the "fragile PKI dependency order." Plan changes to Root CAs, Intermediate CAs, and Leaf Certificates meticulously and sequentially to avoid widespread outages, loss of visibility, and client trust issues. Hybrid certificates will be crucial for maintaining backward compatibility during transition.

1. Double Symmetric Key Sizes: For symmetric cryptography, a direct defensive implication is to plan for doubling key sizes (e.g., from AES-128 to AES-256) to compensate for the quadratic speedup offered by Grover's algorithm. This is often a less disruptive change but still requires planning and implementation.

Key Takeaways

• Quantum risk is a present-day planning problem, not a future one. The "Harvest Now, Decrypt Later" threat demands immediate action, especially for long-lived, sensitive data.
• Legacy cryptography is pervasive, while PQC visibility is minimal. Organizations must address significant technical debt in outdated cryptographic implementations (e.g., RSA 1024, TLS 1.0/1.1, RC4) while simultaneously preparing for PQC.
• PQC migration requires a comprehensive framework, not just technical upgrades. Due to the deep integration of PKI across enterprise systems, a holistic approach to discovery, triage, ownership, and governance is essential to avoid a "patch mentality" failure.
• Prioritize migration using a structured risk scoring model. Evaluate cryptographic assets based on their quantum weakness, impact of compromise, and the effort required for migration to guide resource allocation and ensure "what moves first."
• Crypto-agility must become a core buying rule and be integrated into existing workflows. Incorporating PQC considerations into procurement and leveraging established vulnerability management processes are crucial for sustainable transition.
• Meticulous planning for PKI dependency order is critical. Changes to certificate chains must be sequenced precisely to prevent widespread outages, loss of monitoring, and client trust failures during the migration.

About the Speaker(s)

Arun Singh is a Security Research Engineer at Qualys. His work focuses on critical security challenges, as demonstrated by his expertise in vulnerability management and the transition to post-quantum cryptography.