Encryption and key management
Keys that encrypt keys, rotation, and hardware that never gives up a secret.
01The intuition
The problem it solves
You store a billion files. If a disk is stolen, or a backup tape goes missing, or an engineer copies a bucket, the bytes should be useless to whoever has them. So the files are encrypted. But encryption only moves the problem: now the key must be protected, and a key is a small string that is easy to copy. Put the same key on every server and one compromised server gives away every file ever written. Put a different key in every file's row and the database that holds the rows becomes the thing to steal.
A second problem is change. Keys should be rotated, which means re-encrypting. Re-encrypting a billion files to rotate one key would take weeks.
Build it one piece at a time
Step 1: one key per file (the data encryption key, DEK). When a file is written, generate a fresh random key, encrypt the file with it, and store the ciphertext in object storage. A stolen disk now holds files each locked with its own key, and the keys are not on the disk.
Step 2: wrap the DEK with a master key (the KEK). The per-file key must be kept somewhere. Encrypt it with a master key and store the wrapped DEK next to the file's metadata. The master key is the only one that must be guarded.
| File | Ciphertext location | Wrapped DEK (stored) | KEK used |
|---|---|---|---|
| report.pdf | bucket/ab12 | wrap(KEK-7, dek_1) | KEK-7 |
| photo.jpg | bucket/ab13 | wrap(KEK-7, dek_2) | KEK-7 |
Step 3: never let the master key leave the key service. The master key lives in a key management service backed by hardware security modules, devices that perform encryption inside themselves and are built to never output the key. Application servers call the service: "unwrap this DEK for me". They receive the file key, use it, and discard it. The master key itself is never in a server's memory.
Step 4: rotate cheaply. To rotate the master key, create KEK-8 and re-wrap the DEKs: each is 32 bytes, so a billion files means re-wrapping 32 GB of keys, not re-encrypting petabytes of data. Old versions are kept for decrypting old wraps until every wrap has been rewritten. The files never change.
Step 5: control and record every use. Each unwrap call is an authorization decision (may this service unwrap keys for this tenant?) and an audit log line (who, which key, when). A tenant can be given their own KEK, so deleting that one key makes all their data unreadable, which is how "delete everything" can be made fast and verifiable.
Why it works, with the numbers
Envelope encryption keeps the expensive and the sensitive apart. Encrypting data is fast and happens everywhere; guarding keys is slow and happens in one place.
rotate KEK: 109 wraps × 32 B = 32 GB rewritten; re-encrypt data instead: 109 files × 1 MB = 1 PB rewritten
A key service at 3,000 unwraps a second is comfortably one small cluster of HSMs, because each unwrap is a single AES operation on 32 bytes. The guarantee is that a stolen copy of storage, or of the metadata database, or of an application server, is not enough on its own to read data: an attacker needs the storage, the wrapped keys and a live, authorised path into the key service. The honest limits: a compromised application server can unwrap the keys it is authorised for while it is compromised; keys are cached in memory briefly for performance, so memory dumps matter; and losing the master key, for example a backup that was never tested, loses everything, so key backups are the one place where redundancy beats secrecy.
The trade-off you must say out loud
Every read now includes a call to the key service, so it must be highly available and fast, and that is a dependency you have added to everything. Caching unwrapped keys for a few minutes removes most of the calls at the cost of a longer window after revocation. The interviewer's follow-up is how a user "deletes" data instantly when backups exist, which is crypto-shredding: destroy the key and the backups become noise.
Where it shows up in the 100 Google problems
- Design a key management service: the HSM-backed service, versions, rotation, per-tenant keys, authorization and audit at 3,000 operations a second.
- Deduplicated multi-tenant storage: convergent encryption, where the DEK is derived from the content hash so identical files encrypt identically and can still be deduplicated.
- Design Google Pay: card numbers tokenised and the real numbers kept only under keys the payment servers never hold.
- Authentication platform: the signing keys for tokens are KEK-grade secrets with the same rotation story.