Post-Quantum Migration Is Not a Library Upgrade, It Is a Distributed Systems Problem

The easiest way to underestimate post-quantum migration is to draw it as a one-line change: RSA / ECDH / ECDSA -> ML-KEM / ML-DSA / SLH-DSA That picture is cryptographically tidy and operationally wrong. Take one ordinary API request. It may terminate TLS at a managed load balancer, pass through an API gateway, traverse an Envoy-based service mesh, authenticate with an OIDC workload identity, retrieve secrets from a vault, and persist data behind a cloud KMS. The path may also depend on certificate authorities, trust bundles, language runtimes, container images, and signed deployment artifacts. Every hop can have a different algorithm, provider, owner, release cycle, and rollback mechanism. So changing one TLS library while leaving gateway certificates, JWT signing, mesh mTLS, KMS key wrapping, or vendor-managed identity flows untouched does not materially reduce the system's exposure. It may only create a new and harder problem: a mixed cryptographic estate that nobody can accurately describe. The right unit of migration is not the library. It is the dependency graph. A single request can cross several independently managed cryptographic surfaces. Each one must be discovered, owned, and governed. The Standards Are Here. The Operating Model Is Missing. NIST published FIPS 203 for ML-KEM, FIPS 204 for ML-DSA, and FIPS 205 for SLH-DSA in 2024. The question is no longer whether standardized post-quantum algorithms exist. The harder question is: how does an enterprise change hundreds or thousands of cryptographic dependencies without breaking production? NIST CSWP 39upd1 defines crypto agility as the capability to replace and adapt cryptographic algorithms while preserving security and ongoing operations. That definition matters because it shifts the goal from "deploy a new algorithm" to "build a system that can survive repeated algorithm changes." For cloud-native environments, that capability needs to behave like a control plane. It should answer: Where is public-key cryptography used? Which data, trust roots, and endpoints face the greatest quantum exposure? Where is an algorithm hard-coded, and where can policy change it? Which clients and services can negotiate a hybrid mode? What production signals prove that a rollout is safe? Which legacy exceptions still exist, who owns them, and when do they expire? This is the gap the Cloud-Native Crypto-Agility Framework, or CN-CAF, is designed to fill. Start With a Cryptographic Dependency, Not an Asset List Traditional inventories tend to list servers, applications, or certificates. A useful post-quantum inventory must capture the relationship between them. For every cryptographic dependency, record at least: Asset: the service, endpoint, certificate, key, image, or library. Locus: where the cryptographic decision is made, such as an app library, gateway, sidecar, issuer, KMS, CI/CD system, or cloud IAM provider. Protocol or use: TLS, mTLS, JWT signing, KMS wrapping, image signing, or another operation. Algorithm: the current classical, hybrid, or PQC choice. Data lifetime: how long the protected information must remain confidential. Exposure: internet-facing, partner-facing, internal, administrative, or data-plane. Provider and owner: who implements the cryptography and who is accountable for migration. Replacement path: policy change, certificate rotation, dependency upgrade, source-code change, or vendor action. Evidence: a CBOM record, scan result, runtime observation, test, approval, or telemetry link. The CycloneDX Cryptography Bill of Materials provides a useful representation for this evidence. But a CBOM is a foundation, not the finished operating model. Inventory data must drive prioritization, enforcement, rollout, and rollback. This also changes how "unknown" is treated. If a production dependency uses public-key cryptography but has no owner, algorithm, provider, or evidence record, it should not receive a neutral score. It should be classified as unknown and high risk. The Eight Ways a PQC Migration Can Fail Most migration failures will not begin with a quantum computer. They will begin with ordinary distributed-systems problems. 1. Harvest-now-decrypt-later exposure An adversary can record encrypted traffic today and wait for a future cryptographically relevant quantum computer. That makes long-lived confidential data, internet-facing TLS, partner APIs, backups, and replication channels early priorities. 2. Hidden cryptographic dependencies Cryptography hides in base images, Java keystores, SDKs, database drivers, sidecar defaults, managed gateways, and signing tools. If a dependency is absent from the inventory, it cannot be prioritized, tested, or retired. 3. Hard-coded algorithm coupling Applications that directly select RSA, ECDH, ECDSA, key sizes, or certificate profiles require a code change for every transition. They also make emergency replacement much harder if an implementation or parameter set is later deprecated. 4. Hybrid interoperability and downgrade failure Clients and servers will not migrate at the same time. Misconfigured negotiation can create outages, silent fallback to classical-only modes, or downgrade paths that make a "hybrid" deployment quantum-vulnerable in practice. 5. Performance regression PQC and hybrid handshakes can change message sizes, CPU cost, memory use, and certificate-chain size. In a service mesh, that cost is multiplied across high-cardinality east-west traffic. A cryptographically correct migration can still exhaust proxies or control planes. 6. Certificate and trust-bundle drift A gateway may trust a new issuer while an old sidecar, partner client, or SaaS integration rejects the chain. Temporary fallback certificates also have a habit of becoming permanent when nobody owns the expiration date. 7. Managed-service asymmetry Cloud IAM, OIDC providers, and managed KMS products often abstract the algorithms from tenants. You may control federation settings but not the provider's signing keys or migration schedule. Vendor readiness is therefore a first-class dependency, not a footnote. 8. Weak evidence A team may report that it upgraded a library while runtime telemetry still shows classical-only negotiation. Configuration intent is not proof of production behavior. CN-CAF: A Seven-Step Control Loop CN-CAF treats migration as a continuous loop because cloud-native systems never stop changing. Services are deployed, certificates rotate, base images rebuild, gateways reconfigure, and providers update managed implementations. The lifecycle is: Discover. Combine static scans, runtime observation, and control-plane extraction. Search code, manifests, images, IaC, Helm charts, TLS handshakes, certificate chains, KMS audit logs, Kubernetes CSRs, cert-manager resources, mesh policy, and cloud IAM flows. Classify. Rank dependencies by algorithm vulnerability, data lifetime, exposure, trust role, ownership, and replacement difficulty. Abstract. Move direct algorithm choices behind stable provider interfaces, configurable TLS libraries, service-mesh policy, certificate issuers, or KMS APIs. Pilot. Enable hybrid-capable behavior on a small canary population and run compatibility tests. Enforce. Use gateway policy, mesh configuration, admission controls, certificate profiles, and CI/CD gates to prevent drift. Monitor. Measure negotiation, latency, errors, CPU, certificate validation, downgrade signals, exceptions, and CBOM completeness. Retire. Disable legacy algorithms only when telemetry proves they are no longer needed or every remaining exception has an owner and expiry date. The loop is held together by four invariants: Every production dependency is known and owned, or it is treated as high risk. New algorithm choices are policy-mediated, not buried in business logic. Migration passes through a hybrid-capable state before classical algorithms are disabled. Every step emits evidence and has a tested rollback path. Use Cloud-Native Choke Points The most efficient migration points are the places that already centralize cryptographic decisions. API gateways and ingress controllers are high-leverage surfaces for public TLS. They can expose negotiated groups, certificate signatures, error rates, and client compatibility without requiring every application to own the handshake. Service meshes can shift internal mTLS migration into proxies and control-plane policy. This reduces application rewrites, but it raises a different risk: the cost of larger or more expensive handshakes is multiplied across every service-to-service connection. Roll out by namespace or workload label, baseline p95/p99 latency and proxy CPU, and connect error-budget burn to automatic rollback. Certificate automation through Kubernetes CSR APIs, cert-manager, and issuer abstractions creates a controllable path for testing new certificate profiles and rotating trust bundles. The real compatibility test is not whether an issuer can produce a certificate. It is whether every workload, client, partner, and trust store can validate the complete chain. SPIFFE/SPIRE and workload identity systems should be treated as cryptographic roots of trust. Inventory SVID issuers, trust bundles, validity periods, rotation behavior, and client constraints before introducing new profiles. Cloud IAM and OIDC require a vendor-aware strategy. Track token issuers, JWKS endpoints, TLS dependencies, provider signing choices, and contract evidence. Short-lived federated credentials reduce credential exposure, but they do not automatically make the signing chain post-quantum. KMS and HSM services should be modeled as key-hierarchy graphs: root keys, wrapping keys, data keys, import/export paths, firmware, SDKs, and cross-region operations. Most data-at-rest encryption is symmetric; the migration concern is the public-key operation around the hierarchy. CI/CD and artifact signing deserve early attention when signatures must remain verifiable for years. Firmware, software updates, image signatures, and attestations do not have the same threat clock as short-lived TLS authentication. A Migration Needs States, Not a Boolean "PQC enabled" is too vague to be useful. Each dependency should move through explicit states. S0 — Classical only: RSA, ECDH, or ECDSA is accepted. S1 — Hybrid capable: clients and servers can negotiate a hybrid mode. S2 — Hybrid preferred: policy prefers hybrid ECDHE + ML-KEM while retaining a controlled fallback. S3 — PQC primary: post-quantum algorithms are on the primary path where the protocol and ecosystem support it. S4 — Legacy disabled: classical exceptions have expired and old algorithms are blocked. Promotion must be gated by evidence: handshake success, peer capability, no downgrade, path validation, p95/p99 latency, proxy CPU, KMS latency, error rate, and rollback success. There also need to be two deliberate escape paths. A rollback path returns the dependency to the previous policy state when an error budget is breached. An exception path allows a legacy peer to remain temporarily, but only with an accountable owner, compensating controls, a limited blast radius, and an expiration date. Without explicit states, hybrid support becomes permanent dual-stack support and classical algorithms never actually leave. Measure Exposure, Not Activity A migration program can generate thousands of tickets and still fail to reduce meaningful risk. The useful metrics answer five questions: Inventory: Do we know where cryptography is used? Track inventory coverage, unknown algorithms, CBOM completeness, and owner coverage. Risk: Which vulnerable dependencies matter most? Track long-lifetime data, internet-facing endpoints, critical trust roots, and replacement difficulty. Migration: Are changes reaching production? Track hybrid/PQC-enabled dependencies, legacy-disabled dependencies, and rollout progress by service or namespace. Interoperability and performance: Is the change safe for real peers and workloads? Track handshake failures, fallback, downgrade alerts, client compatibility, proxy CPU, certificate size, KMS latency, and error-budget burn. Governance: Is residual risk controlled? Track policy drift, open exceptions, mean exception age, vendor evidence, deploy-gate denials, and rollback recovery time. A simple prioritization score can multiply four factors: Quantum Exposure Score = algorithm vulnerability X data-lifetime weight X exposure weight X replacement-path difficulty The exact weights will vary. Transparency matters more than false mathematical precision. Platform, security, and application teams should be able to explain why one API, issuer, or trust root is being migrated before another. A Practical 90-Day Starting Plan You do not need to make every workload PQC-only this quarter. You do need to make the migration tractable. Days 1–30: establish visibility and ownership. Inventory public endpoints, service-mesh policies, Kubernetes certificates and Secrets, OIDC issuers, KMS public-key operations, signing keys, and cryptographic libraries. Attach an owner and evidence source to every production dependency. Days 31–60: rank and abstract. Prioritize long-lived confidential data, internet-facing edges, critical trust anchors, and hard-to-replace dependencies. Identify algorithm choices that can move into gateway, mesh, issuer, provider, or KMS policy. Record vendor-managed gaps explicitly. Days 61–90: pilot and instrument. Select a narrow public TLS or service-mesh canary where the client population is measurable. Define success, downgrade, performance, and rollback gates before changing policy. Create time-bounded exceptions for unsupported peers and publish a dashboard for inventory, rollout, interoperability, performance, and governance. This work delivers value even before every platform supports every post-quantum primitive. It replaces uncertainty with an owned migration path. The Real Goal Is Reachability Post-quantum migration is a distributed-systems change across gateways, proxies, certificates, identities, KMS, CI/CD, vendors, and application code. The goal is not PQC-only tomorrow. It is to make each dependency visible, owned, risk-ranked, policy-reachable, observable, and attached to a tested rollback path. With that control plane, migration becomes governed state transitions instead of emergency rewrites—the essence of cloud-native crypto agility.