Paper 2024/1837

Analyze Your Leakage! Security Analysis of Encryption Schemes for Substring Search

Abstract

Searchable symmetric encryption (SSE) enables queries over symmetrically encrypted databases. To achieve practical efficiency, SSE schemes incur a certain amount of leakage; however, this leads to the possibility of leakage cryptanalysis, i.e., cryptanalytic attacks that exploit the leakage from the target SSE scheme to subvert its data and query privacy guarantees. Leakage cryptanalysis has been widely studied in the context of SSE schemes supporting either keyword queries or range queries, often with devastating consequences. However, little or no attention has been paid to cryptanalysing substring SSE schemes, i.e., SSE schemes supporting arbitrary substring queries over encrypted data. This is despite their relevance to many real-world applications, e.g., in the context of securely querying outsourced genomic databases. In this paper, we present the first leakage cryptanalysis of three prominent substring-SSE schemes due to Chase and Shen (PoPETS '15), Faber et al. (ESORICS '15), and Hahn et al. (SIGMOD 2018). We propose novel, inference-based query reconstruction attacks on each of these schemes that exploit their respective leakage profiles. We implement our attacks and experimentally validate their success rates and efficiency over real-world datasets. Our attacks achieve high query reconstruction rate with practical efficiency, and scale smoothly to large datasets. Notably, our attack success attack rate is the highest against the scheme due to Hahn et al. (SIGMOD 2018), which is the most recent of the three schemes. This demonstrates that, as far as substring SSE is concerned, newer schemes are not necessarily "more secure". To the best of our knowledge, ours are the first and only query reconstruction attacks on (and the first systematic leakage cryptanalysis of) any substring-SSE scheme to date. Query reconstruction against substring SSE schemes is inherently harder to achieve than against traditional SSE schemes for keyword search, as the query space for substring SSE is significantly larger. In fact, while the vast majority of known attacks against SSE schemes for keyword search restrict the query space to the most-frequent keywords, our attacks achieve decent query recovery rates without any such restriction on the queried substrings. Our work carries a wider message for designers of SSE schemes: it is not sufficient to merely identify the leakage profile of any new scheme; rather, it is incumbent on designers to cryptanalyze that leakage profile and show that is not consequential in the face of state-of-the-art attacks. The novel attack techniques in our paper provide a starting point for such analysis for substring SSE schemes.

Note: This (substantially) revised version of the paper additionally proposes new query reconstruction attacks on the substring-SSE schemes due to Faber et al. (ESORICS '15), and Hahn et al. (SIGMOD 2018), while retaining the query reconstruction on the substring-SSE scheme of Chase and Shen (PoPETS '15) from the previous version. The paper also has an expanded discussion section.