Envelope Encryption and Key Management: KMS, HSM, Key Rotation and Crypto-Shredding Architecture (2026)

Most teams believe their data is “encrypted at rest” the moment they tick a box on a bucket or a database. What that checkbox actually buys is a question about where the keys live, who can ask for them, how often they change, and what happens to the ciphertext when someone must be forgotten. The cipher itself, usually AES-256, is the easy and solved part. The hard part is the key management architecture wrapped around it, and the pattern that makes that architecture tractable at scale is envelope encryption.

Envelope encryption encrypts your data with a data key, then encrypts that data key with a second, centrally guarded key. It lets you protect petabytes with a key service that can only handle a few thousand requests per second, lets you rotate a master key without touching a byte of data, and lets you delete one small key to render an entire tenant’s data permanently unreadable. It also introduces new failure modes: a key service outage becomes a data outage, a careless cache becomes a key-reuse bug, and a nonce collision silently destroys confidentiality.

What this covers: the DEK and KEK hierarchy, AES-GCM nonce rules and the 2^32 random-nonce bound, how AWS KMS, Google Cloud KMS, Azure Key Vault and HashiCorp Vault Transit implement the pattern, what FIPS 140-3 HSM levels mean, BYOK and external key stores, three kinds of key rotation, crypto-shredding for erasure, encryption context, quotas and throttling, multi-region replication, failure modes, and a runnable Python example.

Context and Background

Symmetric encryption is cheap and fast but has one awkward property: whoever holds the key can decrypt everything encrypted under it. Early storage encryption designs used a single volume key, held in a configuration file or an environment variable beside the data. That makes the key exactly as safe as the least protected machine that reads it, and it makes rotation a bulk re-encryption project nobody schedules.

Hardware security modules (HSMs) changed the economics of protecting a root of trust. An HSM is a tamper-resistant device that generates keys internally, performs cryptographic operations inside its boundary, and refuses to export the key in the clear. But an HSM is a scarce, comparatively slow resource. You cannot stream a terabyte of database pages through it, and you cannot give each of ten thousand microservice instances its own physical device. The compromise that the whole industry converged on is to keep a small number of high-value keys inside the HSM or a managed key management service (KMS), and let those keys protect many short-lived, cheap-to-generate data keys that do the bulk work outside it.

All three hyperscalers document this pattern in nearly identical terms. Google Cloud’s guidance describes envelope encryption as encrypting a key with another key: data is encrypted with a data encryption key (DEK), and the DEK is encrypted by a key encryption key (KEK) managed in Cloud KMS. It recommends generating DEKs locally, creating a new DEK for each write, storing the wrapped DEK next to the data it protects, and never storing a plaintext DEK. AWS KMS exposes the same pattern through GenerateDataKey, which returns a plaintext data key and a copy encrypted under a KMS key, and AWS publishes that KMS keys sit inside hardware security modules validated under FIPS 140-3 Security Level 3. Azure Key Vault and Managed HSM, and HashiCorp Vault’s Transit engine, provide wrap and unwrap or encrypt and decrypt primitives that serve the same role.

If you are building a platform, the key layer interacts with everything else. Workload identity decides who may call the key service; our piece on SPIFFE and SPIRE workload identity covers how services prove who they are without static credentials. Secrets that are not bulk data, such as API tokens and database passwords, follow a related but distinct path described in Kubernetes secrets management with the External Secrets Operator. And the long-term cryptographic horizon matters: wrapped keys outlive the algorithms that wrapped them, which is why post-quantum cryptography for OT and IIoT belongs in any key-lifecycle plan.

This article is a reference architecture. It assumes you know what AES is and focuses on the decisions around it: where the hierarchy has levels, which operations cross the network, and what breaks.

The Envelope Encryption Reference Architecture

Envelope encryption is a two-level (often three-level) key hierarchy: a data encryption key encrypts the payload locally, a key encryption key held in a KMS or HSM encrypts the data encryption key, and the wrapped key is stored beside the ciphertext. Only the KEK needs to be centrally protected, rotated and audited, while DEKs are cheap, numerous and disposable.

Figure 1: Envelope encryption hierarchy. A root key in an HSM protects tenant KEKs in the KMS, each KEK wraps many data keys, and each data key encrypts one object locally.

Figure 1 shows the shape. At the bottom, objects are encrypted with AES-GCM using DEKs generated by the application or returned by the KMS. In the middle, a KEK (for AWS, a KMS key; for Google, a CryptoKey; for Vault, a named transit key) wraps those DEKs. At the top, an HSM-resident root or backing key protects the KEKs themselves. In a managed service the top level is invisible to you: AWS states that KMS keys never leave the service unencrypted, and the backing HSMs are the compliance boundary.

The long-description version: a write path asks the KMS for a fresh data key, receives it in plaintext and wrapped form, encrypts the data locally, discards the plaintext, and stores the wrapped key with the ciphertext. A read path fetches the wrapped key, asks the KMS to unwrap it, decrypts locally, and discards the plaintext. The KMS sees only small key blobs, never your data.

Why two levels instead of one

The obvious alternative is to encrypt everything directly with the KMS. That fails for three reasons. First, size limits: AWS KMS Encrypt accepts only a few kilobytes of plaintext (documented as 4 KB; verify against the current API reference), and Google Cloud KMS documents a 64 KiB maximum for Encrypt and Decrypt input. Second, throughput: every byte would cross the network to a shared service. Third, blast radius: a single compromised credential with Decrypt rights would pull plaintext for every object, whereas an envelope scheme limits the exposure to the keys that credential can unwrap.

Latency matters as much as limits. A local AES-GCM operation on a modern CPU with AES instructions runs at gigabytes per second per core, while a KMS call is a network round trip, typically single-digit to tens of milliseconds depending on region and load (illustrative; measure your own). Envelope encryption makes the slow, remote operation proportional to the number of keys, not the number of bytes.

The DEK lifecycle: generate, use, wrap, discard

A DEK has a short and precise life. It is generated from a cryptographically secure random source, either by the KMS (GenerateDataKey returns it wrapped and plaintext in one call, so the plaintext never needs to be generated by your code) or locally followed by a Encrypt or wrap call. It is held in memory only as long as encryption requires. Then the plaintext is zeroised and only the wrapped form persists.

The wrapped DEK is metadata, and it must travel with the ciphertext. Common storage choices are a header in the object, a column next to the encrypted column, or a separate key-store table keyed by object ID. Co-locating it is operationally simpler and keeps the two from drifting apart; a separate table makes bulk re-wrapping easier because you can scan keys without reading data. Whatever you choose, record the KEK identifier and version used to wrap, the algorithm, and the encryption context (covered below), because a decrypt six years from now needs all of them.

Granularity: per object, per tenant, per table

How many DEKs do you create? Google’s guidance leans toward a new DEK per write, which removes the need to ever rotate DEKs. The cost is key-service traffic and wrapped-key storage overhead (a wrapped AES-256 key is on the order of a hundred bytes). The other extreme, one DEK per database or per bucket, minimises overhead but concentrates risk and makes the AES-GCM invocation limit a live concern.

Per-tenant DEKs, wrapped by per-tenant KEKs, are the architecture that makes SaaS crypto-shredding possible. Consider a multi-tenant analytics platform with 2,000 tenants. If each tenant has one KEK and objects are encrypted with fresh DEKs, deleting a tenant’s KEK makes all of that tenant’s objects unrecoverable regardless of how many backups exist, while other tenants are unaffected. If all tenants share one KEK, erasure of a single tenant requires re-encrypting everyone else’s data or accepting that you cannot truly delete. We return to this later.

Data key caching and its security trade-off

Generating a DEK per object at high request rates can exceed KMS quotas, so teams cache data keys and reuse them for many objects over a short window. The AWS Encryption SDK documents this feature explicitly: by default it generates a new data key for each encryption, which follows the practice of discouraging excessive key reuse, and caching is optional and should be used cautiously and only when required to meet performance goals. You set thresholds (maximum age, maximum messages, maximum bytes) so a cached key is retired before it has encrypted too much. The SDK also now points to the AWS KMS Hierarchical keyring as an alternative caching approach in newer SDK versions, with the caveat that content encrypted with that keyring can only be decrypted with it.

Reuse has a cryptographic cost: every message encrypted under the same DEK consumes from that key’s nonce budget, and a compromised DEK exposes everything it encrypted. Treat the cache as a budget with three limits, not a convenience. We quantify the nonce limit next.

AES-GCM Nonce Rules and Why They Shape the Design

AES-GCM is the dominant authenticated encryption mode for envelope encryption because it is fast, hardware-accelerated and standardised in NIST SP 800-38D. It has one non-negotiable rule: never encrypt two different messages under the same key with the same nonce (NIST calls it the initialization vector, IV). Violating it leaks the XOR of the two plaintexts and, worse, lets an attacker recover the authentication subkey and forge messages. This is catastrophic, silent, and cannot be detected from the ciphertext.

The 96-bit random IV and the 2^32 bound

SP 800-38D permits two ways to build an IV. The deterministic construction combines a fixed field (identifying the device or context) with a counter, so uniqueness is guaranteed by design as long as the counter never repeats. The random construction draws the IV from a random bit generator. The standard recommends a 96-bit IV for efficiency, and when IVs are random it limits the number of invocations of authenticated encryption under a given key to 2^32. A NIST workshop paper on practical challenges with AES-GCM summarises the consequence: NIST limits the number of messages that can be encrypted with a single key to 2^32 for random 96-bit IVs, which keeps the probability of a repeated key and IV pair below 2^-32.

The arithmetic is a birthday bound. With a 96-bit space and n random draws, the chance of at least one collision is roughly n^2 divided by 2^97. At n = 2^32 that is about 2^64 / 2^97, which is 2^-33. In round terms, after four billion messages you have a collision probability around one in eight billion, which is why NIST draws the line there. Past that, the risk climbs quadratically: at 2^40 messages the same approximation gives about 2^-17, roughly one in 130,000, far beyond what any security engineer accepts for a break that reveals plaintext.

Worked example (illustrative workload): a service encrypts 5,000 records per second under one long-lived DEK with random IVs. That is about 4.3 x 10^8 messages per day, so the 2^32 limit (about 4.29 x 10^9) is reached in roughly ten days. A “never rotate the DEK” policy would silently blow through the bound within two weeks. HashiCorp’s Transit documentation makes the same point for its AES-GCM keys: rotate before roughly 2^32 encryptions per key version, with the example that at about 40 million operations a day, rotating every three months stays within the limit.

Practical consequences

Three design rules fall out of the nonce limit. First, prefer a fresh DEK per object or per small batch, which keeps each key’s invocation count tiny and makes the bound irrelevant. Second, if you must reuse a DEK (caching, streaming), count invocations and rotate the key at a safe fraction of 2^32, for example a small multiple below it, not at it. Third, use a deterministic or counter-based IV only if you can guarantee uniqueness across restarts, replicas and failover, which is hard in distributed systems; a counter that resets after a crash is the classic nonce-reuse bug.

Larger nonce constructions help. AES-GCM-SIV and XChaCha20-Poly1305 are designed to tolerate random nonces or misuse, trading speed or ecosystem support. These are worth knowing but note that managed KMS interfaces and FIPS-validated modules mostly expose AES-GCM, and FIPS 140-3 mode on Vault, for example, excludes ChaCha20-Poly1305 from certified use.

There are other GCM limits. The tag length affects forgery probability: the forgery probability grows with the number of blocks of associated data and ciphertext relative to 2^t for tag length t, so truncated tags (32 or 64 bits) are a liability, and 128-bit tags are the sane default. SP 800-38D also caps a single message’s plaintext length at a bit under 2^36 bytes (about 64 GiB), so very large objects must be chunked, with a per-chunk nonce and ideally a chunk index authenticated as AAD to prevent reordering and truncation. That is precisely what streaming formats like the AWS Encryption SDK message format do (verify exact framing details in the SDK specification).

Additional authenticated data

GCM authenticates but does not encrypt additional authenticated data (AAD). It is the correct mechanism for binding ciphertext to its context: tenant ID, record ID, table name, schema version. If an attacker with storage write access swaps tenant A’s wrapped ciphertext into tenant B’s row, a scheme that authenticates the tenant ID as AAD fails closed. Without AAD, the swap decrypts cleanly and you have a cross-tenant data leak with no cryptographic alarm. AAD is the data-layer sibling of the KMS-layer encryption context discussed below.

Inside the Key Services: AWS KMS, Cloud KMS, Key Vault and Vault Transit

The pattern is common but the services differ in quotas, rotation semantics and trust boundaries. Differences that look minor on a feature matrix become the dominant design constraints at scale.

AWS KMS

AWS KMS organises around KMS keys. A symmetric KMS key never leaves the service in plaintext; callers use GenerateDataKey, Encrypt, Decrypt and ReEncrypt against it. The overview documentation states the keys are protected by FIPS 140-3 Security Level 3 validated hardware security modules.

Quotas are where architecture meets arithmetic. The documented shared quota for symmetric cryptographic operations is calculated per account, per Region, per one-second interval, and covers Decrypt, Encrypt, GenerateDataKey, GenerateDataKeyWithoutPlaintext, GenerateMac, GenerateRandom, ReEncrypt and VerifyMac together. The quota is 100,000 requests per second in us-east-1, us-west-2 and eu-west-1, 20,000 in a list of regions including us-east-2, ap-southeast-1, ap-southeast-2, ap-northeast-1, eu-central-1, eu-west-2 and eu-south-2, and 10,000 elsewhere. RSA keys share a much smaller 1,000 requests-per-second quota. These figures were retrieved from the AWS documentation for this article, but quotas are adjustable and change, so check Service Quotas for your account.

Two details routinely surprise teams. The quota is per account and Region, not per key, so splitting load across many KMS keys does nothing to raise it. And it counts requests made by AWS services on your behalf: S3 SSE-KMS traffic uses the same budget as your application. A noisy neighbour in your own account, a batch job calling Decrypt in a tight loop, can throttle the checkout path. Cross-account calls count against the caller’s account quota, not the key owner’s.

Custom key stores add another ceiling: operations on keys in an AWS CloudHSM or external key store count against both the account quota and a per-store quota documented as 1,800 requests per second, which is not adjustable and can be shared by multiple accounts using the same store.

Google Cloud KMS

Cloud KMS arranges keys in key rings and keys with versions, and offers software, HSM (Cloud HSM) and external (Cloud EKM) protection levels. Its envelope encryption guidance is explicit about DEKs and KEKs, and the Encrypt and Decrypt input limit is 64 KiB. Rotation creates a new primary version; per the documentation, previous versions remain active and incur costs until destroyed, and data encrypted with earlier versions is not re-encrypted automatically. That last sentence is the heart of the rotation story below.

Azure Key Vault and Managed HSM

Azure Key Vault exposes keys with wrap/unwrap, encrypt/decrypt and sign/verify operations and throttles by transactions per ten seconds per vault. The documented limits for RSA 2,048-bit keys are 4,000 non-create operations per ten seconds for software-protected keys and 2,000 for HSM-protected keys, falling to 1,000 and 500 for RSA-3072 and 500 and 250 for RSA-4096. A key-creation category is capped at 20 and 10 per ten seconds respectively. The limits are weighted, so a 4,096-bit HSM operation costs eight 2,048-bit operations. Exceeding them returns HTTP 429. Managed HSM is the dedicated, single-tenant offering with its own limits (documented at up to 5,000 keys per HSM instance and 100 versions per key). The takeaway for envelope design: RSA wrapping is expensive per operation, so wrap with AES keys where the service allows it and cache unwrapped DEKs for short windows.

HashiCorp Vault Transit

Vault’s Transit secrets engine is encryption as a service. Keys live in a keyring; rotation adds a new version, new encryptions use it, and older data remains decryptable. min_decryption_version archives old versions, and rewrap decrypts with the original version and re-encrypts with the latest without exposing plaintext, so policy can grant rewrap without decrypt. Transit supports aes256-gcm96 by default, key derivation from a context (useful for per-tenant keys derived from one master), and convergent encryption for deterministic lookups. Datakey set generation for envelope encryption is documented as an Enterprise feature, so open source users generate DEKs in the client or use the plain datakey endpoint. Unlike the hyperscaler services, you operate Vault: its availability, seal, backup and storage backend become your problem, which is the price of portability.

Comparing the services for envelope work

Dimension	AWS KMS	Google Cloud KMS	Azure Key Vault / Managed HSM	Vault Transit
Wrap primitive	GenerateDataKey, Encrypt	Encrypt, Decrypt on CryptoKey	wrapKey, unwrapKey	encrypt, datakey, rewrap
Documented single-call data size	4 KB (verify)	64 KiB	RSA/key dependent	Larger, limited by request size and config
Throttle model	Per account and Region per second	Per project quotas (verify)	Per vault per 10 seconds, weighted	Your cluster capacity
Automatic rotation	Yes, 90 to 2,560 days, default 365	Scheduled rotation, new primary version	Rotation policy on keys	Manual or scripted rotate
Rewrap without plaintext	ReEncrypt	Re-encrypt flow via your code	Your code	rewrap
Operated by	Provider	Provider	Provider	You or HCP

Use the table as a starting point. The row that matters most for your design depends on whether you are throughput-bound (quotas), compliance-bound (HSM level and key custody) or portability-bound (multi-cloud).

HSMs, FIPS 140-3 Levels and Who Holds the Root

An HSM’s value is not speed but a defined boundary: keys are generated and used inside, the module resists tampering, and operations are authenticated and logged. NIST’s cryptographic module validation program validates modules to FIPS 140-3, which is built on ISO/IEC 19790 (requirements) and ISO/IEC 24759 (test methods). The standard defines four security levels across eleven requirement areas, each level adding protection over the one below.

The practical reading, hedged because the detailed text is in the ISO documents: Level 1 is essentially a validated algorithm implementation with no physical protection requirement, and is common for software modules. Level 2 adds tamper-evidence and role-based authentication. Level 3 adds tamper-resistance and response, meaning the module detects intrusion and zeroises critical parameters, plus identity-based authentication and stronger separation of interfaces. Level 4 adds protection against environmental attacks such as temperature or voltage manipulation and is rare. Cloud KMS documentation aiming at regulated customers consistently cites Level 3, as AWS does for KMS.

Two cautions. A “FIPS validated” label applies to a specific module version and operating configuration, so check the certificate (AWS cites NIST certificate 4884 for the KMS HSMs) and whether your usage mode matches the validated mode. And validation of the HSM does not validate your application: if you export a DEK and put it in an unprotected log line, the HSM did its job and you still lost.

BYOK, HYOK and external key stores

Customers who cannot accept provider custody have three escalating options. Bring Your Own Key (BYOK) means you generate key material, typically in your own HSM, and import it wrapped into the provider’s KMS. The provider holds a copy in its HSMs, so you control provenance and can delete your imported material, but the provider can technically use it. AWS notes that imported-material keys cannot use automatic rotation and that deleting a symmetric imported key is final, since you cannot recreate a key that decrypts its old ciphertexts even with the same material (the documentation states this for symmetric keys).

Hold Your Own Key (HYOK) and external key stores keep the key outside the provider entirely. AWS external key stores and Google Cloud EKM forward wrap and unwrap requests to a key manager you operate. The cryptographic custody is yours; so is the availability. Every decrypt now depends on your key manager’s uptime, the network path to it, and its throughput. AWS documents that external key store throttling surfaces through an ExternalKeyStoreThrottle metric and a shared 1,800 requests per second ceiling per store.

The trade-off is stark. External custody gives a revocation lever: cut the key manager off and the cloud provider cannot read the data. But in practice the revocation lever is also a self-inflicted outage lever, and the services layered above the KMS (a managed database, a search index) may not tolerate a key that disappears mid-flight. Choose it for a regulatory mandate or a sovereignty requirement, not for a vague feeling of control. Confidential computing offers a complementary trust model, where keys are released only to attested enclaves; see our article on confidential AI inference with TEEs and GPU confidential computing for how attestation-gated key release works.

Access Policy, Encryption Context and Audit

Key management is an access-control problem with an audit trail attached. The cryptography is the same whether the right or wrong service unwraps a key; policy decides which.

Encryption context

Encryption context is a set of non-secret key-value pairs bound to the ciphertext as additional authenticated data. AWS documents it as optional, string-only, supported on symmetric KMS keys but not on asymmetric or HMAC keys, required to match on decrypt, and recorded in plaintext in CloudTrail. That last fact has two consequences. It is excellent for auditing, since you can see which key was used for which tenant or object. And it must never contain secrets or personal data.

Encryption context also enters policy. A key policy can allow kms:Decrypt only when kms:EncryptionContext:AppName equals a value, or only when certain context keys are present (kms:EncryptionContextKeys). Grants can carry EncryptionContextEquals or EncryptionContextSubset constraints. Used well, this converts a coarse “service X may decrypt with key K” into “service X may decrypt with key K only for tenant 42’s records”, which is the difference between a breach of one service exposing everything and exposing a slice.

Least privilege by operation

Separate encrypt from decrypt. Producers that only write need GenerateDataKey and Encrypt, not Decrypt. A re-encryption job needs ReEncrypt or rewrap, which on Vault can be granted without decryption rights. Key administrators who can change policy or schedule deletion should not hold decrypt rights, and vice versa. Pair this with workload identity so the caller is a verified service, not a shared credential.

Audit and detection

Every key operation should land in an immutable log. For AWS, CloudTrail records KMS API calls including the encryption context; for Google, Cloud Audit Logs; for Azure, Key Vault diagnostic logs. The useful detections are behavioural: a sudden spike in Decrypt volume from one principal (a bulk exfiltration pattern), Decrypt calls from an unexpected network or Region, ScheduleKeyDeletion or DisableKey events outside a change window, and failed decrypts with mismatched context, which often signals either a bug or an attacker replaying ciphertext across tenants. AWS also lets you alarm on use of a key in pending deletion, a cheap early warning that something still depends on a key you are about to destroy.

Runnable Envelope Encryption Example in Python

The following example uses AWS KMS through boto3 and the cryptography package. It generates a data key per object, binds tenant and object identifiers as both KMS encryption context and GCM AAD, and stores a self-describing envelope. It is a teaching sketch: it omits retries, chunking for large objects and key caching. Verify API details against your SDK versions.

import base64, json, os
import boto3
from cryptography.hazmat.primitives.ciphers.aead import AESGCM

kms = boto3.client("kms")
KEK = "alias/tenant-42-kek"          # a symmetric KMS key

def seal(plaintext: bytes, tenant: str, object_id: str) -> dict:
    ctx = {"tenant": tenant, "object": object_id}
    # 1. Ask KMS for a fresh 256-bit data key (plaintext + wrapped copy)
    resp = kms.generate_data_key(KeyId=KEK, KeySpec="AES_256",
                                 EncryptionContext=ctx)
    dek, wrapped = resp["Plaintext"], resp["CiphertextBlob"]
    # 2. Encrypt locally with a random 96-bit nonce; bind context as AAD
    nonce = os.urandom(12)
    aad = json.dumps(ctx, sort_keys=True).encode()
    ct = AESGCM(dek).encrypt(nonce, plaintext, aad)
    # 3. Drop the plaintext key reference (best effort in Python)
    del dek
    return {
        "v": 1, "kek": resp["KeyId"], "alg": "AES-256-GCM",
        "ctx": ctx,
        "wrapped_dek": base64.b64encode(wrapped).decode(),
        "nonce": base64.b64encode(nonce).decode(),
        "ct": base64.b64encode(ct).decode(),
    }

def unseal(env: dict) -> bytes:
    ctx = env["ctx"]
    resp = kms.decrypt(CiphertextBlob=base64.b64decode(env["wrapped_dek"]),
                       EncryptionContext=ctx)
    aad = json.dumps(ctx, sort_keys=True).encode()
    return AESGCM(resp["Plaintext"]).decrypt(
        base64.b64decode(env["nonce"]), base64.b64decode(env["ct"]), aad)

def rewrap(env: dict, new_kek: str) -> dict:
    # Move the DEK to a new KEK without touching the data ciphertext
    out = kms.re_encrypt(CiphertextBlob=base64.b64decode(env["wrapped_dek"]),
                         SourceEncryptionContext=env["ctx"],
                         DestinationKeyId=new_kek,
                         DestinationEncryptionContext=env["ctx"])
    env = dict(env)
    env["wrapped_dek"] = base64.b64encode(out["CiphertextBlob"]).decode()
    env["kek"] = out["KeyId"]
    return env

Notice what the design gets right. The plaintext data key exists only inside seal and unseal. The envelope records the KEK identifier, algorithm and version, so future migrations can find everything. The encryption context is authenticated twice, once by KMS when it wraps the key and once by GCM when it encrypts the data, so a ciphertext transplanted to another tenant fails at either layer. And rewrap demonstrates the key property of the hierarchy: moving to a new KEK touches only a roughly hundred-byte blob per object, never the payload.

Notice what it does not do. It does not cache, so every seal is a KMS call and consumes quota at the shared per-second rate. It does not chunk, so large objects need a streaming wrapper. And Python cannot reliably zeroise memory, so highly sensitive workloads belong in languages or runtimes with explicit secure-memory support, or behind an enclave.

Figure 2: Write and read flow for envelope encryption with a bounded DEK cache. The KMS is called on cache misses and on every decrypt of an uncached wrapped key.

Figure 2 adds the cache the code omits. On a write the application looks up a cached DEK for the tenant; on a miss it calls GenerateDataKey with the encryption context, encrypts locally with a fresh nonce, stores ciphertext, nonce and wrapped key, and inserts the DEK into the cache with age and byte limits. On a later read the wrapped key is unwrapped through KMS, unless the cache holds it. The long-description summary: caching trades KMS calls for plaintext key residency, and the thresholds define how much risk you accept.

Sizing the quota: a worked example

Suppose a service writes 20,000 objects per second at peak and reads 60,000 per second, with a fresh DEK per write and no caching. KMS demand is 20,000 GenerateDataKey plus 60,000 Decrypt calls, or 80,000 symmetric requests per second. In a region with a 100,000 requests-per-second shared quota that leaves 20 percent headroom for everything else in the account, including S3 SSE-KMS and other teams. In a 20,000-per-second region the same design needs four times the quota, or caching.

Now add a DEK cache that reuses a key for 60 seconds or 10,000 messages, whichever comes first. Writes drop from 20,000 to roughly 2 GenerateDataKey calls per second per distinct tenant key at that rate (illustrative: depends on tenant distribution), and reads that hit hot wrapped keys largely disappear. The cost: each cached DEK now encrypts up to 10,000 messages, still more than five orders of magnitude below 2^32, so the nonce bound is safe, and the plaintext key stays in process memory for up to a minute. That trade is usually acceptable. Make it a decision, document it, and alert when cache hit ratio falls, because a cold cache after a deploy is a self-inflicted quota spike.

Key Rotation: Automatic, Re-wrap and Re-encrypt

“Rotate your keys” is three different operations that vendors and auditors routinely conflate. The differences decide how much work rotation causes and how much risk it actually removes.

Figure 3: Three kinds of key rotation. Automatic rotation changes only future encryptions, re-wrapping moves DEKs to the new KEK version, and re-encryption replaces the data ciphertext as well.

Automatic rotation: new material, old data untouched

In AWS KMS, automatic rotation generates new key material for a symmetric encryption KMS key on a schedule. The configurable period is 90 to 2,560 days, with a default of 365 days when you do not set one. Only the key material changes; the key ID, ARN, policies and permissions do not, so applications and aliases need no update. Eligible keys are symmetric keys with KMS-generated material, including multi-Region keys; asymmetric, HMAC, imported-material and custom-key-store keys cannot be automatically rotated. A disabled or pending-deletion key does not rotate. Old material is retained so existing ciphertext still decrypts (the AWS rotation overview describes this; confirm in the “Rotate keys” topic). On-demand rotation also exists, with its own limits that you should verify in the current documentation.

What this achieves is narrower than people assume. New GenerateDataKey and Encrypt calls wrap under the new material. Existing wrapped DEKs remain wrapped under old material, and KMS will unwrap them on request, so an attacker who obtains decrypt access still gets old data. Automatic rotation limits the volume of data under one version of the KEK and satisfies “cryptoperiod” controls, but it does not retroactively protect old ciphertext. Google Cloud KMS is explicit about the same semantic: rotation creates a new primary version but previous versions remain active until destroyed, and data encrypted with earlier versions is not re-encrypted automatically.

Re-wrap: move DEKs to the new KEK

Re-wrapping decrypts each wrapped DEK with the old KEK version and re-encrypts it under the new, without touching the data ciphertext. It is cheap per object (one small blob, one service call) and it is what AWS ReEncrypt and Vault rewrap do; Vault notes the plaintext is never exposed to the caller. Re-wrapping is what actually lets you retire an old KEK version: once every wrapped DEK is under the new version and verified, the old version can be disabled and eventually destroyed.

The cost is proportional to the number of DEKs, not the data. A store with 50 million objects and a DEK per object requires 50 million re-wrap calls. At an allocated 5,000 requests per second that is 10,000 seconds, under three hours, but it consumes 5,000 per second of your shared quota for that window, so schedule it off-peak and throttle it (illustrative arithmetic). Per-tenant or per-table DEKs shrink that to thousands of calls, another argument for coarser DEKs where the nonce budget allows.

Re-encrypt: replace the data

Re-encryption decrypts the data and encrypts it again under a new DEK. It is the only way to retire a compromised DEK or to migrate algorithm or key size, and also the most expensive: every byte is read, decrypted, encrypted and rewritten. Run it when you suspect a DEK leaked, when a DEK has approached its invocation limit, or when changing cipher or format. For petabyte stores it is a multi-week background project and should be designed as an incremental, resumable job with per-object versioning in the envelope header (the "v": 1 field in the earlier example is there for this).

Which rotation do you need?

Trigger	Operation	Why
Compliance cryptoperiod, no incident	Automatic rotation	Bounds future exposure per key version
Retire an old KEK version	Re-wrap	Moves DEKs, leaves data
Suspected KEK compromise	Re-wrap now, then rotate again and revoke old	Stop old version being usable
Suspected DEK compromise or nonce budget exhausted	Re-encrypt affected data	Only way to replace the exposed key
Cipher or format migration (including post-quantum)	Re-encrypt	New algorithm needs new ciphertext

Treat rotation as a tested runbook, not a checkbox. The failure that bites is rotating the KEK and then deleting the old version before every wrapped DEK was migrated, which turns an operational task into data loss. Always scan for wrapped keys by version before retirement, and prefer disable over destroy until a long soak period has passed.

Crypto-Shredding: Deleting Data by Deleting Keys

Erasure obligations (a customer’s right to deletion, a retention expiry, a decommissioned tenant) collide with the reality that data lives in primary stores, replicas, search indexes, caches, analytics extracts and backups. Deleting rows from the primary does nothing for a tape from last March. Crypto-shredding solves this by making the ciphertext meaningless: destroy every copy of the key that can decrypt it and the data is effectively erased, wherever its bytes remain.

Figure 4: Crypto-shredding workflow. Disable first, wait out a safety window, then schedule deletion; replicas and exports of the key must be destroyed too.

Architecture requirements

Crypto-shredding is only as strong as the key boundary. Four requirements follow. First, the erasure unit must map to a key: per-tenant, per-user or per-record KEKs. If a tenant’s data shares a KEK with other tenants, you cannot shred one without the others. Second, all wrapped DEKs for that unit must descend from the shredded KEK only; a DEK wrapped under two KEKs, or a plaintext DEK cached in a log, defeats the scheme. Third, no plaintext copies of the data may exist outside the encrypted store (an unencrypted search index or analytics export is a bypass). Fourth, every copy of the KEK, including backups, multi-Region replicas and exports, must be destroyed.

Using the cloud services

In AWS KMS, deletion is scheduled with a waiting period of 7 to 30 days (default 30; the actual period can run up to 24 hours longer). During pending deletion the key cannot be used in any cryptographic operation, you can cancel, and after the period ends the key material is deleted and cannot be recovered. AWS recommends disabling a key instead if you are unsure, and supports a CloudWatch alarm if anyone attempts to use a key in pending deletion. A subtlety: scheduling deletion makes the key unusable immediately, but resources protected by data keys are not affected until the KMS key is used again, which is exactly why the waiting period is a safety net rather than an erasure guarantee: data you thought was shredded may still be decryptable from an in-memory cached DEK until it expires.

Multi-Region keys complicate shredding. AWS states that a primary key cannot actually be deleted until all of its replica keys are deleted, and that replicas are fully functional keys with their own policies, so a tenant “erasure” must delete the replicas deliberately. Imported-material keys add another wrinkle: AWS notes that for asymmetric and HMAC keys with imported material you can recreate an equivalent key from the original material, which means the original material itself, wherever you keep it, is a copy that must be destroyed to complete the shred.

Backups, caches and legal reality

Backups are where crypto-shredding is most valuable and most often misapplied. If backups contain the ciphertext and wrapped DEKs, and the KEK is gone, the backup is unreadable and need not be edited. If backups also contain the plaintext KEK (a naive key-vault backup restored with the data), you have not shredded anything. Isolate key backups from data backups and apply deletion to both.

Whether cryptographic erasure satisfies a given legal erasure obligation is a question for counsel and the regulator, not for architecture, and you should not assume it does. Some interpretations accept destruction of keys when data is rendered effectively inaccessible; others require more. What the architecture can do is give you an auditable, per-subject, provable deletion event, with a log record of key disablement and scheduled deletion, which is a far stronger starting position than “we ran DELETE and hope the backups age out”.

The inverse hazard deserves equal respect: crypto-shredding is irreversible, so accidental or malicious key deletion is a data-destruction attack. Defend with separation of duties (the person who schedules deletion cannot also approve it), long waiting periods, alerting on ScheduleKeyDeletion, and deletion protection controls where the platform offers them.

Multi-Region Keys, Disaster Recovery and Availability

A KMS is a dependency on every read path, which makes its availability and regional scope architectural. AWS multi-Region keys address the DR case: related keys in different Regions share a key ID and key material, so ciphertext encrypted in one Region decrypts in another without a cross-Region call and without re-encryption. Exactly one is primary; replicas can be promoted. Key material and rotation settings synchronise from the primary, while policies, grants, aliases, tags and enabled state are independent and not kept in sync, which means a policy fix in one Region does not propagate. Automatic and on-demand rotation can be performed only on the primary. You cannot convert a single-Region key to a multi-Region key; existing data would need re-encryption. Many AWS services currently treat multi-Region keys as single-Region, so S3 replication, for example, re-encrypts under the destination Region’s key.

Design implications. Every regional deployment should have a local key it can reach without crossing a Region boundary, because a cross-Region unwrap during an outage compounds the failure. Wrapped DEKs written in Region A with a multi-Region key are readable in Region B at failover, so the DR plan must verify the replica policy actually allows the DR role to decrypt, which is the most commonly missed check. Test failover with real decrypts, not just by checking that a replica exists.

If you must use independent keys per Region, store the wrapped DEK twice (one per region’s KEK) or re-wrap asynchronously, accepting a window where fresh writes are not decryptable in the other Region.

Trade-offs, Gotchas, and What Goes Wrong

KMS as a single point of failure. If the key service is unreachable or throttling, you cannot unwrap DEKs, and every read of uncached data fails. Mitigation: a bounded DEK cache so hot data survives short outages, regional redundancy, retries with exponential backoff and jitter, and graceful degradation (read-only modes, stale reads). A cache extends survival time but widens exposure; choose thresholds deliberately, and note that a cold cache after a restart during an outage is the worst case.

Throttling cascades. The shared per-account quota means one runaway job starves everything. Symptoms are ThrottlingException in logs, rising latency, and retry storms that worsen the problem. Mitigate with client-side rate limiting, per-service quotas of your own, backoff with jitter, and separate accounts for unrelated workloads, since quotas are per account and Region. Remember managed services count too: an S3-heavy job using SSE-KMS can drain the budget your application needs.

Nonce reuse and counters. Random 96-bit nonces are safe under about 2^32 messages per key; reused cached DEKs and long-lived keys can quietly exceed that. Deterministic counters are safe only if never repeated across crashes and replicas. Count usage per DEK and enforce a hard cap well below the bound.

Plaintext key residency. A cached DEK lives in process memory, swap, core dumps and possibly logs. Disable core dumps for services handling keys, avoid logging request payloads, and on managed runtimes accept that zeroisation is best effort.

Context mismatch on migration. Encryption context must match on decrypt. If you rename a bucket, move records between tenants, or change how you build the context string, decrypts fail. Design stable identifiers for the context and store enough to rebuild it, as AWS suggests.

Rotation without inventory. If you do not know which DEKs sit under which KEK version, you cannot safely retire anything. Record KEK ID and version in every envelope, and keep a queryable inventory.

Key deletion mistakes. Deleting a key still referenced by backups, or by a downstream system you forgot, is permanent data loss. Disable first, alarm on use, wait, then delete.

Over-trusting the checkbox. Provider-managed default encryption protects against stolen disks, not against an authorised but compromised identity. Envelope encryption with per-tenant keys and context-bound policy is what narrows the blast radius of identity compromise.

Long-lived ciphertext and the quantum horizon. Symmetric AES-256 is considered resilient, but any asymmetric wrapping (RSA key transport, imported material wrapped with RSA) is exposed to harvest-now-decrypt-later. Prefer symmetric KEKs for wrapping where possible and plan the migration path described in the post-quantum guidance linked below.

Practical Recommendations

Start from the unit of erasure and the unit of isolation, and let them decide your key granularity. For a multi-tenant system that means a KEK per tenant, a fresh DEK per object or small batch, and the tenant and object identifiers bound as both KMS encryption context and GCM AAD. Use the provider’s FIPS-validated KMS unless a regulation demands external custody; adopt BYOK or an external key store only when you have staffed the availability burden that comes with it.

Treat quotas as design inputs. Compute your steady and peak KMS demand, compare it with the documented shared quota for your Region, and add a bounded DEK cache or hierarchical keyring if you are within 50 percent of the limit. Alert on throttling and cache hit ratio. Separate unrelated workloads into separate accounts so they do not share a budget.

Make rotation boring. Enable automatic rotation where eligible, record KEK versions in envelopes, run re-wrap jobs on a schedule, and test the full runbook, including restoring from backup after a rotation. For crypto-shredding, rehearse the whole flow on a test tenant, including replicas and backups.

A checklist to adopt:

Envelope includes version, KEK ID, algorithm, nonce, encryption context and wrapped DEK.
Fresh DEK per object, or a hard invocation cap well below 2^32 per key.
Tenant and object identifiers authenticated as AAD and as KMS context.
Separate encrypt, decrypt, administer and delete permissions; alarms on disable and delete.
Bounded DEK cache with documented thresholds; KMS quota alarms at 70 percent.
Multi-Region or regional keys tested with a real DR decrypt.
Re-wrap and re-encrypt runbooks exercised, with an inventory by KEK version.
Crypto-shred runbook: disable, soak, schedule deletion, destroy replicas and key backups, log the event.

Nothing here is legal or compliance advice; map the controls to your own regulatory obligations.

Frequently Asked Questions

What is envelope encryption and why is it used?

Envelope encryption encrypts data with a data encryption key (DEK) and then encrypts that DEK with a key encryption key (KEK) held in a KMS or HSM. It is used because KMS services cap request size and throughput, so they cannot process bulk data directly. Wrapping DEKs keeps the heavy work local and fast, lets you rotate or revoke the KEK centrally, enables per-tenant keys, and limits what any single compromised credential can decrypt.

How is a KMS different from an HSM?

An HSM is tamper-resistant hardware that generates and uses keys inside its boundary. A KMS is a service layer that provides APIs, policy, auditing and rotation, usually backed by HSMs. AWS KMS, for example, states its keys are protected in FIPS 140-3 Security Level 3 validated HSMs. A KMS adds multi-tenant access control and integration with cloud services, while a dedicated HSM or CloudHSM gives you single-tenant hardware and more custody, at higher operational cost.

How often should I rotate encryption keys?

Rotate by cryptoperiod, usage volume and incident, not only the calendar. AWS KMS lets automatic rotation run from 90 to 2,560 days with a 365-day default; Google Cloud KMS gives 90 days as an example schedule. For AES-GCM with random nonces, also keep each DEK well below the 2^32 invocation bound from NIST SP 800-38D. Rotate immediately after a suspected compromise, and remember rotation alone does not re-encrypt old data.

Crypto-shredding deletes the keys that decrypt data so the ciphertext, including copies in backups, becomes unreadable. It needs per-subject or per-tenant keys and complete destruction of every key copy. Whether it satisfies a specific legal erasure duty depends on the regulator’s interpretation and your facts, so involve counsel; architecture provides the auditable mechanism, not the legal conclusion.

Does AES-GCM have a limit on how much I can encrypt with one key?

Yes. With random 96-bit IVs, NIST SP 800-38D limits the number of encryptions under one key to 2^32, keeping the chance of an IV collision below about 2^-32. A single message is also bounded at roughly 64 GiB of plaintext, so large objects must be chunked. Using a fresh DEK per object sidesteps the problem. Tag truncation below 128 bits raises forgery risk and is best avoided.

What happens if the KMS goes down?

You cannot unwrap uncached DEKs, so reads and writes that need fresh keys fail. Mitigate with a bounded DEK cache, regional key replication such as AWS multi-Region keys, client backoff with jitter, and a DR plan tested with real decrypts. Recognise that every cache increases plaintext key residency, so choose thresholds that match your outage tolerance and your security posture together.