High Recovery with Fewer Injections: Practical Binary Volumetric Injection Attacks against Dynamic Searchable Encryption

The operations of a dynamic SSE scheme naturally yield multiple leakage patterns. We denote an adaptive semantic secure SSE scheme as $\mathbf{SSE}=(Setup:\lambda\rightarrow\mathbf{D},\ Query:\mathbf{D\times Q\rightarrow RF},\ Update:\mathbf{D\times U\rightarrow\delta})$, in which $\mathbf{D}$ is the encrypted database, $\mathbf{RF}$ is the set of files matching the queries $\mathbf{Q}$, $\mathbf{U}$ is the set of updates containing $op$ and $(w,id)$, and $\delta$ represents the state of the client after the update from $\mathbf{U}$. We define two types of patterns:
$\bullet$ the $access\ pattern$ is the function family where $\mathbf{ap}:\mathbf{D}\times\mathbf{Q}^{t}\rightarrow\mathbf{R}^{t}$ such that for a sequence of queries $\mathbf{Q}=(q_{1},\ ...,\ q_{t})$, it outputs the response file identifiers $\mathbf{R}=(ids(q_{1}),\ ...,\ ids(q_{t}))$.
$\bullet$ the $access\ injection\ pattern$ is similar to the $access\ pattern$, except that we need to recognize the injected file identifiers such that $\mathbf{aip}:\mathbf{D}\times\mathbf{Q}^{t}\rightarrow\mathbf{IR}^{t}$, where $\mathbf{IR}=(iids(q_{1}),\ ...,\ iids(q_{t}))$ represents the injected file identifiers for the queries.

We note that most of LAA schemes [25, 7, 35] rely on the access pattern; while ZKP [52] exploits the access injection pattern for injection attack. We also formally define the search and volume patterns used in our attacks.
$\bullet$ the $search\ pattern$ is the function family that $\mathbf{sp}:{\mathbf{D}}\times\mathbf{Q}^{t}\rightarrow\mathbf{M}^{t\times t}$ where for a sequence of queries $\mathbf{Q}=(q_{1},\ ...,\ q_{t})$, it outputs a binary $t\times{t}$ matrix $\mathbf{M}$ such that $\mathbf{M}[i,\ j]=1$ if $q_{i}=q_{j}$ and otherwise, $\mathbf{M}[i,\ j]=0$.
$\bullet$ the $response$ $length$ $pattern$ is the function family that $\mathbf{rlp}:\mathbf{D}\times\mathbf{Q}^{t}\rightarrow\mathbf{RL}^{t}$ where, for a sequence of queries $\mathbf{Q}$, it outputs the number of the response files $\mathbf{RL}=(\mathbf{\#D}(q_{1}),\ ...,\mathbf{\#D}(q_{t}))$.
$\bullet$ the $response$ $size$ $pattern$ is the function family that $\mathbf{rsp}:\mathbf{D}\times\mathbf{Q}^{t}\rightarrow\mathbf{RS}^{t}$ where, for a sequence of queries $\mathbf{Q}$, it outputs the size of the response files $RS=(\sum_{f\in{D(q_{1})}}|f|_{w},...,\sum_{f\in{D(q_{t})}}|f|_{w})$.

To capture a general injection attack model, we enable the adversary to actively generate and inject files. We regard the adversary as an honest-but-curious server who follows the protocols but can still inject files to the client database³³3Or one may regard the adversary as an active observer who can generate injected files for the client and observe the query response.. We divide the whole attack process into three stages (see Figure 1).
(1) In the baseline phase, the adversary observes the client’s query leakage $\mathbf{LP}^{*}$ as pre-knowledge (provided the client sends queries to the server). This step is of importance for injection attacks (except for ZKP [52] and single-round attack [39]). This is because the adversary should obtain the correlation between the keywords and response files from the baseline’s observations. The idea is to compare the volume difference between the response results before (baseline) and after injection for query recovery.
(2) In the injection, the adversary should carefully generate files $\mathbf{F}$ by using its known keywords $\mathbf{W}$ and the information obtained from the baseline. Next, the client encrypts the files and uploads them to the server.
(3) During the recovery phase, the adversary obtains the target queries’ leakages $\mathbf{LP}$ and recovers them by combining all the known information, namely $\mathbf{W}$, $\mathbf{LP}^{*}$, $\mathbf{F}$, and $\mathbf{LP}$.

We let $\mathbf{Q}$ denote the target query set observed by the adversary and $\mathbf{Q}_{r}$ denote the query recovery results. We refer to the recovery rate as ${Rer}:\mathbf{\#{CorrectPred(Q_{r})}}/\#\mathbf{Q}$. We denote the number of injected files as ${ILen}:\#\mathbf{F}$ and the word count of the injected files as ${ISize}:|\mathbf{F}|_{w}$, where $\mathbf{F}$ is the set of injected files. The goal of injection attacks is to obtain a high Rer and make ILen and ISize as “small” as possible by only exploiting the known keyword universe and pre-injection leakage.

The BVA (see Algorithm 1) works as follows. In the baseline phase, the adversary observes and records the response sizes of unknown queries. During the injection phase, it generates and injects files according to the injection parameter $\gamma$ in a $binary$ way. In the last phase, the adversary observes an additional sequence of the client’s queries $\boldsymbol{{Q}}=({q}_{1},...,{q}_{m})$ as the attack targets with response size $\boldsymbol{RS}=(rs_{1},...,rs_{m})$. It aims to recover all the queries in $\boldsymbol{{Q}}$.

Note an example (see Figure 12, Appendix D) shows the differences between the decoding attack and ours in terms of injection length and size.

Let $P$ be the probability distribution over the keyword universe and $P(w_{u})$ be the probability that the client will query the keyword $w_{u}$. We use $\widetilde{rs}_{w_{u}}$ to represent the response size of $w_{u}$ observed in the $baseline$ phase. We formalize the probability of incorrect recovery as follows.

We see that only the third case can cause an incorrect recovery, which implies that the recovery rate depends on the selection of $\gamma$. A well-selected $\gamma$ can greatly reduce the occurrence of the third case and make the adversary achieve the same recovery rate as the decoding attack. Even in the worst case (i.e., $\gamma=\#\mathbf{W}/2$), the recovery rate can still maintain $>70\%$ in Enron and Lucene. We further state that the binary injection approach can restrict the injection length to $\log\mathbf{\#\mathbf{W}}$, which outperforms prior schemes [3, 39]. Note more details will be given in the experiments (see Section 4).

The attack can recover multiple queries with a high recovery rate (e.g., averagely $80\%$ in Enron) and a small injection volume by leveraging the rsp, even the file contents and co-occurrences of keywords are hidden. It does not require any knowledge of query and file distribution. The BVA is a more practical VIA compared to prior attacks.

Unlike the decoding attack relying on offset, the BVA adjusts a proper $\gamma$ for different datasets. This could affect the recovery rate and injection size. For example, setting a small $\gamma$ can decrease the injection size (compared with decoding) but could fail to distinguish some queries. To refine the attack performance, we introduce the BVMA, which is fully independent of any offset or $\gamma$. The BVMA is the first injection attack that $combines$ the response length and size patterns (as well as the sp). The combination can filter known candidate keywords precisely with less injection size, so that it enhances the recovery rate. See the BVMA in Algorithm 2.

We also provide a claim and its proof for the injection size.

We see that the BVMA inherits the advantages of the BVA (except the usage of $\gamma$) and further provides an improvement on injection size, for example, the BVMA outperforms the best case’s BVA (i.e., when $\gamma=\#\mathbf{W}/2$, see Figure 5).

Threshold countermeasure (TC) [52] can prevent large-size files (e.g., #word > the threshold $T$) from being injected into the database. The $T$ could be set relatively small in practice to counter injection attacks, without seriously affecting the functionality of dynamic SSE. For example, only $3\%$ of the files in Enron ($\#\mathbf{W}=3,000$) contain more than 500 words. If employing TC with $T=500$, we could skip these $3\%$ of files from indexing. Under this setting, a dynamic SSE can effectively resist prior attacks (e.g., [3, 39] and ours). This is because each injected file must contain a considerably large number of words (e.g., $\geq\#\mathbf{W}/2$ words), in particular, the single-round [39] and decoding [3] attacks force an injected file to contain $\mathcal{O}(m\#\mathbf{W})$ and $\mathcal{O}(\textit{offset}\cdot\#\mathbf{W})$ words.

We design a generic transformation method to “protect” VIAs from TC (see Algorithm 3). The transformation takes the threshold $T$ and the set of large files $Basic\_F$ as input and runs the cutting and refilling, where $Basic\_F$ is the output of a concrete VIA algorithm, e.g., BVA. In Algorithm 3, we cut large files (with #word>$T$) into smaller ones to satisfy the threshold of TC. To eliminate the impact of file cutting on recovery rate, we keep the injection length $\#file_{u}$ or size $|file_{u}|_{w}$ of each keyword $w_{u}\in\mathbf{W}$ consistent before and after Algorithm 3. For example, in the single-round attack [39], for any keyword $w_{u}$, we keep its injection length $\#file_{u}$ unchanged (after cutting) in order to avoid bring any impact to the recovery phase. In the decoding [3] and our attacks, we keep keywords’ injection size consistent (by refilling).

During the cutting phase (lines 3-3), for each $f\in{Basic\_F}$, we extract all keywords $C\_W$ from $f$. We then generate $\lceil\#C\_W/T\rceil$ files for $Cut\_F$ by following 1) the size (word count) of each file is $T$; and 2) each file contains up to $T$ distinct (non-overlapped) keywords from $C\_W$ so that each keyword $w_{u}$’s injection length $\#{file_{u}}$ is 1 (note the number remains the same before and after cutting). We finally have sets of small-size files to bypass TC while maintaining the consistency of the keywords’ injection length.

In the refilling phase (lines 3-3), for each file $c\_f\in{Cut\_F}$, we generate two file sets $Ref\_F_{1}$ and $Ref\_F_{2}$. $Ref\_F_{1}$ is constructed by refilling $|f|_{w}/T-2$ files, in which each file is with size of $T$ and it contains all the keywords in $c\_f$. Next, we generate as few files as possible (for $Ref\_F_{2}$) to accommodate all the keywords in $c\_f$, with each file having a size of $|f|_{w}-(\lceil|f|_{w}/T\rceil-1)\cdot{T}$. We ensure that the injection size of keywords in $c\_f$ is still $|f|_{w}$ after the refilling.

We say that the injection length strongly relies on the word count of each file $f$ and the number of files in ${Basic\_F}$. Our attacks, requiring fewer injected files than others, can naturally provide a practical performance against TC. This is proved by the experiments (see Figure 7). For example, in Enron with $\#\mathbf{W}=3,000$, setting $T=500$, $\gamma=\#\mathbf{W}/2$ for the BVA, and $m=\#\mathbf{W}/2$ for the single-round attack, we see that the lower bounds of the injected files for our attacks are approximately $10^{5}$ and $10^{3}$ which are at least $10^{2}\times$ less than that of the single-round ($10^{7}$) and decoding ($10^{9}$) attacks.

We used Google Trends [22] of 260 weeks trends between October 2016 and October 2021 to simulate the real query trends for Enron and Lucene. We applied the Pageviews, Toolforge [34] containing 75 months of page views from July 2015 to September 2021 to generate monthly query trends for Wikipedia. We assumed that the client performs 1,000 queries weekly for Enron (Lucene) and 5,000 queries monthly for Wikipedia. We regarded the queries generated by the client (within ten weeks/months) as the target in the recovery phase. We put the dataset information in Table 2, in which QI represents the source of query trends, and “coverage" is the time interval of QI.

In the experiments, we made 30 runs for each test and further output the average result. We measured the query recovery rate for the compared attacks, in which the rate represents how much percentage of the client’s queries the attacks could recover correctly.

We compared our attacks with prior injection attacks in three real-world datasets. Note we do not consider padding strategies in this section but will test the attacks against them later. We tested the performance of the BVA and decoding attack under different parameters since they exploit the rsp with similar recovery approaches. We also performed empirically evaluations on the BVA, the BVMA and other attacks. Note that we did not put ZKP into further comparisons (except in Figure 7 against TC). The crucial difference between our attacks and ZKP is on the leakage pattern. Our attacks exploit the vp while ZKP focuses on the aip. There are both pros and cons for the attacking strategies. For example, our attacks could bypass ORAM (around $60\%$ against both static padding and ORAM on average, see Figure 8), while ZKP cannot; but ZKP requires less injection size than ours (see Figure 7).

Table 3 shows the time cost of restoring $10\times{1,000}$ queries (provided that the adversary knows the keyword universe). Most of the attacks take $<3s$, while the BVMA is slower than others (about $19s$). This is because it merges multiple leakages for keyword filtering, which naturally increases the time complexity.

Figure 5 illustrates that as the number of leaked keywords increases, $Rer$, $ILen$ and $ISize$ present an upward trend. More concretely, $Rer$ delivers a quasi-linear growth, while the incline of $ILen$ and $ISize$ gradually flattens. From the recovery rate, we see that the single-round attack with $m=1$ can only restore $<1\%$ queries, which performs the worst. The BVA and BVMA share a small gap (e.g., $<10\%$ on average in Enron and Lucene) with the decoding and the single-round ($m=\#\mathbf{W}$) attacks. We also notice that the BVMA surpasses the minimum recovery rate of the BVA (see the error bar in Figure 5(a)) by almost $10\%$ when the keyword leakage reaches $100\%$. This is reasonable as the BVMA combines different leakage patterns (e.g., rlp and rsp) to filter candidate keywords, which can bring advantage on recovery rate.

The results of $ILen$ (see Figure 5(b)) show that both BVA and BVMA (only injecting $<20$ files) require much fewer injections (at least $50\times$) than the decoding attack. The single-round attack with $m=1$ takes the same injection length as the decoding attack but with a poor recovery rate (see Figure 5(a)). We note one may set $m=\#\mathbf{W}$ to produce a practical recovery in the single-round attack. But this requires a massive amount of (> $10^{6}$) injected files.

As for the metric $ISize$, the decoding attack gives the worst performance. This is because the attack strongly relies on offset. Table 4 illustrates that offset grows abruptly with the expansion of keyword universe. When $\#{\boldsymbol{W}}=3,000$, each injected file $f_{i}$ must contain $207,015\times i$ words (where $i\in[\#\mathbf{{W}}]$), which is extremely impractical in reality. Similarly, the performance of the single-round attack is restricted by $m$. To achieve a $>80\%$ recovery, the attack (with $m=\#\mathbf{W}$) requires a relatively large injection size, around $10^{10}$ in Enron.

Fortunately, the BVA and BVMA are independent of the offset (and $m$) and require fewer injections. For example, in Enron (resp. Lucene) with 3,000 (resp. 5,000) keywords (see Figure 5, 14), they achieve $>80\%$ recovery rate on average by only taking nearly $10^{8}$ and $10^{4}$ injection size, respectively. The costs are multiple orders of magnitude less than those of the decoding attack ($10^{12}$) and single-round attack with $m=\#\mathbf{W}$ ($10^{10}$). In Wikipedia (see Figure 15) including 100,000 keywords, the injections of the BVA and BVMA are only $10^{10}$ and $10^{6}$ with approx. $60\%$ recovery rate. To maintain the same level of recovery, the single-round and decoding attacks must take respectively $10^{4}\times$ and $10^{6}\times$ costs.