Practical Volume-Based Attacks on Encrypted Databases

We start by examining 11 representative applications that enable search queries over a secondary index (e.g., Gmail, Twitter, and Facebook) to identify realistic attacker capabilities that can be leveraged in concert with volume leakage. We find that many of these applications satisfy two key characteristics that enable us to mount efficient volume-based attacks, even if they are built atop a cryptographic backend (such as ORAM or PIR) that plugs traditional sources of leakage, and only leaks the volume of results.

First, we find that many applications inherently allow other users to inject application data into a victim user’s index. This property of applications has also been noted in prior work [2, 31, 30]. In our setting, it allows the attacker to potentially influence the volume of results returned by a query.

However, it is not clear how to leverage file injection alone when the only information available is the number of results. File-injection attacks have been studied in the searchable encryption literature [2, 31, 30], but these attacks rely crucially on the attacker knowing the query access patterns—namely, the set of files matching the keyword. The key idea is that the attacker injects special files $F_{1},\dots,F_{n}$ constructed so that each keyword is contained in a unique subset of files. When the victim queries for a keyword, the attacker learns the exact set of files returned and hence the keyword. In our model, though, the attacker only learns the number of files returned, not the exact set. Ensuring that each keyword has a unique number of files means injecting $|D|$ files, where $D$ is the dictionary space. For the English dictionary ($\mathtt{\sim}$$200K$ words), this attack would only be feasible on a small subset. Moreover, given a set of files, there may be many different keywords that are present in the same number of files, precluding these attacks in our setting.

Instead, our strategy is to leverage a second property we observed in the real applications surveyed, which is key for making an injection attack feasible with only volume leakage: the ability to replay queries issued by a user without further user intervention. While this seems at first glance to be a strong assumption, we find that several applications display this behavior as a built-in feature, ostensibly to hide transient application errors.

As an example, Gmail inbox search fits our setting seamlessly, and satisfies both the aforementioned properties. The user can search for a keyword in their emails, an attacker can inject data by simply sending the user an email with a specific keyword, and the user’s query is automatically replayed by the application when the server’s response is delayed without relying on user intervention. In Section 2.2, we define these abilities formally, demonstrate how they appear more generally in a wide range of applications, and explain why they are hard to avoid.

Given these attacker abilities, we present attack algorithms that are able to reconstruct user queries on secondary indices. Our high-level strategy, described in Section 3, is twofold:

1. 1.

   Inject: the attacker injects $k$ specially crafted files that alter the number of results for a candidate query.

2. 2.

   Replay: the attacker causes the client to automatically replay the query without user intervention.

The process repeats to narrow the search space, without the user’s knowledge. This base attack succeeds with $100\%$ probability in identifying words in the attacker’s dictionary. Specifically, given a dictionary of keywords $D$ that represents the attacker’s domain of interest, the attack recovers a queried keyword in only $O(\log_{k}|D|)$ replays of the query (e.g., $<5$ for the English dictionary).

Subsequently, we build upon our base attack to present three ancillary attacks. The ancillary attacks show that our strategy remains feasible, albeit more expensive or less accurate, even when certain mitigation techniques are employed (Section 5).

• •

  No replay attack: We provide an extension to our base attack that works even when query replay is not possible (Section 3.2). While the detection accuracy decreases in this case due to the mentioned shared cardinality, the attack still succeeds with significant probability on a smaller dictionary.

• •

  Attack with padding: We further demonstrate that our attack remains possible even when padding is used to hide result counts (Section 3.3), through an extension to our base attack that requires more injected data but with proven effectiveness.

• •

  Attack with noise: We finally show an extension of the base attack with noisy data when the attacker does not know the result count precisely (Section 3.4).

In Appendix A, we also discuss extensions to the attack for recovering keywords in conjunctive queries.

Finally, we demonstrate the feasibility of our techniques and attack the real Gmail web client by simulating a server-side adversary (Section 4.5). The characteristics of real applications poses a number of constraints on the attack, e.g., based on the behavior of replays, or the time it takes to inject files into the secondary index. Despite these constraints, we show that our attack completes within a matter of minutes for the Gmail application. We also analyze the theoretical complexity of our attacks, and experimentally evaluate their overheads and accuracy in a variety of settings.

While there are ways to mitigate the attack, the vulnerability from result count leakage is difficult to eradicate from a system completely. Padding to the worst-case count theoretically prevents leakage, but in many applications, this results in unaffordable overheads. Rather than trying to reduce system leakage, we believe that the most effective mitigation is actually on the application side, although these techniques too may be burdensome because they interfere with application-specific functionality (e.g., disallowing users from sending email). In Section 5, we discuss these mitigations, but we note that in general, it is difficult to protect against the attack completely because it relies on very little from the system model, and instead exploits features inherent to the application model.

We consider systems in which an untrusted server (the adversary in our setting) maintains a secondary index in an encrypted database. The index maps a keyword to a list of documents or database rows (referred to as files, henceforth) that the keyword appears in and is stored on the server for query efficiency. Whenever the application proxy or the client queries the index for a keyword, the user receives the corresponding list of files containing the keyword. We assume that the query’s execution reveals no information to the adversary except the number of results.

More formally, we define a database $\mathcal{D}$ as a set of records that associates keywords with the files from a collection $\mathcal{F}$ that the keywords appear in:

A query for word $w$ is a function $q_{w}$ (where $w$ is private) that maps $\mathcal{D}$ to a list of matching files in $\mathcal{F}$:

An implementation of such a database may internally use one layer of indirection, so that the first query returns a list of file pointers, or indices into $\mathcal{F}$, and the subsequent queries are used to fetch the file contents from $\mathcal{F}$.

The adversary’s goal is to identify the keyword $w$ using only the size of the result set $|q_{w}(\mathcal{D})|$.

We assume an application model based on the behavior of actual applications that rely on a secondary index. The model consists of two key assumptions: the ability to inject data into a user’s index and the ability to replay a user query without the involvement of the user. We argue that these two assumptions are in fact often inherent to the application. As evidence, we survey a variety of popular web applications that rely on a secondary index and find that both assumptions hold in 5 out of the 11 surveyed. Finally, we describe how these assumptions together make it difficult to detect our attack.

At a high level, the base attack works by searching on the keyword universe through multiple rounds of user query replay. By recording the result counts between rounds, the attacker can narrow down the keyword search space by a constant factor per round.

The attacker uses file injection to influence the result count between rounds. During each round, the attacker constructs files from the keyword search space and injects the files into the user’s index. The response for each round will then contain some number of injected files. The attacker can use the new result count to determine the number of files injected after the previous round. In this way, the attacker can determine which subset of the search space contains the user’s query.

The setup of the attack is as follows: A user queries $q_{w}$ on a database $\mathcal{D}$, as defined in Section 2. The response is the set of matching file contents, $q_{w}(\mathcal{D})=\{f_{1},\dots,f_{n}\}$. The goal of the attack is to recover $w$, using only $n=|q_{w}(\mathcal{D})|$, the number of files returned.

Algorithm 1 provides pseudocode for the base attack RecoverQuery. In more detail, the attacker first records the user query’s $q_{w}$ and the number of files returned, $n_{0}$. $n_{0}$ is the number of files that already matched to $w$ prior to the attack. This enables the attacker to differentiate user-uploaded files from injected ones.

Next, the attacker proceeds in rounds to reduce the keyword search space. He chooses an initial dictionary $D_{0}$, a set of words that might contain $w$, and a parameter $k$. During each round $j$, the attacker divides $D_{j}$ into $k$ equal partitions. He injects $k$ files into the database and distributes the words among them as follows: If a word appears in the $i$-th partition, he adds the word to exactly $i$ out of the $k$ files. Hence, if a word appears in the $k$-th partition, the attacker adds this word to all $k$ files.

The attacker then replays the user’s query $q_{w}$ on the updated database and records the number of files returned, $n_{j}$. Assuming that the attacker can block updates to the secondary index, the number of files injected since the previous round is then $i^{*}=n_{j}-n_{j-1}$. Thus, $w$ must have been assigned to the $i^{*}$-th partition during round $j$. The attacker repeats this in rounds, each time using the $i^{*}$-th partition as the new dictionary, until $|D|=1$.

The complete overheads for the attack are summarized in Fig. 4. This attack converges in a bounded number of rounds since each round is guaranteed to reduce the dictionary size. Furthermore, for a high enough $k$ and a small enough $D$, the number of rounds, i.e., the number of times the attacker has to replay the user’s query, is quite low. We formalize this in the following claim:

The attacker must also inject a significant number of files. We show that the number of files, along with the file size, measured in number of words, is not too large.

The attack presented can recover a user’s query on a generic secondary index with perfect accuracy, even when the file contents and metadata, except result counts, are hidden. The number of results returned is indeed the only information we assume, and we do not require knowledge of the distribution of the query dictionary.

The base attack relies heavily on the ability to replay the user’s query. Without the ability to replay, it is difficult to recover the query with total accuracy without some knowledge of the distribution of words in the database. This is a fundamental limitation of the attack—since we assume that the attacker cannot read any file metadata other than the total number of results, the attacker cannot differentiate between user-uploaded files and injected files during just a single round of the user’s query.

We now present a version of our attack that does not require the attacker to replay queries. We show that the attacker can guess the user’s query in a single round with some degree of accuracy if he can inject a larger number of files. Moreover, if the universe of possible keywords is smaller in size, then the attacker can identify the query with high probability. For example, consider an attacker who knows that Alice is sick, and wants to identify what disease she has by recovering her queries. The attacker can use the set of common diseases as the dictionary of possible keywords, the size of which is on the order of tens. Note that using this dictionary still does not require knowledge of Alice’s query distribution. In fact, our attack will also permit the attacker to identify that the query of the victim is not in his query set.

The key idea is as follows. Because the attacker has only one round to complete the attack, he must inject enough files before the user sends his query such that the attacker can still recover the query with some accuracy. Although he cannot inject files multiple times as in the base attack, he may still be able to inject a large enough quantity of files so as to filter out the noise from user-uploaded files that match the query. And, as we will see from the analysis, this can actually be done in such a way that multiple queries can be recovered without requiring the attacker to execute the attack repeatedly per query, in contrast to the base attack.

We describe the attack formally in Algorithm 2. First, the attacker initializes the attack using SingleRoundInit. The attacker starts with a dictionary $D$ of candidate words, and chooses a constant $m$. Before the user sends his query $q_{w}$, the attacker injects $m|D|$ files into the database $\mathcal{D}$, such that the $i$-th word in the dictionary appears in $mi$ files. Thus, each word appears a unique number of times and is spaced apart by at least $m$ files.

Then, when the user queries $q_{w}$, the attacker estimates $w$ using SingleRoundRecoverQuery (Algorithm 2). The attacker first reads the result set size $n=|q_{w}(\mathcal{D})|$. If $n<m$, then $w$ is not in the attacker’s dictionary, and no more information can be gained for this particular query. If $n\geq m$, then the attacker guesses $w^{\prime}$, the $i$-th word in the dictionary, where $i=\lfloor\frac{n}{m}\rfloor$. With some probability, the attacker’s guess is correct and $w^{\prime}=w$.

The question, then, is how to choose $m$ such that we maximize the probability that $w^{\prime}=w$. Clearly, the larger $m$ is, the better, since a larger $m$ can filter out more noise from the user’s uploaded files. Given some underlying distributions of word and query frequency, we can write the precise probability of the attack’s success.

Formally, let $Q$ be a probability distribution over the universe of words where $Q(w)$ is the probability that the user will query $q_{w}$. Let $\mathcal{D}_{0}$ be the initial database, before any file injections. Then, $|q_{w}(\mathcal{D}_{0})|$ equals the number of user-uploaded files that would have been returned for $w$.

This claim implies that if a large enough $m$ is chosen, then the attacker will be able to perfectly recover all user queries. For instance, if $m$ is greater than $\max_{w}{|q_{w}(\mathcal{D}_{0})|}$, then the probability of an incorrect guess is 0. Therefore, the better the attacker can estimate the distribution $|q_{w}(\mathcal{D}_{0})|$ and $Q$, the more he can increase his probability of recovering the user’s query correctly. Otherwise, he will have to guess a large enough $m$ to ensure accurate query recovery, at the cost of more file injection.

The query’s success rate is also dependent on the dictionary of words chosen by the attacker. If $Q(w)=0$ for all $w\in D$, for example, the attacker will not be able to output a correct guess. Ideally, the attacker would insert the entire universe of words, but this is infeasible since the total number of words injected is given by: $m+2m+\dots+|D|m=O(m|D|^{2})$. However, even if the attacker can only afford to probe a small dictionary, he can still increase his chance of success if he has some knowledge of $Q$; he can then choose to probe words that the user is more likely to query.

There are two key advantages of this approach over the base scheme presented in Section 3.1. First, the initial round of file injections can be reused to recover multiple user queries over a long period of time. As long as the attacker chooses a large enough $m$, the noise due to files that may be added by the user later on can still be filtered out. The attacker can launch a long-running attack in which he continuously probes for the same dictionary of words by gradually increasing $m$ to match the rate at which real files are added. Then, at any point in the future when the user queries for a word in the dictionary, the attacker will be able to discover the word.

The second advantage is that this variation of the attack is mostly passive, in that the attacker actively injects files once and then passively reads file responses for the remaining duration. This is in contrast to the base attack, in which the attacker must actively inject new files with every query response. Thus, although the file injection overhead becomes higher and the success rate is reduced, an attack without the ability to replay a user’s query is still both possible and practical.

An obvious countermeasure to the attack outlined in Section 3.1 is to use a cryptographic scheme that pads query responses to hide the number of files returned. Note that padding might not always be possible because it potentially adds nontrivial bandwidth overheads and hence increases costs for a system operator.

Padding interferes with the attacker’s ability to determine the number of files returned for a query. However, as we show in this section, the attacker can still learn some information. The common issue in all of the following schemes is that the attacker retains the ability to inject files. Thus, even if the attacker can no longer determine a user’s query, he can still inflate the bandwidth overhead by injecting large enough files.

The simplest scheme would be to always pad to the worst case. Formally, the largest possible response is $max_{w}|q_{w}(\mathcal{D})|$. The scheme must then pad every result set to this count, which is potentially very expensive. The attacker can aggravate the problem by simply injecting a large number of files that all contain the same word, forcing the system to send that many files in response to all requests.

A more practical scheme is to use tiered padding. In this case, each response is padded to one of several predefined sizes, or tiers. For example, one could choose to use base-2 exponential padding, so that each response size is rounded up to the nearest power of 2.

Tiered padding can deter the base attack, but comes at the cost of expensive bandwidth overheads. Here, we analyze the number of files that the attacker must inject and the bandwidth overhead for the server. We use exponential tiered padding for the analysis, but a similar analysis applies to any padding scheme. Recent works [51, 52] propose more efficient padding schemes that add probabilistic noise to the result set size; in Section 3.4 we describe an extension of our attack that applies to such scenarios.

Recall that on every round, the attacker records $n_{j-1}=|q_{w}(\mathcal{D})|$, the number of files returned to the user’s query at the end of the previous round. Under this padding scheme, $n_{j-1}=2^{p}$ for some $p$. The actual number of files is then in the range $(\frac{n_{j-1}}{2},n_{j}]$. In the next round, the attacker must inject enough files to ensure that the query will be padded to the next highest tier, so that there is a measurable difference in the query’s number of results. This is at least $\frac{n_{j-1}}{2}$ files.

In a direct translation of the base attack, the attacker has to inject $k$ partitions of the dictionary in such a way that he can differentiate between the partitions. Then, the attacker would have to inject $\frac{n_{j-1}}{2}$ files for the first partition, $\frac{n_{j-1}}{2}\times 2$ for the second, and so on. This leads to ${n_{j-1}}{2^{k-2}}$ files injected for a single round. Even worse, $n_{j}=n_{j-1}2^{k-2}$, so the next round will also require an exponentially larger number of files to be injected.

The number of files injected can be reduced by injecting the partitions one at a time, with $\frac{n_{j-1}}{2}$ files per partition. After all of the files for a partition are injected, the attacker can replay the query to measure if the user’s query matched that partition. This way, the attacker can inject $\frac{kn_{j-1}}{2}$ files per round. However, this requires increasing the number of query replays by a factor of $k$, since each round now requires $k$ replays instead of one.

While the overhead for the attacker is significant, this analysis does not take into account the substantial bandwidth costs for the client. Every query may require nearly doubling the query’s number of results. To answer the attacker’s replayed queries, the cryptographic scheme needs to pad the files with approximately as much data as the attacker must inject, to hide the number of files returned. This can be prohibitively expensive for a database system.

In the PIR setting, an even more effective version of our attack is possible: the server has the ability to also delete data in addition to injecting it. So the attacker can toggle the number of results for a keyword over multiple padding sizes, instead of just increasing it.

In Section 3.1, we assume that the attacker can identify precise result counts. That is, we assume that the observed number of results is exactly equal to $|q_{w}(\mathcal{D})|$, to the number of files that matched $w$ in the database $\mathcal{D}$. This allows the attacker to precisely measure the change in query result sets between rounds due to injected files.

However, the change measured may not exactly equal the number of injected files. For example, if the cryptographic scheme adds some noise to the result sets, then the attacker cannot precisely identify the change in result counts due to file injection. Another example appears in some searchable encryption schemes, where the results are batched together in blocks (say $m$ results per block), or when using ORAMs [53] that attempt to hide the number of results within an ORAM Path. For the first, the attacker observes the number of blocks so it can estimate the actual number of results within an error of $\mathtt{\sim}$$m$. For the second, we discuss in Section 6 that such ORAMs still reveal an approximate number of results in some realistic settings.

In this section, we show that our attack still has a significant chance of success even if there is some noise in the volume measurements. Formally, if the attacker expects a noise of at most $s$ files in some time interval, this means that for each word $w$, the database system can add up to $s$ elements to the database $\mathcal{D}$. Each of these elements is of the form $(w,f)$, where $f$ is a dummy file. If a user queries $q_{w}$ on every interval, he can expect an increase of at most $s$ files with each new query.

Similar to ideas presented in the above scenarios, the attacker can still recover a query $q_{w}$ if he can inject more files to filter out noise in the database. In particular, with an expected noise of $s$ in between rounds of an attack, he can repeat a word in the $i$-th partition $si$ times instead of just $i$. If the user’s query word $w$ falls in partition $i$ during round $j$, then the number of results observed will be $n_{j}\leq n_{j-1}+si+s$. Then, to determine the partition that the user’s query belonged in, he can compute $\lfloor\frac{n_{j}-n_{j-1}}{s}\rfloor=i$.

Thus, assuming that the attacker can correctly guess the maximum noise that will be added during any round, the attacker can still recover the user’s query with perfect accuracy. The attacker can estimate $s$ with some knowledge of the application. For instance, he can record the rate of incoming email for an average user, for example. Furthermore, if the attacker underestimates $s$ and guesses a wrong partition, he will quickly discover his error since the query’s result set size is unlikely to match any partition during the following round.

The overhead to overcome noise is quite low; a factor of $s$ to the number of files and words injected. Thus, even if the attacker is unable to perfectly measure the number of results and/or block network traffic, he can still recover the user’s query with near-perfect accuracy.

Our attacks so far focus on queries with single keywords. However, applications may allow clients to issue queries with multiple keywords as well. One way in which applications may handle such queries is by expressing the queries as a conjunction of the different keywords. For such cases, we describe an extension to our attack in Appendix A. We present two attacks for conjunctive queries—the first optimizes the number of required replays while the second reduces the number of files injected.

Applications may alternatively express multi-keyword queries as disjunctions of the different keywords instead. We leave attacks on disjunctive queries to future work.

In all experiments, we use the entire corpus of emails from the Enron email dataset [54] as the queried documents, consisting of $\mathtt{\sim}$500K emails belonging to 151 users and $\mathtt{\sim}$2.5GB in size. We extracted keywords from this dataset by first stemming the words [55], and then removing 675 stopwords. We next filtered out any words that contained non-alphabetic characters, or were $\geq 20$ or $\leq 3$ characters long. This gave us a total of $\mathtt{\sim}$259K keywords. In our experiments, we only used the top $\mathtt{\sim}$123K keywords (i.e., those that appeared in $>3$ documents) in order to remove noise from the dataset.

Since an attacker’s dictionary may contain words that do not exist in the queried documents, we supplemented the Enron keywords with a corpus of English words [56]. Preprocessing the English words in a similar manner yielded a total of $\mathtt{\sim}$257K keywords. The union of both datasets resulted in a universe of $\mathtt{\sim}$342K keywords.

Assuming that the queried word is in the initial dictionary chosen by the attacker, the base attack achieves perfect query recovery, with strict bounds on the overheads necessary in number of query replays and data injected (as described in Fig. 4). Our simulation of the attack in Figs. 7 and 7 confirms the theoretical guarantees.

In this experiment, we build the attacker’s dictionary $D$ by randomly sampling keywords from the keyword universe. We pick the keyword queried by the user at random from $D$ in order to stress test the effort required by the attacker—a keyword not in the $D$ would be trivially detected at the end of a single round without requiring further replays. We then report the number of rounds required to guess the keyword with $100\%$ accuracy for different choices of $k$ in Fig. 7, and the total number of files injected across rounds in Fig. 7. Recall from Section 3.1 that any instance of the attack converges after exactly $\left\lceil\log_{k}{|D|}\right\rceil$ replays and $k\left\lceil\log_{k}{|D|}\right\rceil$ files injected, where $k$ is an integer chosen by the attacker. Thus, with a dictionary of fixed size $|D|$, the parameter $k$ represents a tradeoff between the number of query replays required vs. the number of file injections required. The attacker’s choice of $k$ then depends on the attacker’s ability to replay the query and the rate at which files can be injected for the target application.

We explore this tradeoff with fixed-size dictionaries in Fig. 7, which demonstrates how the average number of bytes injected per round increases with $k$ (while the number of rounds decreases). In the worst case where the dictionary comprises the entire keyword universe and $k=24$, the bytes injected per round is still less than 10MB, demonstrating the feasibility of the attack. We also show the maximum number of bytes injected across any round in Fig. 7, equivalent to the number of bytes injected during the first round. The number of bytes that the attacker can inject during a single round must be at least as large as this number. We find that even in the worst case, this is approximately 50MB.

In the single-round variation of the attack, we sacrifice some accuracy but do not require the ability to replay the user’s query. This variation of the attack is also stronger in that it can be used to identify multiple queries over a long period of time, whereas the base attack must be instantiated once for every query of interest. Also, this variation is a mostly passive attack, since the bulk of the attack is spent reading query responses, rather than also injecting files in an online fashion.

We evaluate this attack by measuring its accuracy while varying the parameter $m$ chosen by the attacker. Recall that $m$ represents the tradeoff between the file injection overhead and the number of files injected (Section 3.2). In this experiment, we only query keywords that exist in the Enron dataset, since keywords that do not exist in the dataset will always be accurately detected for any choice of $m$.

For each value of $m$, we measure the attack’s accuracy in two scenarios: (i) when the queried keyword is in the attacker’s dictionary and the attacker guesses the keyword; and (ii) the keyword is not in the dictionary, and the attacker determines that the keyword is not of interest. In each scenario, we first fix the dictionary, and then inject a single round of files at the beginning of the simulation for a chosen value of $m$. We then query 1000 randomly selected keywords and measure the percentage of accurate guesses. Fig. 10 plots the accuracy of guesses as $m$ increases, averaged over different dictionary sizes.

Predictably, the accuracy of the attack improves with $m$, while the number of file injections required also increases. For $m=5$, we need only inject $5|D|$ files, but achieve an accuracy rate of only $\mathtt{\sim}$$14\%$ for words that belong to the attacker’s dictionary. For $m=1000$, we achieve an accuracy of $\mathtt{\sim}$$96\%$, but must inject $1000|D|$ files. In practice, a lower value of $m$ might not only suffice but also be feasible: for $m=20$ we achieve an accuracy of $\mathtt{\sim}$$64\%$, while the number of bytes injected for a dictionary of size 10K is $\mathtt{\sim}$$7$GB.

We assess the feasibility of the attack when the server pads query responses to one of several predefined sizes. In such cases, though it is still possible for the attacker to guess the queried keyword, it also requires greater effort. As described in Section 3.3, the attacker can choose to either minimize the number of rounds, or minimize the number of files injected. In this experiment, we evaluate the latter strategy. Specifically, we measure the overhead incurred by the attacker when the server pads responses to powers of 2 and 10, and compare it with a baseline where the responses are unpadded.

We build the attacker’s dictionary by randomly selecting keywords from the Enron dataset, and then measure the overhead for each keyword in the dictionary. We use this setup to stress the number of files the attacker will have to inject, since responses for non-existent keywords will get padded to a size of 1 by the server.

Fig. 10 illustrates the attacker’s overhead in terms of the total number of bytes injected with varying dictionary sizes. When responses are padded to a power of 2, the attacker has to inject a feasible $\mathtt{\sim}$$35$MB on average to mount the attack, with a large dictionary size of 10K keywords. Though the overhead increases dramatically when the responses are padded to a power of 10, a small dictionary size of 100 keywords still requires only $\mathtt{\sim}$45MB of injected data to pinpoint the keyword.

So far, we have experimentally validated the theoretical performance of our attacks across various parameter choices. We now demonstrate the practical feasibility of our attack in real-world applications by attacking Gmail’s inbox search feature. We attack the real Gmail web client, assuming that the server maintains a secondary index over the user’s (encrypted) emails and only learns the volume of query results. Note that this is not currently the case, and Gmail’s servers have access to far more leakage than simply the volume of results. However, our aim is to demonstrate that even if Gmail (and other real-world applications) were to deploy sophisticated privacy-preserving mechanisms at the server such as ORAM or PIR, the volume of query results remains a potent source of leakage. Therefore, in this experiment, we attack the real Gmail web client by simulating such a server-side adversary using a man-in-the-middle proxy; we simulate the adversary because we don’t have actual control over Gmail servers.

We first show that the attacker can indeed meet the two key requirements of file injection and automatic query replay. Subsequently, we perform an exhaustive experiment across a wide range of dictionary sizes (10 to 100K) to determine the minimum amount of time required to mount a successful attack on Gmail. The parameters of our attack are governed by the following constraints: (i) the periodicity of replays in the Gmail client; (ii) the time it takes to inject files into a user’s inbox; and (iii) the pagination limit in Gmail (which upper bounds the total number of injections). We find that for a small dictionary of size 10, a successful attack can be mounted within 1 minute from start to end; for a large dictionary with 100K words, an attack completes successfully in around 7 minutes (see Fig. 11).

We now describe our methodology in more detail.