Breaking Encrypted Databases: Generic Attacks on Range Queries
summary
Encrypted range queries leak either access patterns or volumes, and those leaks let an attacker reconstruct numeric data. Using a PQ tree algorithm and about n log n random observed queries the attacker orders and exactly recovers every value (100 distinct values ≈ 500 queries). With only volume leakage a graph/clique method identifies elementary ranges and, given about n^2 log n random ranges observed, recovers counts per value up to reflection.
AI-written summary · about
chapters (20)
- 0:00Introduction
- 0:58Research motivation
- 2:42Encrypted database attacks
- 4:33Overview of approaches
- 5:45Threat model and architecture
- 7:13Securing data against risks
- 9:13Client-side encryption
- 10:40Encryption techniques
- 13:41Access pattern and volume
- 15:47Access pattern attacks
- 18:00PQ tree data structure
- 21:20Attack query requirements
- 23:53Volume leakage attacks
- 25:54Elementary volume analysis
- 28:34Reconstruction algorithm
- 32:31Query requirements for volume
- 34:03Practitioner recommendations
- 36:17Leakage mitigation techniques
- 38:01Conclusion
- 39:51Q&A session
related talks
31mPractical Private DB Querying
34mWhy your encrypted Database isn't secure: practical attacks against encrypted OSS databases
23mEncrypted Search Party
41mKeeping Secrets: Emerging Practice in Database Encryption
19mPrefix Siphoning: Exploiting LSM-Tree Range Filters For Information Disclosure
31mFast, highly effective database security using searchable encryption (without the yak shave)
37mFrontiers in Cryptography
26mAll Your Queries Are Belong to Us: The Power of File-Injection Attacks...