Crypto-Agility in Practice: A Design Guide for Architects

In August 2022, about four weeks after NIST announced that SIKE would continue into a fourth round of evaluation, two researchers at KU Leuven published an attack that recovered SIKEp434 private keys in roughly an hour on a single classical processor core (Castryck and Decru, IACR ePrint 2022/975). SIKE was an isogeny-based key exchange with an unusually small public key, and several teams had been prototyping with it. Six months earlier, Rainbow, a finalist signature scheme, had fallen to an attack that recovered a key over a weekend on a laptop (Beullens, IACR ePrint 2022/214).

Neither break involved a quantum computer. Both were ordinary cryptanalysis, arriving after years of public scrutiny, at the point in the process where scrutiny is supposed to be most intense. And the set of standardised algorithms has kept moving since: NIST selected HQC as a backup key encapsulation mechanism in March 2025 (NIST IR 8545), on the reasoning that ML-KEM (Kyber) and HQC rest on different mathematical assumptions, so a break in one is unlikely to break the other.

That is the practical case for crypto-agility, and it doesn’t depend on any forecast about when a cryptographically relevant quantum computer arrives. The algorithms an architect can rely on change on a schedule nobody controls. The question is what your systems do when the change comes.

Most published guidance on crypto-agility answers that question at the level of committees, policies, and awareness programs. This article answers it at the level of interfaces, wire formats, and key custody, because that’s where a substitution succeeds or stalls.

What Crypto-Agility Means at the Design Level

Crypto-agility is often described as the ability to switch algorithms. That description is too loose to design against, because almost every system can switch algorithms given enough time and enough downtime.

A more useful definition has two variables. Time to substitute is the elapsed time from a decision to replace a cryptographic primitive to that replacement running in production across every instance. Reach is how much of the system a substitution touches: how many code paths, how many stored records, how many external parties have to change something on their side. An agile system substitutes quickly and touches little. A system that needs a coordinated release across nine services, a data migration, and a renegotiation with four partners is not agile, no matter how many algorithms its libraries support.

Both variables are measurable, and we recommend teams measure them before they design anything. The simplest way to get a number is a substitution test on a system you already run.

Pick one primitive in one service. Then answer five questions with evidence rather than estimates:

1. How many distinct call sites invoke this primitive, counting configuration files, infrastructure templates, and anything a partner integrates against?
2. Where is the algorithm named? In source, in a config value, in a database column, in a certificate, in a protocol negotiation, or in several of these with no single source of truth?
3. What assumes the current sizes? Fixed-width columns, allocated buffers, message length limits, hardware token capacity.
4. What data already encrypted under the old primitive has to remain readable, and for how long?
5. Who else has to agree? Every counterparty, every embedded device, every long-lived client.

Teams that run this exercise usually find the answer to question one is larger than expected and the answer to question two is “several places, inconsistently.” That is the real starting position, and it’s a better input to a roadmap than a maturity score.

The Five Places a Substitution Touches

A cryptographic change propagates through a system along predictable paths. Designing for agility means deciding, deliberately, what each path looks like.

The call site

This is application code that asks for a cryptographic operation. Agility here comes from routing every request through one internal interface rather than calling library functions directly from twelve services. The interface doesn’t have to be sophisticated. It has to be the only door.

The wire

Two parties have to agree on which algorithm they’re using. Protocols that negotiate this at connection time, with algorithm identifiers exchanged in the handshake, allow one side to add support before the other. Protocols that assume the algorithm, or that hard-code an identifier in a client build, force simultaneous upgrades on both sides.

Stored formats

Anything written to disk with a cryptographic transformation applied is a commitment that lasts as long as the record. A stored blob that carries no algorithm identifier and no version field cannot be re-keyed selectively, because nothing in the record says what produced it. Adding a version byte to a ciphertext envelope is the cheapest agility investment available, and it can only be made before the data is written.

Key custody

Keys live in hardware security modules, cloud key services, smartcards, secure elements, and configuration secrets. Each custodian supports a fixed set of algorithms and key sizes, and each one changes on its vendor’s timetable rather than yours. A key custodian that can’t generate or store a 2,400-byte private key will block a migration that the application layer is entirely ready for.

The trust chain

Certificates bind identities to public keys, and each certificate is signed by another key up a chain to a root. Substituting a signature algorithm means every relying party has to accept the new one, which is the slowest of the five paths and the one with the most external dependencies.

Post-Quantum Primitives Change Shape, Not Just Size

The most common design failure we see in migration work is an abstraction built for the wrong shape. Teams create an internal interface, feel appropriately agile, and then discover that the new primitive doesn’t fit through it.

The clearest example is key establishment. RSA key transport works like this: the sender picks a symmetric key, encrypts it with the recipient’s public key, and sends it. An interface shaped as encrypt(recipientPublicKey, secret) describes that operation exactly.

ML-KEM is a key encapsulation mechanism, or KEM. A KEM works differently. The sender runs an encapsulation function against the recipient’s public key, and the function returns two things: a ciphertext to transmit, and a shared secret derived inside the function. The sender doesn’t choose the secret. There is no slot to put one in. So encrypt(recipientPublicKey, secret) cannot host ML-KEM, and every service that calls it has to change, which is exactly the outcome the abstraction was built to prevent.

The correct abstraction for key establishment is the KEM shape, because RSA key transport can be expressed as a KEM and a KEM cannot be expressed as key transport. Systems designed around encapsulate and decapsulate today will accept a new KEM tomorrow with a configuration change.

Three further shape changes are worth knowing before you design:

There is no post-quantum equivalent of static Diffie-Hellman. Diffie-Hellman lets two parties derive a shared secret from long-term public keys without either sending a message first. Protocols built on that property, including some authenticated key agreement patterns and offline device provisioning schemes, have no direct post-quantum replacement. They need redesign, not substitution.

Some hash-based signature schemes are stateful. LMS and XMSS require the signer to track which one-time key has been used, and reusing one destroys the security of the scheme. That obligation reaches into backups, virtual machine snapshots, and failover, none of which are cryptographic concerns in an ordinary signing deployment. SLH-DSA (SPHINCS+) is the stateless alternative and avoids the problem at the cost of much larger signatures.

Signing has different randomness requirements. ML-DSA (Dilithium) signing is hedged by default, mixing fresh randomness with a deterministic derivation. Deployments that assumed deterministic signatures for reproducibility, or that run in environments with a weak entropy source, need to check this explicitly.

The Size Problem, With Numbers

Post-quantum keys and signatures are larger than what they replace, and the gap is wide enough to break assumptions that have held for twenty years. The figures below come from FIPS 203, FIPS 204 and FIPS 205, with the FN-DSA numbers from the Falcon submission that the draft standard is based on.

Primitive	Public key	Signature or ciphertext
RSA-2048	256 bytes	256 bytes
ECDSA P-256	65 bytes	64 bytes (raw)
ML-KEM-768	1,184 bytes	1,088 bytes
ML-DSA-65	1,952 bytes	3,309 bytes
FN-DSA-512 (draft)	897 bytes	about 666 bytes
SLH-DSA-SHA2-128s	32 bytes	7,856 bytes

A move from ECDSA P-256 to ML-DSA-65 multiplies signature size by roughly 50. Four consequences follow, and each one is a design decision rather than a tuning exercise.

Handshakes stop fitting in one packet. A TLS handshake carrying a hybrid key share plus a certificate chain signed with ML-DSA can run to several kilobytes, and it crosses the point where a single round trip stops being enough on constrained links. Where latency is part of the product, measure it on the real network rather than in a lab.

Storage assumptions break loudly and quietly. A fixed-width database column truncates. A hardware token with 8 KB of usable storage refuses the key. Both are recoverable. The quiet failure is a system that accepts the larger value and degrades somewhere unrelated, such as a log pipeline that starts dropping records.

Certificate chains grow multiplicatively. Every certificate in a chain carries both a public key and a signature. Replacing both across a three-certificate chain turns a chain of roughly one kilobyte into one of ten or more.

SLH-DSA is a different operational proposition. A 7,856-byte signature is acceptable for firmware images signed a few times a year and unacceptable for per-transaction signing. It’s the conservative choice for long-lived signing roots, because its security rests only on the hash function, and it belongs where its size doesn’t recur.

Inventory Is the Input, Not the Project

You can’t substitute what you can’t find, so an inventory comes first. The failure mode here is producing a document that says the organisation uses AES-256, RSA-2048 and SHA-256, which is true and useless.

A cryptographic bill of materials, or CBOM, is a machine-readable record of cryptographic assets and their dependencies, expressed in a standard format so that tooling rather than a spreadsheet keeps it current. The CycloneDX specification added support for this in version 1.6.

Whatever format you choose, the fields that make an inventory actionable are the ones that answer the substitution test:

• The primitive and parameter set, not the family. “ECDSA” isn’t an entry; “ECDSA P-256 for client authentication” is.
• The call site, down to the service and the code path.
• The key custodian and what algorithms it supports today.
• The data lifetime protected by that primitive, which is what decides urgency for anything confidentiality-related.
• The external dependency, meaning whoever else has to agree before this can change.
• The owner, an actual named team.

Two of these are usually missing from first attempts. Data lifetime is missing because nobody asked the business how long the records need to stay confidential. External dependency is missing because it doesn’t appear in code scanning, and it is the field that most often determines the true timeline. The PQC Framework, published at pqcframework.org, works through inventory and prioritisation as a migration methodology in more depth than we can here.

Automated discovery is necessary and insufficient. Scanners find libraries, network scanners find negotiated ciphersuites, and neither finds the algorithm choice embedded in a contract with a payment processor.

Designing the Interface

Once you know what you have, the design question is where to put the boundary between application code and cryptographic implementation.

Put it at the level of the cryptographic purpose, not the algorithm and not a generic facade. Interfaces named for what the caller wants achieved, such as establishSharedSecret, signArtifact, protectRecordAtRest, survive a substitution. Interfaces named aesEncrypt don’t. Interfaces named Crypto.encrypt() are worse than both, because they hide parameter choices that the caller has to make correctly and give the impression that any algorithm can be dropped in.

Four properties make the boundary useful:

Algorithm selection is configuration, not code. The primitive in use should be readable from a configuration source at runtime and changeable without recompiling. This also gives you a single place to answer “what are we actually running in production right now,” which is a question most organisations answer slowly.

Every protected artefact declares its algorithm. A version or algorithm identifier travels with each ciphertext, signature, and stored blob. Without it, decrypt-and-re-encrypt migrations require you to guess or to migrate everything at once.

The system reads more than it writes. During any transition, a system needs to verify or decrypt under both the old and new primitive while producing output under only one. Design the read path for plurality and the write path for a single configured choice, and a migration becomes a sequence of small, reversible steps.

Failure is explicit. When an unsupported algorithm identifier arrives, the code should reject it and say so. Silent fallback to a weaker option is how a downgrade becomes an incident.

Standard interfaces help where they exist. PKCS #11 gives a consistent interface to hardware key stores, and version 3.2 adds mechanisms for the new algorithms. Language-level provider frameworks let a new implementation register behind an existing interface. Where you use them, keep the provider selection in configuration too.

Hybrid and composite as agility mechanisms

Hybrid key establishment runs a classical and a post-quantum exchange together and derives the session key from both shared secrets, so an adversary must break both to recover it. It is the deployment pattern in current browser and server implementations, and it’s also a natural agility structure: the interface already handles two mechanisms and combines their outputs, which makes replacing one of them an ordinary operation.

Composite signatures apply the same idea to certificates, binding two signature algorithms into a single certificate so relying parties that understand only one can still validate. Standardisation work at the IETF is ongoing, and the pattern is worth designing for even where you don’t deploy it yet.

Hybrid carries costs, which we treat as a decision rather than a default. Two exchanges mean more bytes and more code, more implementation surface to get wrong, and a longer eventual path to a single-algorithm system. Different national authorities have taken different positions on how long hybrid should persist. What matters for design is that the plurality-capable interface is the same either way.

Operations: Rotation, Automation, and Shrinking Certificate Lifetimes

An agile design that depends on manual operations isn’t agile, because the constraint moves from the code to the change window.

The clearest current example is certificate lifetime. In April 2025 the CA/Browser Forum adopted Ballot SC-081v3, which reduces the maximum lifetime of a public TLS certificate in stages, reaching 47 days by March 2029, with intermediate steps of 200 days and 100 days. Any organisation still issuing and installing certificates by hand will find that schedule unworkable on its own terms, before any post-quantum change is considered. Automated issuance and renewal, typically through ACME, the protocol that lets a server prove control of a name and fetch a certificate without human involvement, becomes an operational requirement.

That requirement turns out to be the migration capability as well. An organisation that can reissue its entire certificate estate in a weekend without a maintenance window can also change its signature algorithm in a weekend. The capability that gets funded for compliance reasons is the same one that delivers agility, which is a useful argument to have available when you’re asking for the budget.

The same logic applies to keys. Rotation should be a routine automated operation exercised on a schedule, not an emergency procedure documented in a runbook nobody has run. A team that rotates keys monthly by automation has already proved it can re-key under a new algorithm. A team that has never rotated a production key is discovering two things at once, under time pressure.

Three operational capabilities are worth building explicitly for cryptographic incidents:

• A published inventory of what is affected, queryable by primitive, so that “which systems use ECDSA P-256” is answered in minutes rather than weeks.
• A tested path to an alternate certificate authority, including systems that already trust the alternate root, because a compromised or distrusted CA is a live scenario and has happened repeatedly.
• A rollback that works, since an algorithm change can degrade performance or interoperability in ways testing missed.

Rehearsing the Substitution

The only reliable evidence that a system is agile is a substitution that actually happened.

Run one, deliberately, on a schedule. Pick a service, change one primitive, and measure the elapsed time from decision to full production deployment. The first attempt will surface the assumptions nobody documented: the buffer sized for a 256-byte signature, the partner integration that pins an algorithm identifier, the hardware token that runs out of room. Those findings are the point of the exercise, and finding them during a rehearsal costs a fraction of what they cost during an incident.

Build the same check into continuous integration. A test suite that exercises the cryptographic interface against at least two different primitives, and fails when a code path only works with one of them, prevents agility from decaying quietly between rehearsals. Add a test that asserts every protected artefact carries an algorithm identifier, and another that confirms an unknown identifier is rejected rather than ignored.

Library currency belongs in the same pipeline. OpenSSL 3.5, released in April 2025, ships ML-KEM, ML-DSA and SLH-DSA in its default provider, and other major libraries have added support on their own schedules. Knowing which version of which library each service links against, and being able to update it without a release freeze, is part of the same capability.

How You Know You Have It

Crypto-agility resists a maturity score, but it takes a small number of honest measurements.

• Time to substitute, measured from the last rehearsal rather than estimated.
• Number of independent call sites for each primitive, which should be falling.
• Proportion of cryptographic operations that go through a managed interface rather than a direct library call.
• Proportion of protected artefacts that carry an algorithm identifier.
• Time to reissue the full certificate estate, which should be measured in hours.
• Number of external parties who must act before a given substitution can complete, which is the figure that usually sets the real timeline.

None of these mention a specific algorithm, and that’s deliberate. A system built to these properties handles the move to ML-KEM and ML-DSA, handles the addition of HQC if a second key encapsulation mechanism becomes prudent, and handles whatever follows from cryptanalysis nobody has published yet.

The regulatory deadlines give the work a date. NIST’s draft IR 8547 proposes 2030 for deprecating and 2035 for disallowing the 112-bit classical public-key algorithms in federal use, and the Commercial National Security Algorithm Suite 2.0 (CNSA 2.0) sets earlier end dates for national security systems depending on the system class. Those are the dates the substitution has to be finished by. The design decisions that make it possible are made now, in the interfaces and formats being written this quarter.

Taking This Further

The design patterns in this article are the practical layer of a larger migration discipline: inventory, prioritisation by data lifetime, protocol-level transition planning, and the governance that keeps an inventory accurate after the first audit. Architects who need the full methodology will find it worked through at pqcframework.org, and the broader technical background to this piece is at PostQuantum.com.

For architects who want structured training rather than reading, Quantum Academy runs post-quantum cryptography programs that cover algorithm selection, hybrid deployment, inventory practice, and migration design, with assessments built around the decisions this article describes. You can see the current catalogue at quantumacademy.com/.