Algorithm agility is an operational property.

1 min read

CRYPTOGRAPHIC TRANSITION

Why a configuration option is not a migration capability.

Cryptographic agility is often represented as a drop-down list of algorithms or a parameter passed to a library. If the system accepts both the old name and the new name, it appears ready for change.

That is only the smallest part of the problem.

A working transition has to change keys, certificates, messages, stored objects, devices, trust anchors and operational procedures while the system continues to serve participants that do not all update at once. It must avoid silent downgrade, preserve the ability to recover and eventually remove the algorithm it was designed to replace.

Agility is therefore not a property of an algorithm. It is a property of the complete system and of the organisation operating it.

Replacement is a distributed event

A cryptographic mechanism rarely exists in one location. It appears across a dependency graph:

protocol specifications and message schemas;
cryptographic libraries and platform APIs;
application policy;
certificate profiles and trust stores;
key-management services;
HSMs, SAMs, secure elements and smart cards;
firmware and embedded readers;
databases containing encrypted or signed objects;
provisioning and personalisation systems;
monitoring, audit and incident procedures;
external participants with independent release schedules.

Changing a primitive in the library does not update the rest of that graph.

The most difficult components are often not the central servers. They are devices in vehicles, gates, retail points or remote installations with long service lives, intermittent connectivity and controlled maintenance windows. A new algorithm may be available in software while remaining unavailable in a certified module or already-issued card.

The transition plan has to begin with where cryptography actually resides.

Inventory must describe purpose, not only names

An inventory that lists RSA, AES and ECC is not enough to plan a change.

For each use, it should identify:

the protocol and application purpose;
whether the operation provides confidentiality, integrity, authentication, key establishment or another property;
algorithm, mode, parameters and key size;
key owner, storage boundary and lifecycle;
encoding and algorithm identifier;
data or transaction lifetime;
implementation and hardware dependencies;
parties that create and consume the result;
update path and expected replacement date;
fallback and recovery behaviour.

The purpose is essential. Replacing an encryption algorithm affects the ability to read historical data. Replacing a signature algorithm affects validation, certificates and long-lived evidence. Replacing key establishment changes live sessions and often the handshake itself.

The same algorithm name can therefore represent several distinct migration problems.

Negotiation and policy are different

Protocol negotiation allows two parties to find a mutually supported option. Policy decides which options are acceptable.

Confusing the two creates downgrade risk. A peer can truthfully advertise an obsolete algorithm that local policy should reject. A message can contain an algorithm identifier that the cryptographic library knows how to process but that the application is no longer authorised to accept.

A sound implementation treats the received algorithm identifier as untrusted input. It maps that identifier against an explicit local policy that considers protocol version, role, key, date and purpose.

The permitted set should not be defined by whatever the installed library happens to support. Libraries preserve compatibility. Security policy deliberately removes it.

TLS 1.3 illustrates another important point: negotiation must itself be protected. It includes downgrade detection and authenticates the handshake transcript. Merely offering a stronger algorithm does not help if an intermediary can erase that offer without detection.

The transition needs more than two states

Real migrations rarely move directly from old to new. A useful lifecycle includes at least the following states.

Prepare

Locate dependencies, implement the new algorithm, establish identifiers and profiles, create test vectors and verify that operational components can carry the new sizes and formats.

Introduce

Deploy support without making it mandatory. Provision new keys and trust material. Exercise the path with controlled participants and record which components can complete it.

Prefer

Use the new mechanism by default while retaining a deliberate compatibility path. The system should make fallback visible and measurable.

Require

Reject the old mechanism for new operations once the relevant population has migrated. Exceptions should be narrow, time-bound and attributable.

Retire

Remove obsolete keys, certificates, code paths, configuration and monitoring rules. Retention needed for historical validation must be separated from permission to create new artifacts.

Recover

Maintain a tested response if the new mechanism, implementation or supply chain fails. Recovery does not necessarily mean returning to the previous algorithm. It may use an alternative implementation, parameter set or independently prepared mechanism.

These states are operational, not merely documentary. Each needs entry criteria, telemetry and an owner.

Coexistence creates the largest attack surface

During migration, the system often supports more combinations than it did before. Old and new certificates coexist. Messages can carry different identifiers. Some readers recognise the new format while others do not. Translation services may appear between generations.

This compatibility window is where assumptions multiply.

A verifier should know whether an old artifact was created before or after the migration boundary. A provisioning system should know which devices are capable of receiving new key material. A central service should distinguish a legitimate legacy path from an unexpected fallback.

Dual signatures and hybrid key establishment can help preserve security across assumptions, but their semantics must be defined. Does acceptance require both mechanisms or either one? What happens if one component ignores the unfamiliar value? Which result is recorded in audit evidence? Can an attacker strip one half without invalidating the other?

Combining algorithms is protocol design, not a substitute for it.

Stored data has a different clock

Live protocols can often change when both endpoints are updated. Stored objects remain tied to the algorithm and key that created them.

Encrypted records may need to be decrypted and re-encrypted, or their data-encryption keys may be rewrapped under a new key-encryption mechanism. Signed archives may need trusted timestamps, validation data or renewed evidence before an old algorithm is no longer considered reliable.

The required migration date depends on how long the protected information must remain secure or verifiable. A short-lived session and a document retained for decades should not share the same schedule simply because they use the same primitive today.

This is also why inventory should include cryptographic purpose and data lifetime. The urgency is attached to the exposure, not only to the name of the algorithm.

Hardware turns policy into logistics

Secure hardware can protect keys and constrain operations, but it also makes cryptographic change physical.

A software service may add an algorithm through a library update. A deployed SAM, smart card or secure element may require new firmware, a new applet, reprovisioning or replacement. Certification constraints may prevent arbitrary updates. Memory, command size and processing time may rule out an otherwise standard construction.

Questions for hardware-backed migration include:

Can the device store old and new key types simultaneously?
Can provisioning authenticate both generations?
Are algorithm identifiers exposed through the command interface?
Can larger public keys, signatures or ciphertexts be transported?
Is rollback prevented or merely discouraged?
Can failure be diagnosed without exporting secrets?
What is the field replacement plan for devices that cannot migrate?

The answer may require a bridge period in which the central architecture understands several device generations. That period should be designed, measured and ended, not allowed to become permanent by accident.

Observability makes fallback governable

A migration cannot be managed if the system records only success or failure.

Useful telemetry includes:

protocol and algorithm selected;
reason for fallback;
key or certificate generation, without exposing secret material;
device and software capability version;
verification failures by stage;
remaining use of deprecated paths;
objects that still require conversion;
exceptions and their expiry dates.

This information should be available before enforcement begins. Otherwise, requiring the new mechanism becomes an experiment performed on production traffic.

Observability also exposes false agility. If a supposedly optional legacy path carries most transactions months after the new default was introduced, the system has not migrated. It has added another configuration.

Test the transition, not only each algorithm

Primitive test vectors establish that individual implementations calculate correct results. Transition tests exercise combinations and timing.

They should include:

old producer with old consumer;
new producer with upgraded consumer;
old producer with upgraded consumer;
new producer with legacy consumer, where failure may be expected;
altered or unknown algorithm identifiers;
stripped negotiation options;
expired legacy exceptions;
rollback after new keys have been issued;
loss of one trust anchor during coexistence;
recovery using independently prepared material.

The expected result must be stated for every combination. "Backward compatible" is too broad to be a test condition.

Agility has an end condition

Systems often celebrate the point at which a new algorithm is supported. The security objective is reached later, when the vulnerable mechanism can no longer be selected for the operations being protected.

This requires decommissioning. Old private keys are destroyed or placed under restricted archival controls. Issuance stops. Verification rules distinguish historical evidence from current permission. Code paths and dependencies are removed. Exceptions close.

Without an end condition, agility becomes indefinite algorithm accumulation. Every retained mechanism expands the test matrix and the attack surface.

The ability to complete change

NIST defines cryptographic agility in terms of replacing and adapting algorithms across protocols, applications, software, hardware, firmware and infrastructure while preserving security and operations. The breadth of that definition is the point.

A system is not agile because it can name a second algorithm. It is agile when it can discover every dependency, introduce a replacement, operate safely during coexistence, detect downgrade, recover from failure and retire what is no longer acceptable.

The real capability is not choice. It is the ability to complete change.