Cryptographic agility is an interface problem

What makes a migration expensive

Every cryptographic migration in the historical record—from single DES, from SHA-1, from RSA-1024, from TLS 1.0—has followed the same cost curve. The new algorithm is available quickly. The transition takes years. And the years are not spent on cryptography.

They are spent finding where the old algorithm is used, discovering that some places cannot be changed without a coordinated release across teams, negotiating with counterparties whose systems cannot be changed at all, and re-processing data that was stored in a format which did not record which algorithm produced it.

NIST SP 800-131A documents that history as a sequence of transitions with defined deprecation and disallowed dates. Read as an operational forecast rather than a compliance reference, it makes a straightforward prediction: any cryptography you deploy today will need to be replaced within the life of the system, and the cost of that replacement is being fixed right now by design decisions that have nothing to do with which algorithm you pick.

Put the algorithm in the data

The single highest-value provision is also the cheapest: every piece of cryptographic output that is stored should carry an identifier for the scheme and key that produced it.

That means a ciphertext stored with a header naming the algorithm, mode, key identifier and any parameters. A signature stored alongside the scheme and the verifying key identifier. A password hash stored with the function name and its cost parameters. A message digest stored with the hash function.

The reason this matters is that migration then becomes incremental. A reader dispatches on the identifier and can handle old and new simultaneously; new writes use the new scheme; old data is re-processed lazily or by a background job. Without the identifier, a reader must assume, which means every stored item has to be converted before the assumption can change—a flag day across a data estate.

Password storage is the clearest illustration. A hash stored with its function and parameters allows an upgrade on next successful login, spread naturally over months, with no user-visible event. A bare digest with the scheme implied by deployment date means either a forced reset for everyone or an indefinite commitment to the original function.

One place to change the call

The second provision is ordinary software design applied to cryptographic calls. If the codebase calls a cryptographic library directly from eighty places, a migration is eighty changes, reviewed separately, deployed at different times.

An internal interface—encrypt, decrypt, sign, verify, derive, hash—with the scheme chosen from configuration inside it, makes the same migration one change plus a configuration rollout. The interface should also be where the algorithm identifier is written and read, so callers never see the scheme at all.

This has a secondary benefit that often matters more than the migration: it creates one place to review. A security review of eighty call sites samples; a review of one implementation is complete. And it prevents the slow accumulation of inconsistency, where six of the eighty call sites use a slightly different construction because they were written by different people in different years.

Two cautions. The interface should be narrow enough to be safe—offering a generic “encrypt with these parameters” reintroduces the problem it solves. And it should not become a permanent wrapper around every possible scheme; the accepted set is meant to move, not grow.

Protocols need a movable floor

For anything on the wire, agility is negotiation, and the standard protocols already provide it. TLS 1.3 negotiates key exchange, signature and cipher suite within a constrained set, and HPKE identifies its key encapsulation, derivation and authenticated encryption choices explicitly in its suite identifier.

The engineering work is not in obtaining negotiation; it is in being able to change what you accept. That requires three things:

• the accepted set expressed in configuration rather than compiled in, so raising the floor is a deployment rather than a release;
• the ability to observe what is actually negotiated in production, so you know what raising the floor would break;
• a defined process for dropping an option, including a communication path to counterparties who will be affected.

The second is routinely missing. An organisation that cannot answer “what proportion of connections currently negotiate the option we want to remove?” cannot raise its floor without risk, so it does not, and the weak option remains for years. Connection-level telemetry on negotiated parameters is cheap to add and is what makes deprecation a decision rather than a gamble.

RFC 8996 is worth reading as a case study in how long this takes when the telemetry and the process are absent.

Wrap keys so rotation is not re-encryption

A related form of rigidity has nothing to do with algorithms. If data is encrypted directly with a long-lived key, rotating that key means decrypting and re-encrypting everything—which for a large dataset is a project, and which therefore does not happen.

Key wrapping removes the coupling. Each data item, or each partition, is encrypted with a data key; the data key is encrypted with a key-encryption key and stored beside the ciphertext. Rotating the key-encryption key means re-wrapping the data keys, which is small and fast. The data itself is untouched.

This also makes cryptographic erasure practical: destroying the key-encryption key renders every data key, and therefore every ciphertext, unreadable, without touching the data store. And it makes per-tenant separation affordable, because a tenant-specific data key is cheap where a tenant-specific re-encryption is not.

The provision to make now is the storage format: a place beside each ciphertext for the wrapped data key and the key-encryption key identifier. Adding it later means rewriting the data, which is the situation it exists to avoid.

Agility without permanent weak options

There is a real tension here that deserves stating. A system that accepts many algorithms is flexible and is also a system that accepts weak algorithms, which is the mechanism behind a long line of downgrade attacks.

Agility means the accepted set can move, not that it is large. The operational discipline is to keep the set narrow, express it in configuration, add the new option before removing the old one, and remove the old one on a stated date rather than when convenient. A transition period with both options is necessary; a transition period without an end date is a permanent weakness.

The negotiation itself must also be protected. Where a protocol negotiates parameters, the handshake authentication must cover the negotiation, so an active attacker cannot force the weakest mutually supported option without detection. This is a property of the standard protocols and a common flaw in bespoke ones, which is one more reason to use the former.

Measuring whether you have it

Agility is easy to claim and straightforward to test. Pick a concrete change—replace the hash used for stored document digests, or move a signature scheme—and estimate it honestly:

• How many places in the code construct or verify that output?
• Can a reader tell, from the stored data alone, which scheme produced each item?
• Can the accepted set be changed by configuration, or does it require a release?
• How much data would need re-processing, and is there a mechanism to do it incrementally?
• Which counterparties would have to change, and is there a channel to ask them?
• How long would the overlap period be, and what ends it?

The estimate is the measurement. A change that takes a configuration rollout and a background job is agility. A change that takes a cross-team programme and a data migration is not, and no amount of algorithm choice will alter that. NIST’s transition guidance for post-quantum standards makes the point implicitly by setting dates: the organisations that meet them will be the ones for whom the answers above were already short.