Cryptographic Erasure: A Data Deletion Strategy Using AWS KMS

Yuichi Sato — Tue, 17 Mar 2026 11:57:10 +0000

This article was originally written in Japanese and published on Qiita. It has been translated with the help of AI.
Original article: https://qiita.com/sassssan68/items/a406e971217c1523026b

Are you really sure your data is deleted?

With a shift in mindset and AWS KMS, you can effectively achieve data deletion.

This article covers:

Challenges of traditional data deletion
The concept of Cryptographic Erasure
How to implement Cryptographic Erasure with AWS KMS

Background and Challenges

Scenario 1: User Account Deletion

Imagine you're running a SaaS service and a user requests to close their account. You need to delete all of that user's data.

You might think, "Just run a DELETE statement on the database, right?" But in reality, data exists in many places:

Production database ← You can delete here
Database backups ← But there are 30 days' worth...
Log files ← Stored in S3...
Analytics data warehouse ← Copies in Redshift too...
Dev/staging environments ← Using masked production data...

Deleting everything without missing anything is practically very difficult.

Scenario 2: System Decommissioning / Service Shutdown

When a SaaS service is no longer profitable and you decide to shut it down, you still need to delete all the data you've been handling.

Just like Scenario 1, data is scattered across databases, backups, logs, and more. On top of that, cloud environments automatically replicate data for availability and fault tolerance:

Multi-AZ RDS and DynamoDB
Automated backups and snapshots stored in S3
Cross-region replicas
Data forwarded via CloudWatch Logs or Kinesis to downstream systems

On-premises, you could physically destroy the disks as a last resort, but in the cloud, you can't touch physical storage (Shared Responsibility Model). This makes it even harder to confidently say, "Everything has been deleted."

The Risks of "Thinking You Deleted It"

Lingering data poses risks such as:

Data breaches
- Data you thought was deleted gets restored from backups and leaked
Regulatory violations
- Failure to comply with GDPR's "Right to Be Forgotten" can result in fines
Audit findings
- Being flagged for "no evidence of data deletion"

What Is Cryptographic Erasure?

Destroy the Key, and the Data Becomes Garbage

Cryptographic Erasure is a sanitization method defined in NIST SP 800-88.

https://csrc.nist.gov/pubs/sp/800/88/r2/final

It's essentially a shift in mindset:

Traditional approach
- Deleting data = erasing the data itself
Cryptographic Erasure approach
- Deleting data = making the data impossible to decrypt (by destroying the key)

Encrypted data without its key is nothing more than meaningless bytes.

In other words, if you delete the key, the data is effectively deleted — even if it physically remains.

Traditional Deletion vs. Cryptographic Erasure

Item	Traditional Deletion	Cryptographic Erasure
Database	✅	↓ (Cannot be decrypted)
Backups	❌ (Cannot delete during retention period)	↓ (Cannot be decrypted)
Logs	❌ (Mixed with other logs)	↓ (Cannot be decrypted)
Analytics	△ (Requires manual work)	↓ (Cannot be decrypted)
Encryption key	—	✅

Traditional Deletion
- Complete deletion is difficult
Cryptographic Erasure
- Deleting the key renders all data unrecoverable

Benefits of Cryptographic Erasure

Invalidate all distributed data at once
- Wherever the data exists, destroying the key invalidates it all
Safe even if backups are restored
- Restored backups are unreadable without the key
Auditable evidence
- A record of "when the key was deleted" is preserved

What Is AWS KMS?

AWS KMS (Key Management Service) is a key management service provided by AWS. It allows you to securely create, store, and delete encryption keys.

https://docs.aws.amazon.com/kms/latest/developerguide/overview.html

Key features:

Fully managed
- AWS handles key storage and protection
Audit-ready
- Key usage history is recorded in CloudTrail
Integrated with other AWS services
- Can be used to encrypt S3, RDS, EBS, and more

Types of KMS Keys

AWS KMS offers three types of keys:

Type	Description	Can Be Deleted?
AWS owned keys	Used internally by AWS; invisible to users	❌
AWS managed keys	Automatically created, e.g., `aws/s3`, `aws/rds`	❌
Customer managed keys	Created and managed by the user	✅

Two Types of Customer Managed Keys

Customer managed keys are further divided into two types based on the origin of the key material (the actual cryptographic key data):

Type	Key Material	Immediate Deletion	Characteristics
KMS-generated key	Generated and managed by AWS	❌ (7–30 day waiting period)	Easy to operate
Imported key	Brought in from outside	✅	Useful when immediate deletion is required

Features Required for Cryptographic Erasure

Customer managed keys in AWS KMS have all the features needed for Cryptographic Erasure:

Key creation
- Keys can be created per user or per system
Key management
- Keys can be given aliases for easier identification
Key deletion
- Keys that are no longer needed can be deleted

Envelope Encryption

AWS KMS uses a method called "Envelope Encryption." This is the technical mechanism that makes Cryptographic Erasure work.

Here's how it works:

A KMS key is used to generate a "data key"
The data key is used to encrypt the actual data
The data key itself is encrypted with the KMS key and stored
The plaintext data key is immediately discarded

So only two things are stored: the "encrypted data key" and the "encrypted data." Neither can be decrypted without the original KMS key.

This is the key point:
When a KMS key is deleted, the data key can no longer be decrypted, and consequently, the data itself becomes unrecoverable. This is the mechanism behind "destroy the key, invalidate all the data."

Practical Design

Scenario 1: User Account Deletion

Design Approach: Issue a KMS Key per User

At user registration:
- User A registers → KMS Key A is created
- User B registers → KMS Key B is created
- User C registers → KMS Key C is created
When User A closes their account:
- Schedule deletion of KMS Key A
- After the waiting period (7–30 days), the key is deleted
- User A's data becomes unrecoverable

User B and User C's data remain unaffected.

Benefits of This Design

Only the departing user's data is invalidated
No impact on other users
Easier to comply with GDPR's "Right to Be Forgotten"

Scenario 2: System Decommissioning / Service Shutdown

Design Approach: Issue a KMS Key per System (or Tenant)

At system build:
- System X → KMS Key X is created
- All data for System X is encrypted with KMS Key X
At system decommissioning:
- Schedule deletion of KMS Key X
- After the waiting period (7–30 days), the key is deleted
- All data for System X becomes unrecoverable

Even if backups remain, the data is unreadable after restoration.

Benefits of This Design

All system data can be invalidated at once
Covers tape backups and DR site data as well
Auditable evidence of "complete deletion" is preserved

Comparing the Two Scenarios

Item	User Account Deletion	System Decommissioning
Key granularity	Per user	Per system
Number of keys	Many (one per user)	Few (one per system)
Scope of deletion impact	Single user	Entire system
Cost	High	Low

Implementation Considerations

Cost

AWS KMS incurs the following charges (as of February 2026):

Item	Cost
KMS key storage	~$1/month/key/region
API requests	~$0.03/10,000 requests

If you create a key per user, costs grow with the number of users.

Example: 100,000 users

Key storage alone: ~$100,000/month

Deletion Is Not Immediate (With Exceptions)

KMS key deletion has a mandatory waiting period:

Minimum: 7 days
Maximum: 30 days
Default: 30 days

During this period, deletion can be cancelled. This is a safety feature to prevent accidental deletion, but it cannot meet requirements for "delete everything right now."

Exception: Use Imported Keys When Immediate Deletion Is Required

KMS keys with externally imported key material are the exception.

Running the following command immediately deletes the key material. Unless it's re-imported, the data is permanently unrecoverable:

# Immediately delete the key material
aws kms delete-imported-key-material --key-id <your-key-id>

⚠️ Warning
Imported keys require generating, managing, and importing key material externally, which adds operational complexity. Carefully evaluate whether immediate deletion is truly necessary.

Design Early

Retrofitting Cryptographic Erasure into an existing system is difficult. Applying it to existing systems may require re-encrypting all data.

Use Customer Managed Keys

When you enable encryption for S3 or RDS, AWS managed keys may be used by default. AWS managed keys (aws/s3, aws/rds, etc.) cannot be deleted. Since you can't delete them, you can't perform Cryptographic Erasure — so always specify a customer managed key.

Here are the default encryption settings for major services and what's needed for Cryptographic Erasure:

Service	Default Encryption	For Cryptographic Erasure
S3	SSE-S3 or aws/s3	Configure SSE-KMS with a customer managed key (also enable S3 Bucket Key to reduce KMS API costs)
RDS	aws/rds	Create with a customer managed key specified
EBS	aws/ebs	Create with a customer managed key specified

Summary

Here are the key takeaways about Cryptographic Erasure:

Shift your mindset from "delete the data" to "delete the key"
Invalidate distributed data all at once
AWS KMS makes it achievable in a fully managed way
Applicable to both user account deletions and system decommissioning
Cost and design require upfront planning
Cryptographic Erasure requires customer managed keys

Lingering data poses risks such as data breaches and regulatory violations. Let's address them properly with Cryptographic Erasure!

DEV Community: Yuichi Sato

Cryptographic Erasure: A Data Deletion Strategy Using AWS KMS

Background and Challenges

Scenario 1: User Account Deletion

Scenario 2: System Decommissioning / Service Shutdown

The Risks of "Thinking You Deleted It"

What Is Cryptographic Erasure?

Destroy the Key, and the Data Becomes Garbage

Traditional Deletion vs. Cryptographic Erasure

Benefits of Cryptographic Erasure

What Is AWS KMS?

Types of KMS Keys

Two Types of Customer Managed Keys

Features Required for Cryptographic Erasure

Envelope Encryption

Practical Design

Scenario 1: User Account Deletion

Design Approach: Issue a KMS Key per User

Benefits of This Design

Scenario 2: System Decommissioning / Service Shutdown

Design Approach: Issue a KMS Key per System (or Tenant)

Benefits of This Design

Comparing the Two Scenarios

Implementation Considerations

Cost

Deletion Is Not Immediate (With Exceptions)

Exception: Use Imported Keys When Immediate Deletion Is Required

Design Early

Use Customer Managed Keys

Summary