Identical Backup Blocks and a Restore Oracle
A SaaS provider stores tenant backups with AES-256-CBC in a custom Java service. All tenants share one 256-bit data key compiled into the configuration; the IV is a fixed 16-byte constant, and PKCS#7 padding is used. During a tenant audit, the customer notices that two backups of the same database taken a week apart begin with identical 4 KB ciphertext blocks. A penetration tester also finds that the restore API returns three distinguishable errors: 'invalid padding,' 'empty plaintext,' and 'decryption failed.' She claims she can recover one plaintext block per 4,096 requests through this endpoint. The provider has 2 PB of backups, a 90-day remediation window, and no ability to re-encrypt everything at once. Restores must remain available throughout. What should the team do?
1. Identify the cryptographic design flaws and explain how the tester's padding-oracle attack recovers plaintext without the key.
Read the worked answer
Flaws exposed by the symptoms
- A fixed IV makes CBC encryption deterministic: equal plaintext blocks produce equal ciphertext blocks. That explains identical 4 KB prefixes and lets an attacker compare tenants.
- A single global key destroys tenant isolation and means one key compromise decrypts every backup.
- There is no MAC, so the ciphertext is malleable. The API leaks whether padding is valid, which is a classic padding oracle.
How the attack works
CBC decryption is P_i = D(C_i) XOR C_{i-1}. To recover the last block, the attacker flips bytes in C_{i-1} and submits C_i. The API's distinct error tells her when the resulting padding is valid, usually 0x01. By trying 256 values for each byte position and observing the error, she learns D(C_i) and therefore P_i. 16 positions x 256 guesses = 4,096 requests per block, matching her claim. She never needs the key.
Why it is serious here
The restore endpoint is authenticated but likely available to support staff, and 2 PB of backups give an attacker many chosen ciphertexts. Identical blocks also permit cut-and-paste splicing between backups. Neither the fixed IV nor the shared key is fixed by rotating the key alone; the API's error behavior must change.
2. Recommend a target architecture and a 90-day migration sequence that avoids re-encrypting all 2 PB at once while preserving restore availability.
Read the worked answer
Target state
Use AES-256-GCM or encrypt-then-MAC with a per-tenant data-encryption key (DEK), wrapped by a KMS/HSM-held key-encryption key (KEK). Store the wrapped DEK and a random 96-bit nonce with each object; never reuse a nonce with a DEK. Separate keys by tenant and by purpose, and record key versions so old objects remain decryptable.
90-day sequence
- Days 1-10: put the restore API behind a uniform error response and rate limiting; move the global key into the KMS/HSM; create per-tenant DEKs for new writes.
- Days 11-30: switch new backups to GCM with envelope encryption; keep a dual-read path that detects the format version.
- Days 31-75: lazily re-encrypt on restore and on rewrite; run a background job prioritized by tenant sensitivity and legal hold, not by tape order. Re-encrypting 2 PB in 90 days may be impossible, so the plan must explicitly leave cold data under compensating controls.
- Days 76-90: verify restore tests, remove the old shared key from application config, and document residual risk for unread cold backups.
Do not claim completion by re-encrypting everything. The defensible outcome is no new CBC writes, no shared key in use, and a measured, auditable backlog.
3. What immediate compensating controls should be applied to the restore API and key storage while migration proceeds?
Read the worked answer
Restore API
- Return one generic failure for every decryption error, with constant-time comparison and no detailed padding message.
- Require strong authentication, per-tenant authorization, and dual approval for bulk restores.
- Rate-limit per account and per tenant, alert on repeated failures, and log ciphertext identifiers, not plaintext.
- Disable unauthenticated or help-desk bulk export paths.
Key storage
- Remove the hard-coded key from source and configuration; inject it from an HSM/KMS with access policy and audit.
- Rotate the global key, but recognize rotation alone does not fix deterministic CBC or the oracle. Re-encryption is still needed.
- Split the root-of-trust duties: key administrators should not be able to run bulk restores without a second approver.
Residual risk
Uniform errors reduce but do not eliminate timing oracles. Rate limiting raises cost but 4,096 requests is small. The only durable fix is authenticated encryption with per-tenant keys. Until then, treat the backup store as sensitive and monitor for anomalous restore patterns.