Prefix Siphoning: Exploiting LSM-Tree Range Filters For Information Disclosure
summary
Shows a concrete timing attack called prefix siphoning that abuses LSM-tree range filters (demonstrated on SuRF and the prefix Bloom filter) to recover key prefixes and sometimes full keys. Implements the attack in RocksDB over 50 million random 60-bit keys, uses ~10 million probe queries in step zero and step one, then identifies prefixes and brute‑forces 24‑bit suffixes in parallel — converging to under 10 million queries per extracted key and outperforming brute force by ~4 orders of magnitude. Presents practical mitigations and their performance or complexity tradeoffs.
AI-written summary · about
chapters (9)
- 0:00Research introduction
- 2:24Revealing keys as threat
- 4:53Threat model and LSM basics
- 7:00Range filter vulnerabilities
- 9:08Prefix siphoning attack
- 11:17Attack on SURF demo
- 14:53RocksDB attack demo
- 17:26Mitigations and limits
- 18:10Conclusion and future work
related talks
51mTiming Attacks Have Never Been So Practical: Advanced Cross-Site Search Attacks
44mBreaking Encrypted Databases: Generic Attacks on Range Queries
15mDUPEFS: Leaking Data Over the Network With Filesystem Deduplication Side Channels
31mPractical Private DB Querying
34mLeapFrog: The Rowhammer Instruction Skip Attack
27mTranslation Leak-aside Buffer: Defeating Cache Side-channel Protections
45mAbusing Performance Optimization Weaknesses to Bypass ASLR
15mUnsafe LLM-Based Search: Quantitative Analysis and Mitigation of Safety...