Key Rotation Without Losing Access to Your Data
A practical guide to rotating encryption keys while preserving historical reads, safe migrations, and backup recovery, with envelope diagrams and a rollout test matrix.
An encryption rollout can pass every functional test and still fail months later, when someone retires the key that an old backup needs.
Key rotation is often presented as a schedule: create a key, switch over, repeat. The difficult part is preserving a usable relationship between the data, its key, and the people or services allowed to recover it.
This article uses a fictional document service to work through that problem. The examples are architecture notes, not production code or a claim about a particular customer deployment. They focus on symmetric data encryption; signing-key and certificate rotation have different verification and trust-distribution requirements.
Start with the Recovery Question
Imagine a service that stores encrypted reports. A report written in September must still open after an October key change. A restored September backup must also work in November.
Before choosing a rotation interval, write down what successful recovery means:
- Which historical records must remain readable?
- Which application versions might read them?
- Which backups, replicas, exports, and disaster-recovery environments retain copies?
- Who can authorize access to the required keys?
- What evidence is needed before a key can be retired?
These questions produce a dependency map. The map matters more than a dashboard showing that the latest rotation job succeeded.
For our fictional service, the acceptance criterion is straightforward: a current application instance can read both a newly created report and an older report restored into an isolated recovery environment. Neither test should require an operator to guess which key was used.
Two Keys, Different Responsibilities
Envelope encryption separates the key that encrypts the payload from the key that protects that key. The data encryption key, or DEK, encrypts the report. A key encryption key, or KEK, wraps the DEK. The stored envelope contains the encrypted payload and wrapped DEK, not an unprotected DEK.
A key-management service can hold the KEK while the application performs payload encryption. That is a common arrangement, not a requirement that every system must follow. See Google's envelope encryption documentation.
- Application receives an authorized report
- A DEK encrypts the report payload
- A KEK protects the DEK through a key service
- Storage retains ciphertext, wrapped DEK, and recovery metadata
- An authorized read unwraps the DEK and authenticates the payload
The diagram describes responsibilities, not a promise about where plaintext is allowed to exist. In this example, the application sees the plaintext and temporarily handles the DEK. A different design may keep more operations inside a cryptographic boundary.
An HSM does not remove the application's responsibility for access control, request validation, or memory handling. Check the actual provider interface, key attributes, and deployment policy before deciding which operations belong where.
Rotation, Rewrapping, and Re-encryption
These terms describe different changes:
| Change | What changes | What stays dependent on the old state |
|---|---|---|
| Select a new write key | Future writes use the new key or version | Historical envelopes may still need the previous key |
| Rewrap a DEK | The wrapping protection and its reference | The payload still uses the same DEK |
| Re-encrypt a payload | The payload ciphertext, usually with a new DEK | Older copies may still need their original keys |
| Retire a key | Its permitted use or availability | Any remaining dependent data may become unreadable |
Managed services do not all expose the same versioning model. For example, AWS KMS rotation can keep the logical key resource unchanged while retaining previous material for decryption. It does not automatically replace every DEK or re-encrypt every protected payload. Read the provider's rotation semantics, not just the feature name.
For our document service, the initial change is deliberately small: select a new KEK for future envelopes while preserving historical reads. Rewrapping existing DEKs is a separate, observable migration.
Do not call that migration a response to every possible compromise. If a DEK and ciphertext have already been copied, wrapping the same DEK differently cannot revoke the attacker's copy. Incident response needs to establish what was exposed and which data requires new protection.
Make Each Envelope Self-Describing
A reader should not apply today's write-key alias to every historical record. It needs a reliable way to identify the protection associated with that record.
OWASP discusses key identifiers and the need to plan for rotation in its Cryptographic Storage Cheat Sheet.
For the example service, a conceptual envelope contains:
- Format version
- The supported envelope schema, not the key's age.
- Key reference
- An immutable reference where required, or the provider's self-describing ciphertext metadata.
- Wrapped DEK
- The protected data key and any metadata required by the wrapping API.
- Payload protection
- Ciphertext, nonce or IV, authentication tag, and an explicit supported algorithm suite.
- Context
- Stable, non-secret information that binds the envelope to its intended use.
This is a field inventory, not a serialization specification. Use a maintained envelope format or library where available. A custom format needs a reviewed canonical encoding, algorithm allowlist, size limits, and authenticated metadata handling.
For AES-GCM, nonce uniqueness under a given key is a security requirement. Rotation is not a substitute for satisfying it. Use a vetted implementation and follow NIST SP 800-38D, including its invocation and IV requirements.
Additional authenticated data can bind a payload to a record identifier or purpose without encrypting that context. It must be reproduced correctly during decryption. Provider encryption context can also appear in audit logs, so it must not contain secrets; see the AWS KMS encryption-context documentation.
A useful design question follows: which fields must remain stable if the DEK is rewrapped? If mutable wrapping metadata is authenticated as payload AAD, changing that metadata can require recomputing payload protection. Separate stable payload context from wrapping metadata deliberately, while authenticating both according to the chosen format and provider API. Do not remove authentication just to make migration easier.
Roll Out Readers Before Writers
A safe ordering for the example service is:
- Inventory active data and recovery dependencies
- Deploy readers that accept both supported envelope versions
- Validate the new key, permissions, and recovery path
- Canary new writes with the new protection
- Expand writes while monitoring old and new reads
- Migrate historical envelopes where the policy requires it
- Review dependencies before disabling or destroying old keys
Start with readers because old application instances may remain alive during a rolling deployment. If a new writer creates envelopes that an old reader cannot understand, a healthy encryption operation can still break the product.
The canary should create a report through the normal application path, read it through another instance, and verify authorization behavior. A successful administrator command against the key service is insufficient evidence that the runtime identity and application path work.
For this example, release evidence includes the application revision, envelope format, configured write-key reference, and successful test record identifiers. It excludes plaintext, unwrapped keys, credentials, and sensitive request content.
A rollback also needs two separate decisions: whether to restore an older application release, and whether to change future write protection. Do not blindly point writers back to a key that is suspected of compromise.
Rewrap Without Overwriting a Newer Write
Suppose a background worker reads report revision 12 and starts rewrapping its DEK. Meanwhile, a user updates the report and creates revision 13. An unconditional worker update could overwrite the newer envelope.
For this service, the migration uses optimistic concurrency:
- Read the current envelope and its storage revision.
- Skip records already protected by the intended target.
- Ask the approved cryptographic interface to rewrap the DEK, or use an authorized unwrap-and-wrap workflow if that is the supported design.
- Validate the resulting envelope through the permitted read path.
- Commit only if the stored revision still matches the revision read.
- On a conflict, discard the stale result and inspect the latest record.
The worker should be restartable. Store a durable checkpoint, but also inspect each record's current state: a checkpoint alone cannot prove that an interrupted update committed.
Not every provider can rewrap inside its cryptographic boundary. If the chosen workflow exposes a DEK to application memory, that is a security property to document and review. It should not happen accidentally because a migration library selected a convenient fallback.
For the fictional rollout, I would cap concurrency separately from ordinary request traffic, measure key-service latency and throttling, and pause the worker when user-facing errors rise. Those are proposed operating controls, not universal threshold values.
When Payload Re-encryption Is Necessary
Rewrapping can change the KEK dependency without reading and rewriting the entire payload. It does not replace a compromised DEK, change the payload algorithm, or repair a flawed nonce strategy.
A payload migration needs its own plan: read through the authorized path, generate the required fresh key material and nonce, encrypt under the target format, validate the result, and commit safely. Treat plaintext handling during that process as part of the threat model.
Google's re-encryption guidance illustrates the distinction between changing a key's primary version and migrating data already encrypted under older versions. Service integrations may automate some work; verify which objects and copies they actually cover.
In our example, a migration report separates three counts: envelopes inspected, envelopes updated, and envelopes verified. A batch being marked complete should not silently mean that unreadable records were skipped.
Backups Decide When Retirement Is Finished
A live database may contain no references to an old key while last month's backup still depends on it.
Key lifecycle planning must include recovery and eventual destruction, as described in the OWASP Key Management Cheat Sheet. The operational consequence is important: data retention and key retention cannot be designed independently.
For the report service, the retirement review would include:
- An inventory of retained backups, snapshots, replicas, and exported encrypted records.
- A recovery test using an older retained copy, not only a freshly created backup.
- Confirmation that the recovery environment can reach the approved key service with the correct identity.
- Evidence that any migration covered the copies it claims to cover.
- Approval from the owners of data retention, security, and service availability.
Disabling a key can be reversible in some systems; destroying its material may not be. A quiet monitoring window is useful evidence, but it cannot prove that an offline archive has no dependency. Do not test retirement by casually disabling a production key and waiting for complaints.
A Test Matrix for the Change
A rotation test should exercise failure paths as well as successful encryption.
| Scenario | Expected outcome for the example service |
|---|---|
| Read a historical report after the write-key change | The envelope selects the correct historical protection |
| Read a new report from another application instance | Readers understand the new format and have appropriate permission |
| Submit a modified ciphertext or context | Authentication fails; no partial plaintext is returned |
| Restart a migration worker after a committed update | Reprocessing does not damage an already migrated record |
| Update a report while migration is running | A stale worker cannot overwrite the newer revision |
| Make the key service unavailable | The application fails within its timeout policy; it does not store plaintext as a fallback |
| Restore an older backup in an isolated environment | Recovery uses the retained protection and approved identity |
| Attempt access with an unauthorized tenant identity | Application and key-service controls reject the request |
The last case is worth testing explicitly. Successfully decrypting a record proves a cryptographic operation worked; it does not prove that the caller was entitled to that record.
What Completion Actually Means
For this example, I would not close a rotation change solely because the new key is active.
I would close it when new writes use the intended protection, supported readers handle historical data, required migrations have verifiable results, recovery has been exercised, and the disposition of old keys is documented. If a retained archive still needs an old key, that dependency remains an operational responsibility.
The practical lesson is simple: key rotation is a change to a running system and its recovery history. Treat the data format, deployment order, migration process, and retirement decision as parts of the same engineering task.