SSE Is Not As Secure As It Looks

Abstract

In a world where more data gets uploaded to the cloud, it is essential that the data gets stored securely. For users to keep search functionality, searchable symmetric encryption has been developed. SSE works by a user sending a token representing a keyword (or a range), after which the server returns the documents that match the keyword (or values in the queried range). These observed documents are called the access pattern. A number of attacks that work on range SSE schemes have been developed. Yet, most of these attacks work on density or query assumptions that hinder their performance if these
assumptions are false. Furthermore, a number of these attacks use auxiliary information. Yet none of them uses known search tokens.

We, thus, propose a novel approach that uses a PQ-Tree to get the order of the observed documents. It uses the known pairs to assign possibilities for these documents and returns a list of options for each observed token and estimated values for each document. The basic attack guarantees that the correct query is always available by assigning document values based on the known tokens. A refined attack was made that assigns more known tokens by adding the best matches based on confidence score. This refinement allows for more exact token and query matches. Both of these attacks were extended using partial or similar documents from which document volume or rank information could be gathered
to further increase the attack performance in cases where such data is available. We evaluate our attacks against current state-of-the-art and outperform those regarding document and query recovery on all tested datasets. Lastly, we use two countermeasures and see that all attacks are impacted but that our attack still outperforms most.