Breaking Encrypted Databases: Generic Attacks on Range Queries
summary
Shows two concrete attacks that recover numeric column values from encrypted databases using only side channels: access pattern leakage is turned into a full ordering with a PQ tree, allowing exact or approximate recovery (roughly O(n log n) random queries to fully resolve n distinct values; ~60 queries to group values within 5%), while elementary volumes are found by building a volume-difference graph and extracting a clique to recover exact counts (requires about O(n^2 log n) random ranges to see all volumes). Mitigations include rounding endpoints, dummy records/queries, or more client-side postprocessing.
AI-written summary · about
chapters (13)
- 0:00Introduction and logistics
- 0:58Motivation for the research
- 2:42Defining side-channel attacks
- 5:09Overview of database security
- 7:13Encryption schemes analysis
- 10:40Advanced encryption challenges
- 13:41Access pattern and volume leak
- 15:53Access pattern attack via trees
- 23:46Volume-based attack methodology
- 32:31Statistical query requirements
- 34:03Mitigation and recommendations
- 38:01Summary and conclusions
- 39:36Questions and answers
related talks
41mKeeping Secrets: Emerging Practice in Database Encryption
34mWhy your encrypted Database isn't secure: practical attacks against encrypted OSS databases
23mEncrypted Search Party
31mPractical Private DB Querying
41mNon-traditional Encryption Problems And Solutions
31mFast, highly effective database security using searchable encryption (without the yak shave)
47mData at Rest Encryption Going Beyond the Basics to Address Modern Attacks
37mFrontiers in Cryptography