Laura Blackstone (Brown University), Seny Kamara (Brown University), Tarik Moataz (Brown University)

Encrypted search algorithms (ESA) are cryptographic algorithms that support search over encrypted data. ESAs can be designed with various primitives including searchable/structured symmetric encryption (SSE/STE) and oblivious RAM (ORAM). Leakage abuse attacks attempt to recover client queries using knowledge of the client's data. An important parameter for any leakage-abuse attack is its known-data rate; that is, the fraction of client data that must be known to the adversary.

In this work, we revisit leakage abuse attacks in several ways. We first highlight the practical limitations and assumptions underlying the often-cited IKK (Islam et al. NDSS '12) and Count (Cash et al., CCS '15) attacks. We then design four new leakage-abuse attacks that rely on much weaker assumptions. Three of these attacks are volumetric in the sense that they only exploit leakage related to document sizes. In particular, this means that they work not only on SSE/STE-based ESAs but also against ORAM-based solutions. We also introduce two volumetric injection attack which use adversarial file additions to recover queries even from ORAM-based solutions. As far as we know, these are the first attacks of their kind.

We evaluated all our attacks empirically and considered many experimental settings including different data collections, query selectivities, known-data rates, query space size and composition. From our experiments, we observed that the only setting that resulted in reasonable recovery rates under practical assumptions was the case of high-selectivity queries with a leakage profile that includes the response identity pattern (i.e., the identifiers of the matching documents) and the volume pattern (i.e., the size of the matching documents). All other attack scenarios either failed or relied on unrealistic assumptions (e.g., very high known-data rates). For this specific setting, we propose several suggestions and countermeasures including the use of schemes like PBS (Kamara et al, CRYPTO '18), VLH/AVLH (Kamara and Moataz, Eurocrypt '19), or the use of padding techniques like the ones recently proposed by Bost and Fouque (Bost and Fouque, IACR ePrint 2017/1060).

View More Papers

Poseidon: Mitigating Volumetric DDoS Attacks with Programmable Switches

Menghao Zhang (Tsinghua University), Guanyu Li (Tsinghua University), Shicheng Wang (Tsinghua University), Chang Liu (Tsinghua University), Ang Chen (Rice University), Hongxin Hu (Clemson University), Guofei Gu (Texas A&M University), Qi Li (Tsinghua University), Mingwei Xu (Tsinghua University), Jianping Wu (Tsinghua University)

Read More

Finding Safety in Numbers with Secure Allegation Escrows

Venkat Arun (Massachusetts Institute of Technology), Aniket Kate (Purdue University), Deepak Garg (Max Planck Institute for Software Systems), Peter Druschel (Max Planck Institute for Software Systems), Bobby Bhattacharjee (University of Maryland)

Read More

Not All Coverage Measurements Are Equal: Fuzzing by Coverage...

Yanhao Wang (Institute of Software, Chinese Academy of Sciences), Xiangkun Jia (Pennsylvania State University), Yuwei Liu (Institute of Software, Chinese Academy of Sciences), Kyle Zeng (Arizona State University), Tiffany Bao (Arizona State University), Dinghao Wu (Pennsylvania State University), Purui Su (Institute of Software, Chinese Academy of Sciences)

Read More

On Using Application-Layer Middlebox Protocols for Peeking Behind NAT...

Teemu Rytilahti (Ruhr University Bochum), Thorsten Holz (Ruhr University Bochum)

Read More