Crypto-shredding does not delete anything from your old backups

An erasure request comes in. The person's data is in your database, in three replicas, and in nightly backups you keep for five years because a regulator told you to. You cannot rewrite a backup. Most teams answer with crypto-shredding: encrypt every record under its own key, and when the record must go, delete the key. Ciphertext without a key is noise, so the backups are dealt with by definition.

I built exactly this, wrote "every copy in every backup becomes unreadable at the same moment" in the README, and then traced what a backup actually contains. The sentence was false. This is what I found, what closes the gap, and what it costs.

How crypto-shredding is supposed to work

The standard shape is envelope encryption. Each record gets its own random data key, the DEK. The DEK encrypts the record. A master key, the KEK, encrypts the DEK, and that wrapped DEK is stored next to the ciphertext. The master key lives somewhere else: an environment variable, a file, a KMS.

row:  id | wrapped_dek = KEK(dek) | ciphertext = dek(data)

Reading a record means unwrapping its DEK with the master key and decrypting. Erasing a record means setting wrapped_dek to NULL. The ciphertext stays, which is convenient: the row still exists, the erase is visible, and the audit log can say when it happened. Nothing can turn the ciphertext back into data, because the only key that could is gone.

Replicas copy the NULL. Backups taken from now on copy the NULL. So far, all true.

The hole

The wrapped DEK is data. It sits in the same row as the ciphertext, so every backup taken before the erasure contains both. And the master key that wraps it is still the master key you use every day.

Restore last month's backup, point the service at it with the current master key, and the erased record is back. Not through a bug, through the design working as designed. "Delete the key" deleted it from the live database and from the future. The past kept a copy.

Here is the honest table for a plain envelope scheme:

It is easy to miss because the claim sounds like a property of the cipher. It is a property of where the keys are. Several commercial "privacy vaults" state the strong version in their marketing. Mine did too, for about a week.

What actually closes it

The master key has to die as well. The procedure is rotation with retirement:

1. Generate a new master key. Load both: new one current, old one for reading.
2. Re-wrap every live DEK under the new key. This touches only the wrapped keys, a few dozen bytes per row; the ciphertext is never re-encrypted, so it is cheap and runs while the service is up.
3. Destroy the old master key. Everywhere: the environment, the file, the secret store, the KMS, and your backups of the key material itself.

After step 3, every backup taken before the rotation holds wrapped DEKs under a key that no longer exists. Those backups are now truly noise for every record that was erased before the rotation. Records that were live at rotation time were re-wrapped and are fine.

So the real guarantee reads:

An erased record is unrecoverable from the live database immediately, and from any backup older than the last master key destruction.

Which means your erasure promise is your rotation cadence. If you tell people their data is gone within thirty days, you rotate and destroy at least monthly, and you keep the receipts.

Two details bite here. If the master key lives in a KMS, "destroy" is whatever the KMS calls it, usually a scheduled deletion with a waiting period; the erasure is complete when that period ends, not when you clicked. And if you back up your master keys, the old version has to leave those backups too, or you have just moved the problem one level up.

The same shape, elsewhere

Once you see it, it is everywhere the wrapped key travels with the data:

• WAL archives and point-in-time recovery. The pre-erasure row is in the WAL stream you keep for PITR.
• Cloud snapshots of the volume or the managed database.
• Logical replication targets and analytics copies.
• Dumps on laptops. The pg_dump someone took to reproduce a bug.
• The key service's own versions. Vault's transit engine keeps old key versions until you raise min_decryption_version; until then, "rotated" keys still decrypt.

Each of these is answered by the same rule: the record is dead when the key that wrapped its DEK is dead, and not before.

Things that go wrong while rotating

Re-wrapping sounds trivial until it runs against a live system.

Do not resurrect a shredded row. Rotation reads a row, gets its wrapped DEK, re-wraps it, writes it back. If an erasure happened between the read and the write, the write puts a valid key back into a row that was just shredded. The fix is one predicate on the update:

UPDATE objects SET key_id = $1, wrapped_dek = $2
WHERE id = $3 AND key_id = $4 AND deleted_at IS NULL

The row's own deleted_at decides, atomically, whether a key may be written.

Page, do not transact. Re-wrapping a million rows in one transaction holds locks for the duration and fails as a whole. Walk the table in pages of a few hundred, ordered by primary key, each row its own small update.

Skip what you cannot open, and report it. A row that names a key you no longer have, or that does not open at all, must not stop the rotation of every other row. Count it, log its id, exit non-zero at the end so the operator looks.

Do not treat a network error like a bad row. A key service that is unreachable is a reason to stop, not a row to skip; otherwise one outage quietly leaves half your table under the old key.

A checklist

• Write the guarantee in the negative form in your threat model: what is not erased, and until when.
• Decide where wrapped DEKs live. Next to the data is simplest, and then rotation cadence equals erasure guarantee. A separate key store with a short backup retention makes data backups useless sooner, at the cost of another system.
• Automate rotation with retirement, and make destroying the old key part of the runbook, including its backups and its KMS versions.
• Guard the re-wrap against concurrent erasure, page it, and make it report what it skipped.
• Put the date of the last key destruction somewhere an auditor can read it. That date is your answer to "when was this person actually gone."

Where this came from

I ran into this while building sealbox, a small self-hosted vault for personal data: your application stores a token, sealbox stores the ciphertext under a per-record key, and an erasure request is one call that shreds everything about a person. Rotation is built in, works with a local master key or with Vault, OpenBao and AWS KMS, and the README now says exactly which backups die when. It is pre-alpha and has not been audited by anyone but me; if you read threat models for a living, I would like to hear where else I am wrong.

The short version of the whole post: deleting the record's key is half of crypto-shredding. Killing the key that wrapped it is the other half, and nobody puts that half in the headline.