Crypto Agility: Make algorithms change safely

Introduction

An algorithm that is secure today may not remain secure in ten years.

Computing power increases, cryptanalysis advances, implementation vulnerabilities emerge, and compliance requirements change. Some changes do not even involve the algorithm itself being broken: keys may be leaked, libraries may become unmaintained, or protocol versions may be retired.

Ciphertext in databases, tokens issued to customers, public keys embedded in device firmware, and protocols used between services may all remain in use for years. We also need to consider:

  • How do we respond when an algorithm becomes increasingly insecure?
  • How do we smoothly replace it with a more secure algorithm?
  • How do we support both old and new algorithms?

Crypto Agility (cryptographic agility) is the ability to answer these questions in advance: a system can replace algorithms, parameters, keys, or protocols in a controlled, observable, and recoverable way without requiring a major product overhaul.

Why Cryptographic Agility Matters

The Security of an Algorithm Depends on Assumptions

Cryptographic security is not a permanent property. It is an assessment based on a particular attack model, available computing resources, and known research. When any of these factors change, previously reasonable choices may need to be reassessed:

  • New attack methods: Researchers discover collisions, downgrade attacks, or more efficient ways to break cryptographic schemes
  • Hardware advances: GPUs, ASICs, and cloud clusters rapidly reduce the cost of brute-force attacks
  • Implementation and supply chain risks: Libraries have vulnerabilities, vendors end support, and hardware modules are retired
  • Policy and compliance: Browsers, operating systems, or government standards stop accepting older TLS versions, hash functions, or key lengths
  • Changes in the threat model: For example, attackers collect encrypted traffic today and decrypt it once they gain access to a quantum computer

Cryptographic Migration Costs Increase over Time

Hard-coding an algorithm or a key may seem quick and convenient, but as an application evolves, it can become an unwieldy mess… The hard-coded algorithm spreads across caches, backups, services, and partner integrations.

Cryptographic migration costs increase over time, so the core value of cryptographic agility is not making transitions cost-free, but making costs predictable: knowing which data is affected, which versions are still in use, what to deploy first, and when old keys can be removed.

A Historical Example: DES

DES is a concrete example. It became a U.S. federal standard in 1977. In 1998, the EFF used purpose-built hardware called Deep Crack to recover a DES key in roughly 56 hours, demonstrating that 56-bit keys were no longer sufficient against well-resourced attackers. NIST did not formally withdraw the DES standard until 2005.

1977FIPS 46 ispublished,establishing DES asa standard1998EFF Deep Crackrecovers a DES keyin roughly 56 hours2001AES becomes thenew federalencryption standard2005NIST withdrawsDES; no longerapproved forprotecting federaldataDES: The Upgrade Window from Adoption to Retirement

Two intervals in this timeline deserve attention: roughly 21 years after DES was adopted, hardware costs finally made its 56-bit keys insufficiently secure; another seven years passed between the public warning in 1998 and its formal retirement in 2005. This was not a grace period for doing nothing, but a window in which systems needed to complete their upgrades.

The question, then, is not just “Is our current algorithm strong enough?” but also “How quickly can we stop using it once it is no longer strong enough?” Today’s algorithms will go through the same lifecycle. Cryptographic agility means preparing in advance for this inevitable upgrade window.

Facing Future Quantum Threats: Symmetric Encryption, Asymmetric Encryption, and Hashing Face Different Problems

Asymmetric Encryption: A Structural Threat

RSA, for example, relies on the difficulty of factoring large integers, while Diffie–Hellman and elliptic curve cryptography (ECC) rely on the difficulty of the discrete logarithm problem. Quantum computers, however, can use Shor’s algorithm to solve both types of problems dramatically faster. Once quantum computing reaches a practical scale, these traditional systems will need to be replaced.

Symmetric Encryption: Reduced Security Strength, Not Immediate Failure

Symmetric encryption typically protects large volumes of data directly, such as database fields, files, and transmitted content. Grover’s algorithm can theoretically reduce the work required for brute-force search from roughly 2^n to roughly 2^(n/2). Using AES as an example, a rough interpretation is that AES-128’s 128-bit security strength against brute-force attacks could fall to around 64 bits, while AES-256 would retain roughly 128-bit security.

Hashing: Not Encryption, but Its Security Strength Also Decreases

Hash functions do not provide confidentiality; they map inputs of arbitrary length to fixed-length digests. Mechanisms such as digital signatures, file integrity checks, HMAC, and key derivation rely on different properties of these functions:

  • Preimage resistance: Given a digest, it is difficult to find an input that produces it
  • Second-preimage resistance: Given an input, it is difficult to find a different input with the same digest
  • Collision resistance: It is difficult to find any two distinct inputs with the same digest

The same hash algorithm can serve different purposes, each relying on different properties, facing different attacks, and requiring different defenses. Consider SHA-256:

Use caseProperty relied onWhat the attacker must doClassical security strengthUnder quantum attacksThe actual defense
Digital signaturesCollision resistanceCreate two documents with the same digest, trick you into signing the harmless one, then substitute the malicious oneRoughly 128-bit (birthday attack, n/2)Theoretically roughly 85-bit (BHT, n/3), with practical speedups difficult to achieveLonger digests: SHA-384 / SHA-512
Integrity verification (download checksums)Second-preimage resistanceFind another input matching a fixed digest they did not chooseRoughly 256-bitRoughly 128-bitObtain the digest itself through a trusted channel; otherwise, the attacker can replace both the file and its digest
HMACKey secrecy and PRF properties, not collision resistanceGuess the keyThe smaller of the key length and output lengthKey strength roughly halvedSufficiently long random keys
Password storageNone of the above properties is the main concernPerform offline dictionary attacks against low-entropy passwordsAlmost unrelated to digest lengthSame as at leftSlow, salted, memory-hard algorithms: Argon2id, scrypt, bcrypt
KDF (such as HKDF)Randomness extraction / PRFAttack the input keying materialLimited by the entropy of the input keyRoughly halvedHigh-entropy input keys

A real-world example: SHAttered demonstrated a practical SHA-1 collision in 2017, making SHA-1 unsuitable for signatures. HMAC-SHA1, however, does not rely on collision resistance and was not broken by this result (although phasing it out is still recommended). The same applies to MD5.

As with AES, this does not mean SHA-256 is already insecure. The point is that an inventory cannot merely record “uses SHA-256”; it must record “algorithm × use case.” Signatures rely most heavily on collision resistance and should be prioritized for upgrades. For password storage, the solution is not a longer hash, but switching to Argon2id and versioning its cost parameters as well.

Harvest now, decrypt later

Some data must remain confidential beyond the lifetime of the system that handles it, such as medical records, government documents, and trade secrets. Attackers can capture traffic or ciphertext protected by traditional asymmetric cryptography today and attempt to decrypt it in the future. This “harvest now, decrypt later” risk means migration to post-quantum cryptography (PQC) cannot wait until quantum computers arrive.

Putting Cryptographic Agility into Practice

Design a one-way system that cannot revert, allowing only gradual replacement with newer algorithms
  1. Identification: Identify the version, algorithm, and key identifier (Key ID / kid) from data, tokens, certificates, or protocol handshakes
  2. Selection: Use a centralized, explicit policy to determine which scheme new data uses, rather than allowing callers to choose arbitrary algorithms
  3. Coexistence: Decrypt or verify supported older versions for as long as necessary, while producing only the new version
  4. Rotation and retirement: Add new keys or versions, monitor usage, and remove old schemes after the cutoff
  5. Observability and testability: Know how much old data remains in production, whether migrations have failed, and whether different implementations actually interoperate

Example: Implementing an Encryption and Decryption Interface

1. Define Ciphertext Metadata and Its Interface

// 1. The ciphertext format should include its version and the KeyID used
type Envelope struct {
Version string `json:"v"` // For example, v2
KeyID string `json:"kid"` // For example, customer-2026-01. The key ID itself is not secret; it makes it easier to store actual keys securely elsewhere and rotate them
Payload string `json:"ciphertext"`
}
// 2. Abstract encryption and decryption into two methods
type Cipher interface {
Encrypt(plaintext, aad []byte) (Envelope, error)
Decrypt(envelope Envelope, aad []byte) ([]byte, error)
}

Given just this ciphertext envelope, the decrypting side knows which rules and which key to use. The actual format could be JSON, binary fields, or a prefixed string.

2. Always Use the Current Version for New Writes; Keep Older Versions Read-Only

v2

v1

New writes

Current policy configuration

v2 + new key

Read ciphertext

Version and kid

New decrypter

Legacy decrypter: read-only

Plaintext

The earlier Cipher interface requires both Encrypt and Decrypt, forcing every version to implement the full Cipher interface. That means each must provide an Encrypt method, leaving a path for writing the old format. Anyone developing a new feature could accidentally call it. An improved structure looks like this:

type Decrypter interface {
Decrypt(envelope Envelope, aad []byte) ([]byte, error)
}
type Encrypter interface {
Encrypt(plaintext, aad []byte) (Envelope, error)
}
// Only the current version needs both encryption and decryption.
type CurrentCipher interface {
Encrypter
Decrypter
}
// v1 implements only Decrypter; Encrypt is deliberately absent.
type LegacyV1 struct{}
// v2 is the current version, so it implements CurrentCipher.
type AESGCMV2 struct{}

The concrete implementations are omitted. The key point is that LegacyV1 satisfies only Decrypter, while AESGCMV2 satisfies both Encrypter and Decrypter.

  • Interfaces
    • Decrypter: Decryption only.
    • Encrypter: Encryption only.
    • CurrentCipher: Combines both, for use only by the current version.
  • Implementations
    • LegacyV1 satisfies only Decrypter, deliberately omitting Encrypt.
    • AESGCMV2 satisfies both Encrypter and Decrypter.

Make “legacy versions are read-only” part of the code structure, not merely a convention. For example, the legacy module exposes only Decrypt and simply cannot Encrypt. Even if someone tries to reuse the old scheme in a new feature, the compiler will stop them.

In practice, retrieve keys from an external source at application startup, then create the current v2 encrypter and the v1 decrypter still supported for reads:

type CipherRef struct {
Version string
KeyID string
}
type CryptoService struct {
writer Encrypter
decrypters map[CipherRef]Decrypter
}
currentV2 := AESGCMV2{ /* keyID: customer-2026-01, key: ... */ }
legacyV1 := LegacyV1{ /* keyID: customer-2019, key: ... */ }
crypto := CryptoService{
writer: currentV2,
decrypters: map[CipherRef]Decrypter{
{Version: "v2", KeyID: "customer-2026-01"}: currentV2,
{Version: "v1", KeyID: "customer-2019"}: legacyV1,
},
}
Implementation Details: Lookup During Decryption
func (c CryptoService) Decrypt(env Envelope, aad []byte) ([]byte, error) {
ref := CipherRef{Version: env.Version, KeyID: env.KeyID}
d, ok := c.decrypters[ref]
if !ok {
return nil, errors.New("unsupported version or key id")
}
return d.Decrypt(env, aad)
}

In the following example, after the user enters a tax ID, the application constructs AAD from the immutable record identity and calls only the service’s encryption entry point:

plaintext := []byte("A123456789")
aad := []byte("tenant/acme:customers:42:tax-id")
encrypted, err := crypto.Encrypt(plaintext, aad)
// encrypted looks roughly like:
// {"v":"v2", "kid":"customer-2026-01", "ciphertext":"Base64..."}
db.SaveCustomerTaxID(42, encrypted)

When reading, the service uses the stored Version and KeyID to find the appropriate decrypter, then decrypts with the same AAD:

stored := db.LoadCustomerTaxID(42)
plaintext, err := crypto.Decrypt(
stored,
[]byte("tenant/acme:customers:42:tax-id"),
)
// plaintext == []byte("A123456789")

If this is a legacy record, stored will contain v1 and customer-2019, and the read path will route it to LegacyV1.Decrypt(...).

Further Reading