  Key-value stores typically leave access control to the systems for which they
act as storage engines. Unfortunately, attackers may circumvent such read
access controls via timing attacks on the key-value store, which use
differences in query response times to glean information about stored data.
  To date, key-value store timing attacks have aimed to disclose stored values
and have exploited external mechanisms that can be disabled for protection. In
this paper, we point out that key disclosure is also a security threat -- and
demonstrate key disclosure timing attacks that exploit mechanisms of the
key-value store itself.
  We target LSM-tree based key-value stores utilizing range filters, which have
been recently proposed to optimize LSM-tree range queries. We analyze the
impact of the range filters SuRF and prefix Bloom filter on LSM-trees through a
security lens, and show that they enable a key disclosure timing attack, which
we call prefix siphoning. Prefix siphoning successfully leverages benign
queries for non-present keys to identify prefixes of actual keys -- and in some
cases, full keys -- in scenarios where brute force searching for keys (via
exhaustive enumeration or random guesses) is infeasible.
