The STRESS (Search Text RElevance Score Side-channel) attack can in certain situations expose private data via a logical side channel in the implementations of some full-text search indexes as used by modern multi-tenant cloud services. The STRESS attack allows an attacker to discover whether a term exists in some other tenants' documents or determine the number of documents (belonging to other tenants) that contain a term of interest. We have shown simple experiments that suggest an attacker can leverage the STRESS attack to learn sensitive information such as credit card numbers and social security numbers contained in other tenants' documents, with low false-positive rates. The attacker does not need special privileges -- Any legitimate user of a vulnerable search service could exploit STRESS. See our paper for more details.

Modern multi-tenant search services provide search interfaces to enable users to query one or more terms to obtain an ordered list of matching documents. The documents are typically sorted according to their relevance scores, which are determined using an algorithm called term frequency-inverse document frequency (TF-IDF). We will define this algorithm and the attack below in more detail; the important thing to note is that the TF-IDF score contains information about how many documents contain a particular term.

To improve search efficacy and reduce the cost of maintaining too many indexes, current best practice suggests multi-tenant search system to use shared indexes: each index is computed over many different users’ documents; when a user issues a query, the system first gets all the documents matching the query, and then filters out any documents the user should not have access to.

However, if the search system provides relevance score information in the query responses, the user can then infer if other documents contain a term of interest by observing how relevance scores differ from a baseline value. This DF side channel has been known to exist in theory for more than 10 years but no practical attacks against deployed services have been developed.

Now we will define the basic attack mathematically. Let $D$ denote a document set that has $N$ documents, $d$ be a document in $D$, and $t$ be any term. Term frequency $tf(t,d)$ is the number of times $t$ appears in $d$ and document frequency $df(t, D)$ is the number of documents containing $t$ at least once. Then the inverse document frequency $$idf(t,D) = 1+\text{log}\,\frac{N}{df(t,D)+1}$$. And the TF-IDF score of $d$ can be calculated as: $$ s = tf(t,d) * idf(t,D) $$

For example, If $t$ only appears once in the user's document $d$, the score of $d$ should be $$s_1 = 1*(1+\text{log}\,\frac{N}{1+1}) = 1*(1+\text{log}\,\frac{N}{2}) $$ However, if anther $X$ documents on the index also contains $t$, the score the user actually observed would become $$s_2 = 1*(1+\text{log}\,\frac{N}{X+1})$$ And $s_2 < s_1$. So with the knowledge of $s_1$, the user can conclude that some other documents on the index also contain $t$ if the observed score is less than $s_1$ or even calculate $X$ by solving equations.

We investigate several popular multi-tenant search systems and services, and find the DF side channels exist in Elasticsearch and four hosted elasticsearch services: AWS Elasticsearch, AWS CloudSearch, Searchly, and bonsai. There are many other hosted elasticsearch services that could also have the DF side channels. Besides, the DF side channels also exist in Swiftype and the full-text search engine of MySQL.

In principle, any services or applications built atop those vulnerable systems/services could be vulnerable to the STRESS attack if they are using shared indexes. During our experiments, we found three services which were susceptible to the STRESS attack: Github, Xen.do(mitigated based on feedback from researchers and is not vulnerable to the STRESS attack at this time) and Orchestrate.io (shut down on March 17th, 2017).

We disclosed via email to the three services investigated. Xen.do immediately removed relevance scores from API responses as a preliminary mitigation. Github forwarded the issue to Elastic.co. In their response to our email, Elastic.co suggests several countermeasures:

Method	Pros	Cons
Removing relevance scores in query responses	Makes the STRESS attack harder; Easy to implement	Does not prevent exploitation of the DF side channel. We show in our paper that an attacker could still learn sensitive information via rank-only STRESS attack. See our paper for more details.
Tenant per index	Eliminates DF side channel; Good for small service	May be cost prohibitive for some large deployments
Disable scoring and ranking	Eliminates DF side channel;	Functionality loss
No ranking for sensitive terms	Prevents STRESS from learning sensitive terms	Does not prevent exploitation of the DF side channel; Hard to reliably identify sensitive information

In our paper, we propose two countermeasures that can eliminate DF side channels more efficiently: Public-corpus DF and Blind DF. Our evaluation suggests Public-corpus DF is a better countermeasure in terms of scalability and deployability.

Publication: Side-Channel Attacks on Shared Search Indexes Download

We will not be releasing our proof-of-concept STRESS attack code publicly, but researchers or companies can request it by emailing Liang Wang.

We are academic security researchers from a variety of institutions:

This work was supported in part by NSF grants CNS-1558500, CNS-1330308, CNS-1453132, the Defense Advanced Research Projects Agency (DARPA) and Space and Naval Warfare Systems Center, Pacific (SSC Pacific) under contract No. N66001-15-C-4070, and a generous gift from Microsoft.