Envelope encryption without a big-bang migration

I had a table full of provider tokens encrypted with one master key, and I wanted to move to per-user keys without a maintenance window. The honest problem was not the cryptography. It was migrating live rows without a big-bang cutover.

Two keys, so one leak is not enough#

The scheme is envelope encryption, and the idea is old and boring, which is what you want from anything holding secrets.

Each user gets their own Data Encryption Key, a DEK. The DEK encrypts that user’s tokens. Then a single master key encrypts each DEK. So the tokens are wrapped by the DEK, and the DEK is wrapped by the master key. Two layers, hence “envelope”.

The payoff is in what each leak buys an attacker. Leak the master key alone and you have nothing, because the wrapped DEKs live in the database you do not have. Leak the database alone and you have nothing, because every DEK is wrapped by a master key you do not have. You need both, together, to read a single token.

Rotation gets cheaper too. To rotate one user you re-wrap one DEK, not re-encrypt every token that user owns. Per-user blast radius, per-user rotation.

Each stored value is serialised as three parts joined by colons:

iv:authTag:ciphertext

The IV keeps identical plaintext from encrypting to identical ciphertext. The auth tag is what makes tampering fail loudly instead of decrypting to garbage. Keep all three or you cannot decrypt, and cannot prove the ciphertext was not touched.

The nullable column that made it incremental#

Here is the part that actually saved me. I did not migrate anything on day one.

I added a nullable column, an encryption key id, next to the encrypted token. The rule is one line of routing:

if encryption_key_id is null  -> legacy path, decrypt with the master key directly
if encryption_key_id is set   -> envelope path, load that DEK, unwrap, decrypt

Old rows have a null key id and keep working exactly as before. New writes get a key id and go through the envelope. When an old row is next written, it graduates to the new scheme and its key id fills in. The two schemes run side by side, and the table converges as normal traffic touches rows, with no migration script racing against production.

A nullable key-id column turns an encryption cutover into a gradual roll-out. Non-null rows take the new path, null rows keep the old one, and nobody schedules a big-bang.

You can backfill the stragglers later if you like, on your own schedule, because nothing is broken while they sit there. The migration is a background fact, not an event.

Never trust yourself to omit a field#

The second habit matters as much as the encryption. Ciphertext should never leave the server, and neither should a decrypted secret.

The tempting approach is to omit secret fields by hand in each API response. That works right up until someone adds a field, forgets, and ships the token to a client. Omission by discipline fails the first busy afternoon. The cost of that one slip is not abstract: a leaked provider token lets whoever finds it act as that user on the connected service, silently, until somebody happens to notice.

So every response goes through a redactor at the boundary that replaces each secret with a boolean. The client never sees a token or its ciphertext. It sees whether one exists:

hasAccessToken: true
hasCredentials: true

That is all the client needs to render “connected” and all it should ever get. The secret is projected down to a yes or no before it hits the wire.

The lesson#

Two small structural choices did the heavy lifting. A nullable key-id column let me change encryption schemes gradually instead of all at once, with old and new rows coexisting. And projecting secrets to has* booleans at the boundary meant safety came from the shape of the response, not from me remembering to strip a field.

Encrypt in envelopes. Migrate by routing, not by cutover. And let the boundary, not your memory, decide what a secret becomes on the way out.