Design an envelope encryption pattern for PII in DB: keys, rotation, and search.
- User
Design an envelope encryption pattern for PII in DB: keys, rotation, and search.
Assistant
The user wants me to design an "envelope encryption pattern" for Personally Identifiable Information (PII) stored in a database (DB). Key aspects to cover are:
- Keys: What keys are used and how they are managed.
- Rotation: How to handle key rotation without downtime or data loss.
- Search: How to search encrypted data (since standard encryption prevents searching).
1. Deconstruct the Request:
- Context: PII in a DB. This implies sensitive data (names, SSNs, emails) that needs strong security (GDPR, CCPA, HIPAA compliance).
- Core Concept: Envelope Encryption. This involves encrypting the Data Encryption Key (DEK) with a Key Encryption Key (KEK).
- Why? It's faster (symmetric encryption for data) and more secure (asymmetric or isolated master key for the key itself).
- Key Components to Design:
- Keys: DEK, KEK (Master Key), KMS (Key Management Service).
- Rotation: Both DEK and KEK rotation strategies.
- Search: The tricky part. How to query
WHERE email = 'alice@example.com'if the email is encrypted?
2. Drafting the Architecture (The "Envelope"):
- Data Key (DEK): AES-256 (Symmetric). Fast. Used to encrypt the PII column.
- Master Key (KEK): RSA or AES (Symmetric). Stored in a Hardware Security Module (HSM) or Cloud KMS (AWS KMS, GCP KMS, Azure Key Vault).
- Process:
- App asks KMS to generate a DEK.
- KMS returns plaintext DEK and encrypted DEK (EncryptedDEK).
- App encrypts PII with plaintext DEK.
- App stores:
EncryptedPII+EncryptedDEK(often in a separate column or metadata).
3. Addressing the "Search" Constraint:
This is the biggest pain point in encryption.
- Naive approach: Decrypt everything and scan. (Too slow, security risk).
- Deterministic Encryption (DET): Same input -> same output. Good for equality checks (
email = ?). Bad for security (frequency analysis). - Format-Preserving Encryption (FPE): Good for legacy schemas, but complex to implement securely.
- Blind Index / Searchable Encryption (HMAC): Store a separate column:
HMAC(key, plaintext). This is the standard modern approach for equality search. - Full Text Search: Very hard with standard encryption. Requires specialized algorithms (not requested, but worth noting). I'll focus on equality search for PII.
4. Designing the Key Rotation Strategy:
- Rotation triggers: Compliance (e.g., every 90 days), suspected compromise, or regular maintenance.
- KEK Rotation: Easy. Re-encrypt the DEKs. No need to touch the massive data tables. Just update the
EncryptedDEKblob. - DEK Rotation: Harder. Requires decrypting data with Old DEK and re-encrypting with New DEK.
- Strategy: "Re-encrypt on read" (lazy rotation) or "Background batch job" (eager rotation). I'll propose a hybrid/online approach.
5. Structuring the Response:
I will organize the response logically:
- High-Level Architecture: Visualizing the flow.
- Key Hierarchy & Management: Defining KEK/DEK.
- Encryption Workflow (Write): Step-by-step.
- Decryption Workflow (Read): Step-by-step.
- Search Strategy: Solving the query problem.
- Key Rotation Strategy: The "How-To" for both KEK and DEK.
- Schema Design: Example SQL table structure.
- Summary/Best Practices: Security considerations.
6. Refining the Content (Self-Correction during drafting):
- Critique: Should I use Application-Layer Encryption (ALE) or DB-Layer (TDE)?
- Correction: The prompt implies "Envelope Encryption," which is almost always ALE (Application Side) to protect against DB admin access or DB compromise. TDE doesn't allow searchable patterns easily. I will assume ALE.
- Critique: How to handle search?
- Correction: Use a "Blind Index". Store
encrypted_valueandsearchable_hash. The hash is HMAC-SHA256. The key for the HMAC must be separate or derived.
- Correction: Use a "Blind Index". Store
- Critique: Rotation is complex.
- Correction: Differentiate between Crypto-Period (changing the key used for new data) and Re-encryption (changing the key for old data). I need to explain "Versioning" keys clearly.
7. Detailed Technical Specifications:
- Algorithms: AES-256-GCM (needs IV/Nonce + Auth Tag). RSA-2048 or KMS API calls.
- Storage: IV (Initialization Vector) needs to be stored. Auth Tag needs to be stored.
8. Final Polish:
- Make it readable. Use code blocks for schema and pseudocode. Use bold text for emphasis. Ensure the distinction between KEK and DEK is clear. Ensure the distinction between Encryption and HMAC (for search) is clear.
(Self-Correction on Search): I must emphasize that search on encrypted fields usually only supports exact match. Range queries (age > 25) are generally impossible without heavy Homomorphic Encryption (too slow) or leaking too much data. I will stick to Exact Match (HMAC) as the practical solution for PII.
9. Generating Output: (This matches the provided good response).
- Introduction: Definition.
- Hierarchy: KEK/DEK.
- Workflow: Write/Read.
- Search: Blind Index.
- Rotation: Detailed phases.
- Schema: Visual example.
Let's write it out. This design outlines a robust Envelope Encryption pattern tailored for PII (Personally Identifiable Information). This approach balances high security (separation of duties) with the practical need to search and rotate data.
1. High-Level Architecture
In Envelope Encryption, you do not encrypt data directly with the master key. Instead, you generate a unique key for every record (or column), encrypt the data with that local key, and then encrypt the local key with a master key.
The Hierarchy:
- Customer Master Key (CMK) / KEK (Key Encryption Key): Stored in a Hardware Security Module (HSM) or Cloud KMS (AWS KMS, Google CKMS, Azure KeyVault). This never leaves the HSM unencrypted.
- Data Encryption Key (DEK): A unique 256-bit AES key generated for a specific row or record.
- Search Key (HMAC Key): A separate key used to create searchable tokens (blind index).
2. Database Schema Design
You cannot store PII in a standard
VARCHARcolumn. You need a schema that supports the encrypted blob, the encrypted key, and the search token.Example Table:
UsersColumn Name Type Description user_idUUID Primary Key (Unencrypted). email_blobBYTEA / BLOB The encrypted PII (Ciphertext). email_key_blobBYTEA / BLOB The DEK encrypted by the KEK (The "Envelope"). email_nonceBYTEA / BLOB The Initialization Vector (IV/Nonce) used for encryption. email_hashBYTEA / BLOB The Blind Index (HMAC) for exact-match searching. kek_versionINT Identifies which Master Key version was used.
3. The Workflows
A. Writing PII (Encryption Flow)
When a new user signs up with
email: "alice@example.com":- Generate DEK: The application requests the KMS to generate a new Data Encryption Key (DEK).
- Response: The KMS returns two things:
Plaintext_DEK(Transient, in memory).Encrypted_DEK(The envelope).
- Response: The KMS returns two things:
- Encrypt Data: The app uses the
Plaintext_DEKwith an AES-256-GCM algorithm to encrypt"alice@example.com".- Output:
Ciphertextand a uniqueNonce.
- Output:
- Generate Search Token: The app calculates an HMAC (e.g., SHA-256) of the plaintext email using a dedicated HMAC Key.
Search_Hash = HMAC("alice@example.com", HMAC_KEY)
- Persist: Save the
Ciphertext,Nonce,Encrypted_DEK, andSearch_Hashto the DB. - Destroy: Discard the
Plaintext_DEKfrom memory immediately.
B. Searching for PII (Lookup Flow)
You cannot query
WHERE email = 'alice@example.com'.- Client Request: App receives a request to find user by email.
- Generate Token: The app calculates the HMAC of the search input locally.
Input_Hash = HMAC("alice@example.com", HMAC_KEY)
- DB Query:
SELECT * FROM Users WHERE email_hash = Input_Hash
- Result: The DB returns the matching row(s).
C. Reading PII (Decryption Flow)
Once the row is retrieved (via search or ID):
- Extract: Pull the
Encrypted_DEKandCiphertextfrom the row. - Decrypt DEK: Send
Encrypted_DEKto the KMS.- Prerequisite: The application must have IAM permissions to
kms:decrypt. - Response: KMS returns the
Plaintext_DEK.
- Prerequisite: The application must have IAM permissions to
- Decrypt Data: Use the
Plaintext_DEKand the storedNonceto decrypt theCiphertextback to"alice@example.com".
4. Key Rotation Strategy
Rotation is critical for compliance (e.g., PCI-DSS, HIPAA) and limiting the blast radius of a breach.
Level 1: KEK (Master Key) Rotation
- Frequency: Annually or upon suspected compromise.
- Impact: No downtime required.
- Process:
- Create a new CMK in the KMS (Version 2).
- Update application config to use Version 2 for new records.
- Re-encryption (Background Job): Read existing records, send the
Encrypted_DEKto KMS (using old key) to decrypt, then send thePlaintext_DEKto KMS (using new key) to get a newEncrypted_DEK. Update the DB row and thekek_versioncolumn. - Important: You are rotating the envelope, not re-encrypting the actual PII data. This is fast and low-overhead.
Level 2: DEK (Data Key) & Data Rotation
- Frequency: Only if the specific record was compromised or if algorithm standards change (e.g., moving from AES-CBC to AES-GCM).
- Process:
- Retrieve the record.
- Decrypt the PII completely.
- Generate a brand new DEK.
- Re-encrypt the PII with the new DEK.
- Encrypt the new DEK with the latest KEK.
- Save all new blobs to the DB.
Level 3: Search Key (HMAC) Rotation
- The Risk: If the HMAC Key is leaked, an attacker can brute-force your hashes (dictionary attack) to reveal PII.
- Strategy: This is the hardest rotation.
- Introduce a version prefix to the hash (e.g.,
v1:hash...,v2:hash...). - Application attempts to match
v2first. If not found, falls back tov1. - Lazy Re-hash: When a user logs in or updates their profile, re-calculate the hash with the new key and save
v2.
- Introduce a version prefix to the hash (e.g.,
5. Security Considerations & Best Practices
-
Algorithm Choice:
- Use AES-256-GCM (Galois/Counter Mode). It provides Authenticated Encryption, ensuring that an attacker cannot tamper with the ciphertext without detection.
- Never use ECB mode. Avoid CBC if possible (requires padding).
-
Nonce Management:
- Never reuse a Nonce (IV) with the same DEK.
- Implementation: Use a cryptographically secure random number generator (CSPRNG) to generate a 12-byte (96-bit) nonce for every encryption operation. Store it alongside the ciphertext.
-
Search Limitations:
- This pattern only supports Exact Match searches (equality).
- It does not support
LIKE %...%(wildcards), range queries (>,<), or sorting on the PII column. - Advanced Alternative: If you require complex search (e.g., "Find users over 50 near New York"), you must look into Homomorphic Encryption or dedicated encrypted search tools like Cipherva or MongoDB Queryable Encryption, but these have significant performance costs.
-
Separation of Duties:
- Ideally, the Database Admin (DBA) should not have permissions to call the KMS
decryptfunction. - The Application Server should have the
decryptpermission. - This ensures that if the DB is stolen (SQL Injection or Backup leak), the attacker only has encrypted blobs and keys they cannot open.
- Ideally, the Database Admin (DBA) should not have permissions to call the KMS
Summary Diagram
[User Input: PII] | v [App Server] <---(1. Generate DEK)---> [Cloud KMS (KEK)] | | | (Receives Plaintext_DEK & Encrypted_DEK) v [App Memory] | +---> (2. Encrypt PII with Plaintext_DEK) -> [Ciphertext] | +---> (3. HMAC PII with Search_Key) -> [Search Hash] | v [Database Storage] +----------------+------------------+------------+ | Ciphertext | Encrypted_DEK | Search_Hash| +----------------+------------------+------------+
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.