Paper 2019/1224

Practical Volume-Based Attacks on Encrypted Databases

Stephanie Wang and Rishabh Poddar and Jianan Lu and Raluca Ada Popa

Abstract

In recent years, there has been an increased interest towards strong security primitives, such as oblivious protocols, that hide which data records a query touches in a database, and reveal only the volume of results. However, recent work has shown that volume is a significant leakage that can enable reconstructing the entire database. Yet, such attacks make two limiting assumptions: they require a large number of queries to be issued by the user, and assume certain distributions on the queries (e.g., uniformly random), which are not realistic in practice. In this work, we present new attacks for recovering the content of individual user queries, assuming no leakage from the system except the number of results, and avoiding the limiting assumptions above. Unlike prior attacks, our attacks require only a {\em single} query to be issued by the user for recovering the keyword. Furthermore, our attacks make no assumptions about the distribution of issued queries or the underlying data. Our key insight is to exploit the real behavior of specific applications. We start by surveying 11 applications to identify two key characteristics that can be exploited by attackers---(i) file injection, and (ii) automatic query replay. We present attacks that leverage these two properties in concert with volume leakage, independent of the details of any encrypted database system. Subsequently, we perform an end-to-end attack on the Gmail web client by simulating a server-side adversary. Our attack on Gmail completes within a matter of minutes, demonstrating the feasibility of our techniques. We also present three ancillary attacks for situations when certain mitigation strategies are employed.