Envelope encryption

Deep dive

How it works

Parts:

• DEK — random 256-bit key, one per object, encrypts the data under an AEAD.
• KEK — key-encryption key held in the KMS/HSM; wraps and unwraps DEKs, never leaves.
• Context (AAD) — tenant, object id, schema version; authenticated on wrap and on data.
• Envelope header — kek_id, wrapped DEK, nonce, tag; stored next to the ciphertext.

1. Generate a random 256-bit DEK locally (or ask the KMS: AWS GenerateDataKey returns it plaintext and wrapped).
2. Encrypt the object with the DEK under an AEAD, with AAD = context (tenant, object id, schema version).
3. Ask the KMS to wrap the DEK under the current KEK, with the same context as its AAD. Discard the plaintext DEK.
4. Store kek_id || wrapped_dek || nonce || ciphertext || tag. The KEK id/version selects the key at read time.
5. Read: unwrap the DEK via the KMS (context must match), decrypt, verify.
6. Rotate: unwrap each DEK under the old KEK, wrap under the new one, replace only the header.
7. Shred: destroy the KEK (or the tenant's KEK); remaining ciphertexts and wrapped DEKs are noise.

KMS/HSM [KEK v1, v2] ──wrap(DEK, ctx)──► kek_id, wrapped DEK (60 B)   ┐ stored
object ──AEAD(DEK, aad=ctx)──► nonce, ciphertext, tag                  ┘ together

Granularity: a KEK per tenant gives per-tenant shredding; per-object DEKs limit a leaked DEK to one object. Google suggests far fewer KEKs than DEKs.

Code

Rust, aes-gcm = "0.11" through its lowest-level in/out API (AeadInOut, detached tag), getrandom = "0.4". A local map stands in for the KMS; only wrap/unwrap expose key use. Compiled and run with the asserts below.

use aes_gcm::aead::{AeadInOut, KeyInit};
use aes_gcm::{Aes256Gcm, Key, Nonce, Tag};
use std::collections::HashMap;

type Key32 = [u8; 32];

fn rand<const N: usize>() -> [u8; N] {
    let mut b = [0u8; N];
    getrandom::fill(&mut b).expect("OS RNG");
    b
}

/// AES-256-GCM, detached tag. Output: nonce(12) || ciphertext || tag(16).
fn seal(key: &Key32, aad: &[u8], pt: &[u8]) -> Vec<u8> {
    let nonce = rand::<12>(); // random 96-bit: at most 2^32 seals per key (SP 800-38D)
    let mut buf = pt.to_vec();
    let tag = Aes256Gcm::new(&Key::<Aes256Gcm>::from(*key))
        .encrypt_inout_detached(&Nonce::from(nonce), aad, buf.as_mut_slice().into())
        .expect("length limit");
    [&nonce[..], &buf, &tag].concat()
}

fn open(key: &Key32, aad: &[u8], sealed: &[u8]) -> Option<Vec<u8>> {
    if sealed.len() < 28 { return None; }
    let (nonce, rest) = sealed.split_at(12);
    let (ct, tag) = rest.split_at(rest.len() - 16);
    let mut buf = ct.to_vec();
    Aes256Gcm::new(&Key::<Aes256Gcm>::from(*key))
        .decrypt_inout_detached(&Nonce::try_from(nonce).ok()?, aad, buf.as_mut_slice().into(),
                                &Tag::try_from(tag).ok()?)
        .ok()?; // tag checked first; plaintext is only returned on success
    Some(buf)
}

/// Stand-in for a KMS/HSM: KEKs never leave; callers only get wrap/unwrap.
#[derive(Default)]
pub struct Kms { keks: HashMap<u32, Key32>, current: u32 }

impl Kms {
    pub fn rotate(&mut self) { self.current += 1; self.keks.insert(self.current, rand()); }
    pub fn destroy(&mut self, id: u32) { self.keks.remove(&id); } // crypto-shredding
    // The wrap AAD binds the DEK to its KEK version and its owner ("encryption context").
    fn aad(id: u32, ctx: &[u8]) -> Vec<u8> { [&id.to_be_bytes()[..], ctx].concat() }
    pub fn wrap(&self, dek: &Key32, ctx: &[u8]) -> (u32, Vec<u8>) {
        (self.current, seal(&self.keks[&self.current], &Self::aad(self.current, ctx), dek))
    }
    pub fn unwrap(&self, id: u32, wrapped: &[u8], ctx: &[u8]) -> Option<Key32> {
        open(self.keks.get(&id)?, &Self::aad(id, ctx), wrapped)?.try_into().ok()
    }
}

#[derive(Clone)]
pub struct Envelope { pub kek_id: u32, pub wrapped_dek: Vec<u8>, pub sealed: Vec<u8> }

/// `ctx` (tenant/object id, schema version) is authenticated, not encrypted.
pub fn encrypt(kms: &Kms, ctx: &[u8], pt: &[u8]) -> Envelope {
    let dek: Key32 = rand(); // fresh DEK per object
    let (kek_id, wrapped_dek) = kms.wrap(&dek, ctx);
    Envelope { kek_id, wrapped_dek, sealed: seal(&dek, ctx, pt) }
}

pub fn decrypt(kms: &Kms, ctx: &[u8], e: &Envelope) -> Option<Vec<u8>> {
    open(&kms.unwrap(e.kek_id, &e.wrapped_dek, ctx)?, ctx, &e.sealed)
}

/// Rotation: re-wrap 60 bytes; the data ciphertext is never read or written.
pub fn rewrap(kms: &Kms, ctx: &[u8], e: &mut Envelope) -> Option<()> {
    let dek = kms.unwrap(e.kek_id, &e.wrapped_dek, ctx)?;
    (e.kek_id, e.wrapped_dek) = kms.wrap(&dek, ctx);
    Some(())
}

fn main() {
    let (mut kms, ctx) = (Kms::default(), &b"tenant=7/object=42"[..]);
    kms.rotate(); // KEK v1
    let mut e = encrypt(&kms, ctx, b"secret payload");
    assert_eq!(decrypt(&kms, ctx, &e).unwrap(), b"secret payload");
    assert!(decrypt(&kms, b"tenant=7/object=43", &e).is_none()); // wrong AAD fails

    let before = e.clone();
    kms.rotate(); // KEK v2
    rewrap(&kms, ctx, &mut e).unwrap();
    assert_eq!(e.kek_id, 2);
    assert_eq!(e.sealed, before.sealed); // data untouched
    assert_ne!(e.wrapped_dek, before.wrapped_dek); // only the wrapped DEK changed
    assert_eq!(decrypt(&kms, ctx, &e).unwrap(), b"secret payload");
    assert!(decrypt(&kms, ctx, &before).is_some()); // v1 still held: old envelope readable

    let mut bad = e.clone();
    bad.sealed[12] ^= 1; // flip one ciphertext bit
    assert!(decrypt(&kms, ctx, &bad).is_none());

    kms.destroy(1);
    assert!(decrypt(&kms, ctx, &before).is_none()); // shredded: v1 envelope is noise
    assert!(decrypt(&kms, ctx, &e).is_some()); // v2 envelope unaffected
}

Complexity and constants

• Encrypt/decrypt: O(n) in object size; overhead per object: wrapped DEK 60 B (12 nonce + 32 key + 16 tag) + 28 B for data (nonce + tag) + KEK id.
• KMS calls: one wrap per object write, one unwrap per cold read. This, not AES, is the latency: a KMS round trip is order of milliseconds over the network, against microseconds for the local AEAD.
• Rotation: O(objects) KMS calls, zero data bytes read or written.
• Random 96-bit nonces under one key: stay below 2^32 invocations (NIST SP 800-38D). A KEK wrapping billions of DEKs needs derived or versioned KEKs; per-object DEKs used once are no concern.

Efficiency

• Cost: measured here on an Apple M4 Pro, release build, aes-gcm 0.11 with hardware AES: seal of 4 KiB order of 2.4 µs, of 1 MiB order of 320 µs (about 3.2 GB/s, one buffer copy); local wrap order of 1 µs. A real KMS wrap adds a network round trip. Bound: KMS latency and quota, then AES throughput.
• Levers:
  • DEK caching with age/message/byte limits — N KMS calls become one per window (AWS Encryption SDK thresholds) — many small objects.
  • Hierarchical keyring — intermediate key cached locally, fewer KMS calls (AWS docs) — multi-tenant, high volume.
  • Chunk large files under one DEK (counter nonces) — one KMS call per file — large files.
  • Re-wrap, never re-encrypt — rotation touches 60 bytes per object (AWS: rotation does not re-encrypt data) — always.
  • Batch and parallelise wraps in the background — bound by KMS quota — bulk rotation or migration.
• Naive → standard → state of the art:
  • Encrypt every object directly in the KMS · one network call per object, size-capped (4096 B on AWS).
  • Per-object DEK wrapped by the KMS · one call per write/cold read; AES at memory speed.
  • Cached or hierarchical keys with thresholds · KMS calls amortised over a window.

Implementation notes

• Use the library's in/out or detached-tag API on pre-allocated buffers to avoid copies; one allocation per object, not per chunk. Check that the AES backend uses hardware instructions: on the same machine, aes-gcm 0.10 without --cfg aes_armv8 was about 5x slower (measured here); 0.11 needed no flag.
• Nonces: a random 12-byte nonce per seal is fine for single-use DEKs and for a KEK that wraps well under 2^32 keys. Otherwise use XChaCha20-Poly1305 (24-byte nonce) or a counter.
• Envelope header: version byte, algorithm id, kek_id, wrapped DEK. Authenticate the header (put it in the AAD) so algorithm downgrade or id swap fails.
• AAD binds ciphertext to its owner: a cloud operator who swaps two rows' blobs gets a tag failure. Do not put secrets in AAD; AWS logs it in CloudTrail.
• Zeroize plaintext DEKs after use (zeroization) and never log them.
• Wrapping is itself an AEAD seal here; for a KEK-only primitive see AES key wrap.
• Keep DEK caches in process memory only, keyed by (kek_id, context).

Pitfalls

• Re-encrypting data on rotation: unnecessary, and the reason the pattern exists.
• Same DEK for many objects or tenants: one leak and one nonce-reuse risk grow together.
• Context not authenticated on the wrap: an attacker moves a wrapped DEK between objects.
• KMS key deletion is irreversible; AWS enforces a 7-30 day waiting period (default 30), so shredding is not instant. Backups of ciphertext are shredded too; copies of plaintext DEKs are not.
• Caching without limits: a cached DEK that never expires defeats shredding and rotation.
• Losing KEK versions: keep old versions until every wrapped DEK is re-wrapped, or reads break.
• AES-GCM does not commit to its key: if a blob may be tried under several KEKs, add a key commitment (Albertini et al.).

Variants and alternatives

In production

• Cloud infrastructure: Google Cloud encrypts storage chunks (up to several gigabytes) with individual DEKs wrapped by KEKs in its internal KMS; AWS KMS data keys back S3, EBS and other services.
• Container platforms: Kubernetes encrypts Secrets in etcd with a DEK wrapped by a KMS-held KEK (kms v2 provider).
• Consumer devices: Apple Data Protection protects each file with a per-file key stored wrapped under a class key.
• Databases: MongoDB client-side field level and Queryable Encryption wrap data encryption keys under a customer master key in a KMS.
• Libraries: the AWS Encryption SDK and Google Tink implement the pattern client-side.

Implementations

Sources

• Google Cloud, Envelope encryption, Cloud KMS docs. docs
• Google Cloud, Default encryption at rest. docs
• AWS, AWS KMS concepts (envelope encryption, data keys). docs
• AWS, Encryption context and Rotate AWS KMS keys. context · rotation
• AWS, Data key caching and Setting cache security thresholds, AWS Encryption SDK. caching · thresholds
• AWS, AWS KMS Cryptographic Details. docs
• Dworkin, NIST SP 800-38D: GCM and GMAC, 2007. doi
• Barker, NIST SP 800-57 Part 1 Rev. 5: Recommendation for Key Management, 2020. nist
• Albertini, Duong, Gueron, Kölbl, Luykx, Schmieg, How to Abuse and Fix Authenticated Encryption Without Key Commitment, USENIX Security 2022. eprint
• Kubernetes, Encrypting Confidential Data at Rest (KMS provider, DEK/KEK). docs
• Apple, Data Protection classes, Apple Platform Security. docs
• MongoDB, Keys and Key Vaults (In-Use Encryption). docs