Deleting a user's data from backups: crypto-shredding with one key per person

#security #privacy #rust #python

A user asks you to delete their data. You delete the row. Then you remember the replica, last month's backup, the S3 export someone made for analytics, and the log line with their email in it. You can't edit most of those.

Crypto-shredding is the standard way out: encrypt each person's data under their own key, keep the keys in one small keystore, and "delete" a person by destroying their key. The ciphertext can stay wherever it is. Without the key it's noise.

I built a small library for this called aegis-shred: a Rust core, a Python package and a CLI.

from aegis_shred import MasterKey, Vault

vault = Vault.open("keys.db", MasterKey.from_env("AEGIS_MASTER_KEY"), create=True)
blob = vault.seal("user-42", b"alice@example.com", context=b"users.email")  # store anywhere
vault.unseal(blob, context=b"users.email")   # b'alice@example.com'
vault.shred("user-42")                       # erase user-42, everywhere, at once
vault.unseal(blob, context=b"users.email")   # raises aegis_shred.Shredded

How it works

master key (from your secret manager)
  └─ wraps one data key per subject ───── keystore (SQLite file)
        └─ HKDF → one key per sealed object
              └─ AES-256-GCM, chunked (STREAM)
                    └─ sealed blob/file ── your database, S3, backups, …

seal creates the subject's key on first use and returns a self-describing blob. The blob names a random key id, never the user.
unseal checks every chunk. A modified byte, a reordered or missing chunk, truncation, or a different context all fail.
shred deletes the wrapped key in one transaction, writes a tombstone and a hash-chained audit entry, and returns a receipt. From then on, in every process, that user's blobs raise Shredded.
The keystore stores subjects only as HMAC(index_key, subject_id), so the keystore and audit log don't list your users either.

The context argument binds a blob to where it lives, so a ciphertext copied from one column into another won't decrypt.

Large files are streamed in 64 KiB chunks with constant memory, and the output file only appears if every chunk verifies.

Install

pip install aegis-shred          # prebuilt wheels for Linux, macOS, Windows
cargo add aegis-shred            # Rust library
cargo install aegis-shred-cli    # the aegis command

Honest limits

This is v0.1, alpha. The byte format is specified and versioned, every guarantee has a test, and a second independent implementation in Python runs in CI. But there has been no independent security audit. Read the threat model in the repo before relying on it.

Whether crypto-shredding satisfies GDPR Art. 17, CCPA or India's DPDP Act for your situation is a question for your lawyers. The library gives you the mechanism and an audit trail, not legal cover.

Repo (MIT OR Apache-2.0): https://github.com/Lingikaushikreddy/Aegis

Feedback on the threat model and the file format is the most useful thing you could send me.

Top comments (2)

Dhruv Malaviya • Oct 15

The context binding is the most underrated part of this design. Ciphertext that only decrypts where it was written stops a whole class of bug where a blob gets copied between columns and quietly decrypts somewhere it shouldn't.

Two things worth flagging. The keystore becomes your single highest-value target , every guarantee rests on it, so it needs protection at least as strong as the data, which usually means an HSM or managed KMS rather than a SQLite file.

And the hash chain needs an external anchor. A chain only the keystore holder can extend is rewritable by the keystore holder.

Kaushikreddy Lingi • Oct 19

Thanks Dhruv, both points are fair. On the keystore: v0.1 keeps the data keys in a SQLite file wrapped by a separate master key, and the docs say to keep the master key in a secret manager or KMS and to back the keystore up apart from your general data backups. That limits the damage from losing the file but doesn't replace an HSM. A native KMS/HSM-backed keystore is the right next step, and a Postgres keystore is already planned.

On the hash chain: you're right that whoever holds the keystore can rewrite it. vault.audit_head() returns the sequence number and head hash so you can anchor them somewhere the keystore holder can't write. Right now that anchoring is left to the user, and I should make it more prominent in the docs.