论文整理之Randex——查询恢复攻击

本文为一篇阅读笔记，原文链接：
Randex,Mitigating Range Injection Attacks on Searchable Encryption

1. SE机制

• 经典的图：
  
• 需要注意的点：
  （1）数据的传输过程中，Owner拥有秘钥$K_I，K_D$KI​，KD​；Users拥有秘钥$K_D$KD​；Server是两个秘钥都没有的~
  （2）$K_I$KI​用来加密索引、生成Token；$K_D$KD​用来加密数据，解密数据
  （3）Search函数的返回值是标识符集合：$ID_Q←Search(I，T_Q)$IDQ​←Search(I，TQ​)
  （4）SE的安全性从两个角度讨论：
  • 数据隐私：给一个加密索引和加密元组，攻击者不知道索引值或元组值的明文
  • 查询隐私：给一个查询，攻击者不能获取明文的查询

2. 符号标识

• $D={D_1，... ,D_n}$D=D1​，...,Dn​ ：明文元组集合
• $D_i=[F_i,d_i]$Di​=[Fi​,di​]：$D_i$Di​表示明文元组，包含$F_i$Fi​和$d_i$di​，其中$Fi$Fi表示该元组所存储信息，$d_i$di​表示索引值，eg：$F_i$Fi​代表一个病人的医疗信息，$d_i$di​就表示指向该信息的索引
  此处需要注意的点：$D_i$Di​需要被加密两次，在索引层被加密一次，数据层被加密一次
• $C_i$Ci​：密文元组，$Di$Di的加密版本
• $d_i\in[1,T]$di​∈[1,T]： 索引值，范围为$[1,T]$[1,T] 该数据集上有T个元组、对应T个索引
• $id_i$idi​：是元组$Di$Di的身份识别码，一般为该元组的内存地址或指针
• 查询准确率可表示为：$Pr[id_i\in ID_Q |d_i\in Q]=1$Pr[idi​∈IDQ​∣di​∈Q]=1

3. 攻击概述

已知元组Ci的身份标识符$id_i$idi​，通过一系列注入查询，得到该元组对应的索引值$d_i$di​（这个索引值是存在服务器上的，通过$K_I$KI​加密的）

已知：

• T：索引空间大小
• 加密元组C的身份标识符$id_i$idi​

目的：

• 指向该元组对应的索引值$d_i$di​

方式：

• 一个二分查找过程：其中，服务器观察上一个查询的访问模式，根据观察结果向合谋用户发出相应范围的查询请求，合谋用户将此请求发往数据所有者，数据所有者将生成的Token发回给用户

4. 攻击假设

• 攻击者是诚实且好奇的服务器，可以静悄悄地不注入不破坏，就观察访问模式
• 攻击者可以与第二个用户合谋，提交一系列adaptively-chosen 范围查询

5. 攻击描述

Given：加密元组$C_i$Ci​的身份码：id
Figure out：加密元组$C_i$Ci​的索引值：d
Process：$\le log_2T$≤log2​T次的二分查找，每一次范围查找的range都取决于上一次查找的访问模式

• 二者的合谋实现了通过访问模式执行范围诸如攻击，揭露某个元组的明文索引值（这个索引加密存在服务器中，只有数据所有者知道）
• 这样的攻击是可以扩展的，进一步地，用户可以知道整个数据及所有元组的索引值
• 本文的范围注入攻击是选择查询攻击的变种，二者的区别如下：
  • 选择查询攻击：适用于关键字查询的可搜索加密$Rightarroow$Rightarroow线性搜索：Q=[1,1],Q=[2,2]……Q=[T,T]
  • 范围注入攻击：适用于一维范围查询的可搜索加密$Rightarroow$Rightarroow二分查找：Q=[1,T/2],Q=[1,T/4]……

6. 猜测概率

（1） 未混淆

对任意一个元组$D=(F，d)$D=(F，d)，索引值的二进制向量$b=(b_1,…,b_T)$b=(b1​,…,bT​)

$P_{attack}=\begin{cases} Pr(d^*=d|b_d=1)=1-\mu, if \; T>1\\ Pr(d^*=d|b_d=1)=1,\qquad if \; T=1\\ \end{cases}$Pattack​={Pr(d∗=d∣bd​=1)=1−μ,ifT>1Pr(d∗=d∣bd​=1)=1,ifT=1​

$\begin{cases} \mu:可以忽略的概率，由SE机制引入\\ d^*:猜测索引值\\ d:实际索引值\\ \end{cases}$⎩⎪⎨⎪⎧​μ:可以忽略的概率，由SE机制引入d∗:猜测索引值d:实际索引值​

（2） 引入Randex混淆

对任意一个元组$D=(F，d)$D=(F，d)，被混淆后的索引向量：$b'=(b_1',…,b_T')$b′=(b1′​,…,bT′​)
则,对b’的猜测概率为1，而对b的猜测概率实际上是和b’的混淆程度有关系的，混淆程度越大，猜测概率越小，具体如下：

$\begin{aligned} P_{attack}&=Pr(d*=d|b_d=1)\\ &=Pr(d*=d|b_d=0) \cdot Pr(b_d=0|b_d=1)\\ &\quad +Pr(d*=d|b_d=1) \cdot Pr(b_d=1|b_d=1)\\ &=\mu \cdot(1-p)(1-q)+\frac{1}{\beta+1}\cdot[1-(1-p)(1-q)]\\ \end{aligned}$Pattack​​=Pr(d∗=d∣bd​=1)=Pr(d∗=d∣bd​=0)⋅Pr(bd​=0∣bd​=1)+Pr(d∗=d∣bd​=1)⋅Pr(bd​=1∣bd​=1)=μ⋅(1−p)(1−q)+β+11​⋅[1−(1−p)(1−q)]​

$\begin{cases} \beta：在b'中，除第d位外，值为1的位数，故b‘中有\beta+1位1\\ \frac{1}{\beta+1}：本身向量b中只有1位为1，这才是正常的索引向量\\ \qquad混淆后b’可能含有多个位为1，所以可能是其中任意一个\\ \end{cases}$⎩⎪⎨⎪⎧​β：在b′中，除第d位外，值为1的位数，故b‘中有β+1位1β+11​：本身向量b中只有1位为1，这才是正常的索引向量混淆后b’可能含有多个位为1，所以可能是其中任意一个​

$P_{randex}=\mu+(p+q-pq)\cdot \frac{1}{\beta+1}$Prandex​=μ+(p+q−pq)⋅β+11​

7. 猜测概率期望

$\begin{aligned} E[P_{randex}] &=E[\mu+(p+q-pq)\cdot\frac{1}{\beta+1}]\\ &=\mu+(p+q-pq)\cdot E[\frac{1}{\beta+1}]\\ \end{aligned}$E[Prandex​]​=E[μ+(p+q−pq)⋅β+11​]=μ+(p+q−pq)⋅E[β+11​]​
其中$\beta$β 的所有可能取值有$\beta \in[{\beta_0,\beta_1,…，\beta_{T-1}}]=[0,1,…,T-1]$β∈[β0​,β1​,…，βT−1​]=[0,1,…,T−1]
$令r_j为\beta取\beta_j的概率$令rj​为β取βj​的概率，则：
$\begin{aligned} E[\frac{1}{\beta+1}] &=E[\alpha]\\ &=\sum_{j=0}^{T-1}\alpha_j \cdot r_j \\ &=\sum_{j=0}^{T-1}\alpha_j ({j=0}^{T-1})Pr[b'=0|b=0]^{T-1-j}Pr[b'=1|b=0]^j (有\beta_j个1，即有j个1)\\ \end{aligned}$E[β+11​]​=E[α]=j=0∑T−1​αj​⋅rj​=j=0∑T−1​αj​(j=0T−1)Pr[b′=0∣b=0]T−1−jPr[b′=1∣b=0]j(有βj​个1，即有j个1)​

$\begin{aligned} E[P_{randex}] &=\mu+(p+q-pq)\sum_{j=0}^{T-1}\alpha_j {j}^{T-1} Pr[b'=0|b=0]^T-1-j Pr[b'=1|b=0]^j\\ &=\mu+(p+q+pq)\sum_{j=0}^{T-1}(1-p+pq)^(T-1-j)(q-pq)^j\\ \end{aligned}$E[Prandex​]​=μ+(p+q−pq)j=0∑T−1​αj​jT−1Pr[b′=0∣b=0]T−1−jPr[b′=1∣b=0]j=μ+(p+q+pq)j=0∑T−1​(1−p+pq)(T−1−j)(q−pq)j​

8.FalsePositive

how appear？
$case1： \begin{cases} 对于b_j：当 q_l \le j \le q_u时 ，每一位都为0\\ 对于b’_j：当 q_l \le j \le q_u时，至少有一位为1\\ \end{cases}$case1：{对于bj​：当ql​≤j≤qu​时，每一位都为0对于b’j​：当ql​≤j≤qu​时，至少有一位为1​
$P=1-(Pr[b'_j=0|b_j=0])^k=1-(1-q+pq)^k$P=1−(Pr[bj′​=0∣bj​=0])k=1−(1−q+pq)k
$case2：b_j=0 \rightarrow b'_j=0，但SE机制引入了false positive$case2：bj​=0→bj′​=0，但SE机制引入了falsepositive
$P=(Pr[b'_j=0|b_j=0])^k \cdot \mu=\mu$P=(Pr[bj′​=0∣bj​=0])k⋅μ=μ
因此：
$P_{fp}=1-(1-q+pq)^k+\mu$Pfp​=1−(1−q+pq)k+μ

9.FalseNegative

how appear？
在SE机制保证数据绝对正确的前提下，由随机响应引入：
$\begin{cases} b_j：b_d是1\\ b'_j：q_l \leq j \leq q_u 时，每位都为0 \end{cases}${bj​：bd​是1bj′​：ql​≤j≤qu​时，每位都为0​
$\begin{aligned} P &=(1-\mu)Pr[b'_d=0|b_d=1](Pr[b'_d=0|b_d=0])^{k-1}\\ &=(1-\mu)(1-p-q+pq)(1-q+pq)^{k-1}\\ &=(1-p-q+pq)(1-q+pq)^{k+1}-\mu \end{aligned}$P​=(1−μ)Pr[bd′​=0∣bd​=1](Pr[bd′​=0∣bd​=0])k−1=(1−μ)(1−p−q+pq)(1−q+pq)k−1=(1−p−q+pq)(1−q+pq)k+1−μ​

10.IndexSize

Generate：Randex增加了索引的存储开销，换句话说，指向data的指针增加了
对于包含n个元组的dataset
$without Randex：指针总数\Rightarrow n$withoutRandex：指针总数⇒n
$\begin{aligned} exploit Randex：指针总数 & \Rightarrow n((T-1)Pr[b]_j=1|b_j=0]+Pr[b'_i=1|b_i=1])\\ &\Rightarrow n((T-1)(q-pq)+1-(1-p)(1-q))\\ &\Rightarrow n \cdot T \cdot (1-p) \cdot q +p \end{aligned}$exploitRandex：指针总数​⇒n((T−1)Pr[b]j​=1∣bj​=0]+Pr[bi′​=1∣bi​=1])⇒n((T−1)(q−pq)+1−(1−p)(1−q))⇒n⋅T⋅(1−p)⋅q+p​