Key Rotation, Key Versions, and Why Re-Encryption Is Optional

Rotation exists to bound two quantities: the amount of data exposed by one compromised key, and the amount of ciphertext an attacker can collect under one key for cryptanalysis. A rotation policy is a statement about acceptable loss. The engineering question is how to perform the rotation without a rewrite that the storage system cannot afford, and the answer depends on which key in the hierarchy is being rotated.

Three rotations that look alike

A master key wraps data keys. Rotating it means producing a new master key and re-wrapping every stored data key under it: one wrap operation per object, on the order of 40 bytes of output per object. The payload ciphertext does not change, and nothing needs to be decrypted and re-encrypted. For a store of a billion objects this is a rewrite of tens of gigabytes of key blobs rather than of the payload, which is a job that can run incrementally in the background while reads continue.

A data key encrypts a payload. Rotating it requires decrypting under the old key and re-encrypting under the new one, because the ciphertext is bound to the key. There is no shortcut: the payload must be read and written. This is the expensive rotation, and it is why data keys are generated per object rather than shared widely — a per-object data key can be rotated by rewriting that object alone, and the operation is naturally parallel.

A password-derived key cannot be rotated without the password. Changing it means re-deriving from a new password and re-encrypting whatever it protects. Systems that store data under a password-derived key usually wrap a random data key under the password-derived key, so a password change re-wraps 40 bytes instead of the payload, the same structure as the master-key case.

Confusing these three is the source of most bad rotation designs. A policy that says “rotate annually” without naming the key produces either an enormous rewrite or a no-op depending on which key the implementer picks.

Versioning is what makes rotation non-atomic

A rotation that must complete atomically across a large store is a rotation that will not complete. The alternative is to let old and new keys coexist, with each ciphertext recording which key version produced it.

The record carries a key identifier or version number, typically a small integer or a short string. Decryption looks up the version, fetches the corresponding key, and proceeds. Encryption always uses the current version. A background process then rewrites records that reference older versions, and when none remain, the old key is retired. At no point is the system in a state where some data is unreadable, and no coordinated cutover is required.

The version identifier must be authenticated along with the ciphertext. If it sits in an unauthenticated header, an attacker can change it to point at a different key version, and the decryption either fails or, worse, succeeds against a key the attacker has some control over. Including the version in the associated data of an AEAD binds it: AES-GCM, specified in SP 800-38D, authenticates associated data without encrypting it, so a version number in the clear is safe as long as it is fed into the authentication tag computation. In a non-AEAD construction, the version must be covered by a separate MAC.

The number of live versions is a bounded resource. Each version needs its key available for decryption, which means the key store holds more material, and an attacker who compromises the store gets all live versions at once. A rotation policy that keeps every historical version indefinitely converts rotation into a record-keeping exercise with no security benefit. The standard practice is to keep the current version and one predecessor, retire the rest once no ciphertext references them, and treat the retirement as a deletion that must be verified.

Re-wrapping without touching payloads

For the master-key case, the operation is mechanical. Each stored record contains a wrapped data key. Re-wrapping reads the wrapped blob, unwraps it under the old master key, wraps it under the new one, and writes the result with the new version identifier.

def rewap(record, old_mk, new_mk, new_version):
    # Unwrap under the retiring master key, then wrap under the new one.
    dek = aes_key_unwrap(old_mk, record.wrapped_dek)
    blob = aes_key_wrap(new_mk, dek)
    # The version must travel with the blob so decryption can select a key.
    return replace(record, wrapped_dek=blob, key_version=new_version)

Two properties matter. First, the data key itself is unchanged, so any ciphertext encrypted under it remains valid, and any process currently holding the unwrapped data key is unaffected. Second, the operation is idempotent if the record’s version is checked first: a record already at the new version is skipped, so an interrupted pass can be resumed without special handling.

The pass is a full scan of the metadata, not of the data. On a store with a large ratio of payload to metadata that is a small fraction of the total bytes, and the pass can be throttled to avoid competing with foreground reads. The cost is dominated by random access to the key blobs, so a store that keeps them in a separate index does the pass far faster than one that must seek through payload extents to find them.

There is a window in which both master keys must be available: the old one to unwrap records not yet migrated, the new one for freshly written records. That window is the rotation’s real risk. During it, the key store holds two master keys, and a compromise yields both. Keeping the window short, and refusing to start a new rotation while one is open, bounds the exposure.

Re-encryption and its actual cost

When the payload must be rewritten — a data key rotation, a change of algorithm, a move to a stronger cipher — the cost is the full payload size, and the constraints change. The job must read every object, decrypt, encrypt, and write, and it must do so without a moment where the object exists only in the new form with no fallback.

The standard technique is to write the new ciphertext alongside the old, then switch the record’s pointer atomically, then delete the old. That doubles the storage requirement for the objects in flight, which for a whole-store migration is a capacity problem rather than a cryptographic one. Doing it in batches keeps the overhead bounded at the batch size.

A cheaper variant rewrites only what the policy requires. If the concern is that a key has been exposed for a long time, the objects written under it after the exposure began are the ones that matter most; rewriting them first reduces the exposure window faster than a uniform scan. If the concern is algorithmic — moving from a mode with a 96-bit nonce and a 2^32 block limit to one with a larger budget — then every object must move, and the ordering is a scheduling question.

Nonce budgets make rotation mandatory rather than optional in some designs. AES-GCM with random 96-bit nonces has a collision probability that becomes non-negligible as the number of messages under one key grows; the birthday bound over 2^96 gives a collision risk that rises with the square of the message count. Deterministic construction — a counter per key — removes the randomness but caps the message count at the counter space. Either way, the key has a maximum message count, and reaching it requires a new key. That is a rotation driven by a hard limit rather than by policy, and it must be tracked as a counter per key rather than estimated.

What rotation does not fix

Rotation does not recover data that was already exposed. If a key was compromised and used to decrypt a payload, rotating the key does not un-decrypt it. The only remedy is to treat the exposed data as disclosed and to rotate so that future data is not exposed by the same key. A rotation performed after a compromise is a containment measure, not a repair.

Rotation does not help if the new key is generated the same way as the old one. A key derived from the same weak passphrase, or generated from the same seeded generator, is not a new key in any meaningful sense. The entropy path determines whether a rotation actually changes the secret.

Rotation does not remove old ciphertext from backups. A backup taken before the rotation contains the old key’s ciphertext, and if the old key is retained for decryption of live records, the backup remains readable. Retiring a key is only meaningful once every copy of the data it protected has also been retired, which is the reasoning behind cryptographic erasure.

Finally, rotation adds an operational failure mode: a version that no longer has a key. This happens when the retirement step runs before the last reference is migrated, when a restore from backup reintroduces records at a retired version, or when a key store loses a version to a partial restore. The defence is to make retirement a two-phase operation — mark the version as retiring, verify zero references across the live store and the backups that will be restored, then delete — and to keep the version-to-key mapping durable in a way that survives the same failures as the data.

Choosing an interval

NIST SP 800-57 frames the choice in terms of cryptoperiods: the time during which a key is authorized for use. The length is set by the amount of data protected, the sensitivity of that data, the strength of the algorithm, and the cost of compromise. There is no universal number, and a policy that names one without stating its assumptions is arbitrary.

The practical approach is to derive the interval from a bound on data volume. If a key protects at most N records and the acceptable exposure is M records, the key must be replaced every M records, and the interval is a consequence of write rate rather than of calendar time. Volume-based rotation also handles the case of a store that is written heavily for a week and then idle for a year, where a calendar policy would rotate an idle key for no benefit and leave a busy one in place too long.

Whatever the trigger, the mechanism is the same: version the records, keep the predecessor available, re-wrap or re-encrypt incrementally, and retire only after verifying that nothing references the old version. The key service API is where those steps become callable operations, and the constraints on who may call them determine whether the rotation can be performed safely at all.