Revisit Attacks on Searchable Symmetric Encryption

Abstract

Searchable Symmetric Encryption (SSE) schemes provide secure search over encrypted databases while allowing admitted information leakages. Generally, the leakages can be categorized into access, search, and volume pattern. In most existing Searchable Encryption (SE) schemes, these leakages are caused by practical designs but are considered an acceptable price to achieve high search efficiency. Many attacks on SSE schemes have shown that such leakages could be easily exploited to retrieve the underlying keywords for search queries. Each attack abuses a different leakage pattern and uses different techniques to achieve high query recovery accuracy. An attacker could be passive or active, where an active attacker can inject files in an SSE scheme, while a passive attacker only observes the queried data. Some passive attacks use the number of files returned by a query to create a match with a candidate keyword. Others use the co-occurrence of multiple keywords in the files to match a query with the same occurrence. We continue this research and design a new Volume and Access Pattern Leakage-abuse Attack (VAL-Attack) that exploits both the access and volume patterns. Our proposed attack only leverages leaked documents and the keywords present in those documents as auxiliary knowledge and can effectively retrieve document and keyword matches from leaked data. Furthermore, the recovery performs with great accuracy and without false positives. We compare VALAttack with two recent well-defined attacks on several real-world datasets to highlight the effectiveness of our attack and present the performance under popular countermeasures.