Envelope Encryption and the Two-Level Key Hierarchy

Encrypting a million stored objects under one key means that every one of them is exposed the moment that key is exposed, that rotating it requires rewriting a million ciphertexts, and that the key must be reachable by every process that reads any object. Encrypting each object under its own key means a million keys to generate, distribute, back up, and revoke. Envelope encryption resolves the dilemma by splitting the key into two levels with different lifetimes and different exposure, at the cost of one extra decryption per read and a wrapped-key field on every record.

The two keys and their jobs

A data key encrypts the payload. It is generated per object, per volume, or per session, used for a bounded amount of data, and normally exists only inside the process that performs the encryption or decryption. A master key — the key-encryption key — never touches the payload. Its only job is to encrypt data keys, a operation called key wrapping.

The stored record therefore carries two things: the ciphertext of the payload, and the wrapped form of the data key. The master key stays in one place, usually a hardware module or a service that holds it, and the storage layer sees only wrapped data keys. Compromising the storage layer yields ciphertext and wrapped keys, neither of which is usable without the master key.

The hierarchy is not limited to two levels. NIST SP 800-57 describes a general structure in which a root key of key-encrypting keys protects a set of key-encrypting keys, which protect data keys, with each level having a narrower scope and a shorter life than the one above. Two levels cover most systems; a third appears when a single organization needs per-tenant or per-region isolation under one root.

The reason the split works is that the two key types have incompatible requirements. A data key must be available wherever the data is processed, must be cheap, and can be discarded after use. A master key must never be available at the point where bulk data lives, must be expensive to extract, and must persist. Putting both roles on one key forces a compromise between availability and isolation; splitting them lets each be optimized separately.

Wrapping is not just encryption

A wrapped key is ciphertext of a key, and the obvious construction is to encrypt the data key under the master key in a standard mode. That construction is weak in a specific way: the wrapped value has no integrity, so an attacker with write access to the stored record can alter bytes of the wrapped key. The alteration produces a different unwrapped key, and the decryption of the payload then fails in a way that leaks information or, worse, yields a key the attacker has influenced.

AES Key Wrap, specified in RFC 3394, addresses this by building a keyed integrity check into the construction. It processes the key in 64-bit blocks and, after each block, applies a round function to a running 64-bit integrity register initialized with a constant. The final register value is prepended to the output, so the wrapped key is eight bytes longer than the key it wraps, and unwrapping verifies the register against the constant before releasing any plaintext. A 256-bit key therefore wraps to 40 bytes. The construction is deterministic: the same key and the same master key always produce the same wrapped bytes, which makes it usable as a stored field without per-record nonces.

Deterministic wrapping has a consequence worth naming. Identical data keys wrap to identical bytes, so an observer of the store learns which records share a key. That is usually acceptable, since data keys are per-object and distinct, but it does mean wrapping does not hide key equality.

The alternative is authenticated encryption with a nonce, such as AES-GCM, which needs a fresh nonce per wrap and stores it alongside. That gives probabilistic wrapping and a stronger notion of secrecy, at the cost of a longer record and a nonce that must never repeat under the same master key. Where the master key lives in hardware that exposes a wrap operation, the hardware defines which construction is available, and the choice is made for you.

Binding the wrapped key to its context is a separate control. Encrypting the data key under a master key derived from both the master secret and a context string — the object identifier, the tenant, the storage class — means a wrapped key moved to another record unwraps to the wrong key or fails integrity. HKDF, specified in RFC 5869, is the standard tool for this: extract a pseudorandom key from the master secret, then expand it with the context as info. The same master secret then yields independent wrapping keys per context without storing any of them.

What the indirection costs

Every read now involves two cryptographic operations instead of one: unwrap the data key, then decrypt the payload. For bulk reads the second dominates, since unwrapping touches 32 to 40 bytes and the payload may be megabytes. For small records the ratio inverts, and the unwrap can be the larger cost. Systems that store many tiny objects often cache unwrapped data keys for a short interval to avoid paying it per record.

The wrapped-key field costs 40 bytes or so per object. At a million objects that is tens of megabytes, which is negligible against the payload; at a billion small records it becomes a real fraction of the store, and the design shifts toward larger encryption units.

Master-key operations become a shared dependency. If unwrapping happens in a remote service, every read acquires a network round trip and the availability of that service becomes the availability of the data. If unwrapping happens in a local hardware module, throughput is bounded by the module. Both are reasons to keep data keys alive briefly rather than unwrap per request, and both turn a cryptographic design into a capacity-planning problem.

Rotation is the payoff. Rotating the master key means re-wrapping data keys, not re-encrypting payloads: 40 bytes per object instead of the whole object. That operation is small enough to run online. The data keys themselves do not change, so ciphertext stays valid, and the rotation is a rewrite of one field per record. The limits of that trick are discussed in key rotation and re-wrapping.

Deletion gains a second meaning. Discarding a data key makes its payload unreadable even if the ciphertext survives, because the wrapped form is useless without the master key and the master key never touched the payload. That is cryptographic erasure, and it is the only deletion primitive that works on write-once media and on backups that cannot be reached.

Where the model leaks

The first leak is the master key’s own protection. Envelope encryption moves the problem rather than eliminating it: the master key must be stored somewhere, and if that somewhere is a file on the same host as the data, the separation is nominal. The design only holds when the master key sits behind a boundary the data path cannot cross, which is what hardware security modules provide.

The second is metadata. The wrapped key reveals the algorithm and length of the data key, and if the same data key encrypts several records, it reveals their grouping. Access patterns over wrapped keys are visible to anyone who can list the store.

The third is key reuse under a master key. Wrapping many data keys under one master key without context binding means the master key’s security is amortized over all of them; a single unwrap oracle that answers for arbitrary wrapped keys is a decryption oracle for the master key. Rate limits and context binding are the mitigations, and both are properties of the wrapping service, not of the cipher.

The fourth is the cache. An unwrapped data key held in process memory for reuse is a plaintext key outside the hardware boundary. Its lifetime, its memory protection, and its handling on fork are the subject of protecting key material in memory and at rest.

A final structural point: the hierarchy only helps if the levels are enforced by something other than convention. A service that can call the unwrap operation for any wrapped key it is handed has the master key’s power in practice, whatever the API suggests. Authorization at the unwrap call — which caller, which context, which record — is where the hierarchy becomes real.