Recent years have seen an increased interest towards strong security primitives for encrypted databases (such as oblivious protocols), that hide the access patterns of query execution, and reveal only the volume of results. However, recent work has shown that even volume leakage can enable the reconstruction of entire columns in the database. Yet, existing attacks rely on a set of assumptions that are unrealistic in practice: for example, they (i) require a large number of queries to be issued by the user, or (ii) assume certain distributions on the queries or underlying data (e.g., that the queries are distributed uniformly at random, or that the database does not contain missing values). 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 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. Instead, our key insight is to exploit the behavior of real-world 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 attack on the real 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.
翻译:近些年来,人们越来越关注加密数据库(如隐蔽的规程)的强大安全原始材料,这些安全原始材料隐藏了查询执行的存取模式,并只揭示了结果的数量。然而,最近的工作表明,即使是数量泄漏也能够重建数据库的整个栏目。然而,现有的攻击依赖一系列不切实际的假设:例如,它们(一) 要求用户发布大量查询,或(二) 对查询或基本数据的某些分发作出某些假设(例如,查询均以随机方式统一分发,或数据库不包含缺失的值 ) 。在这项工作中,我们为恢复个别用户查询的内容提出了新的攻击,假设系统除了结果的数量和避免上述限制假设之外没有渗漏。与以前的攻击不同,我们的攻击只要求用户为恢复关键词发布单一的查询。此外,我们的攻击没有对发出的查询或基本数据的分发作出任何假设。相反,我们的关键洞察力是利用真实世界应用程序的行为。我们开始调查11个应用程序,以恢复个别用户查询的内容,假设系统内有两种关键特性,即自动数据库(一) 利用这些数据库的升级数据。