Cryptographic Erasure: A Data Deletion Strategy Using AWS KMS

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:

1. A KMS key is used to generate a "data key"
2. The data key is used to encrypt the actual data
3. The data key itself is encrypted with the KMS key and stored
4. 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
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
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:

1. Shift your mindset from "delete the data" to "delete the key"
2. Invalidate distributed data all at once
3. AWS KMS makes it achievable in a fully managed way
4. Applicable to both user account deletions and system decommissioning
5. Cost and design require upfront planning
6. 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!