安全访问外包数据的研究*

李红卫，古春生，白凤娥

(1.江苏理工学院 计算机工程学院，江苏 常州 213001；2.江苏理工学院 云计算与智能信息处理常州市重点实验室，江苏 常州 213001)

随着云存储技术的发展，越来越多的客户将数据存储在云服务器上，数据的安全也越来越受到重视。数据加密技术可以保护数据的内容，但无法隐藏客户对数据的访问模式，攻击者通过分析数据的访问模式可能获得存储数据的信息。例如，攻击者获知医生在诊断患者患有某种疾病时需要访问某些记录，当某人就诊时，医生对这些记录进行了访问，攻击者即可推断出该人患有某种疾病。为了保护客户的隐私，需要隐藏客户对存储系统的访问模式，实现数据访问的无关性(obliviousness)。所谓数据访问的无关性是指对任意两次数据访问(不管是读还是写)，所访问的存储位置的序列是等同的[1]。一种最简单的解决方法就是每访问一个数据时读写所有数据。每读一个数据时先解密，写回时再加密，每次加密所用的密钥均不相同，使得攻击者无法识别写回的数据是原数据还是修改后的数据。但该方法的代价太大，因此，GOLDREICH O提出了无关RAM模型机(Oblivious RAM，简称O-RAM)[2]并解决这一问题。随着云计算的飞速发展，在数据外包中O-RAM的应用有着重要作用。

1 相关研究

[1]提出最有效的隐藏访问模式是采用分层结构算法。在分层结构算法中，如果洗牌算法采用AKS网络排序[3]算法，则平均时间复杂度为O(c log4N)，其常数项c大约为6 000。当采用巴切排序网络算法[4]时平均时间复杂度为O(c log4N)，其常数项c大小较为合理[5]。

许多学者在参考文献[1]的基础上又提出了一些新的结构[5-9]。其中参考文献[5-6]在平均时间复杂度方面进行了深入的研究。若客户端存储容量为O(1)时，参考文献[5]得到的平均时间复杂度为O(log2N)，但一些研究人员已经发现参考文献[5]所提的结构存在安全问题[6]。在参考文献[6]所提出的结构中，当客户端存储量为O(1)时，获得最好的平均时间复杂度为O(log2N)；若客户端存储容量为时，可获得的平均时间复杂度O(log N)。参考文献[7-9]在最坏时间复杂度方面做了研究。参考文献[7]得出最坏时间复杂度为，但其平均时间复杂度也是。参考文献[8]提出一种新的O-RAM结构，当客户提供存储空间时，其平均时间复杂度为O(log2N)，最坏时间复杂度为。参考文献[9]的最坏时间复杂度为O(log3N)。

以上所提算法均由两个阶段构成，即访问阶段和洗牌阶段，算法的瓶颈就在洗牌阶段。在洗牌时，客户与服务器之间需要进行大量的数据交换，使得客户无法忍受洗牌过程占用的大量时间。如果能把洗牌过程分解到每次访问操作中，对服务器的访问时间保持在常数量级，这样就能将理论应用于实践中。因此，本文提出一种新的结构，在需要少量客户端存储空间和线性级服务器存储容量的情况下，使得每次操作的代价为O(1)。典型算法的性能比较[9]如表1所示。

表1 几种典型算法的性能比较

2 常量级访问模式

本文假设客户端可信而服务器端不可信。O-RAM的目标就是对服务器完全隐藏数据访问模式，即从服务器角度观察，客户端每次读或写数据块请求将产生一个完全随机的数据访问序列。

2.1 数据结构

假设客户的数据大小为N块，每块大小为L字节，在云存储中，L的典型值一般为64 KB～256 KB。本方案需要占用服务器存储容量为3N块，利用均匀随机函数将N个数据块均匀随机地分布到3N个存储块中，其余2N个存储块存放哑元块。

在客户端设置一个缓存队列Q、两张数据表SerMap和PosMap。

缓存队列Q用来管理从服务器读取的数据块，本文假定最多可存储32个数据块。对缓存队列的操作有：Q.in(b)将数据块b插入队尾；Q.out()从队首移出数据块；Q.remove(b)将数据块b从缓存队列中移出；Q.getLen()返回缓存队列中存放的数据块数；Q.getSit(b)返回数据块b在缓存队列中的位置；Q.getSitF()返回队首数据块的块号。

SerMap[3N]用来表示存储在服务器上各数据块的存储位置，它有3个域，分别是FlData、FlAcc和Fresh。Fl-Data表示存储类型，其值为1表示该块为数据块，否则为哑元块；FlAcc表示其对应的存储块最近是否被访问过。当读/写存储块后，该变量的值设置为1。在查找一个哑元块时，若其值为0则选中该块，若其值为1则改为0，继续查找下一个哑元块；Fresh表示服务器存储块的新鲜度，在对服务器的每次读操作后都会使该变量的值增1，以保证相同数据在加密后结果不一样。

PosMap[N]用来表示用户数据块在服务器中存放的位置映射，包括flag和blockAdd两个域。flag表示数据块存放在服务器/本地的标志，若其值为1时，则表示数据块存放在服务器端，否则存放在Q中；blockAdd指数据块在SerMap/Q中的位置。

2.2 访问模式

定义1：设客户对服务器的操作为(op，u，data)，其中，op表示read(u)或者write(u，data)操作，u表示将要读或写的数据块标识，data表示要写的数据块。

无论op是读操作还是写操作，其访问服务器的序列由Lookup算法决定。

2.2.1 Lookup算法

Lookup算法描述如下：

Lookup(op,u,data*);

1：Random read n(n＜=6)blocks from server;

2：if(PosMap[u].flag=0)then{//所读块在Q中

3：ReadDummy(); //随机读一哑元块

4：Q.remove(u);Q.in(u); //将该块从Q中移出再插入队尾

5：}else

6：ReadBlock(u); //从服务器端读数据块u并插入Q中

7：Random read 6-n blocks from server;

8：if(op=write)then

9：Q.bufs[PosMap[u].blockAdd]←data*;//将要写的数据保存在Q中相应的缓冲区中

10：Evict(); //为避免Q溢出，将部分数据块写入服务器

11：return(PosMap[u].blockAdd);

在该算法中第1行和第7行共读服务器6次，其中随机读取2个数据块和4个哑元块，需要把所读的数据块保存在Q中。第2行至第6行读取指定的数据块u并保存在Q中。如果数据块u已在Q中，则随机读一哑元块。根据程序局部性原理可知，最近访问的数据块在最近的将来仍有可能再被访问到，因此对Q的管理并不按照严格意义上的先进先出策略，而是当访问的数据块在Q中时，将该块从Q中移出并放到队尾，以保证从Q中踢出的数据块是不常用的数据块。

当op是写操作时，将要写的内容覆盖Q中保存数据块u的缓冲区(第9行)。在每一次Lookup调用中，不停地有数据块存入Q中，Q总会变满，因此需要定期将Q中的数据块写入服务器以防止Q溢出，第10行是调用Evict将Q中的最久未用的数据块写入服务器。

2.2.2 Evict算法

Q中最多可存放32个数据块，调用一次Lookup最多有3个数据块进入Q中。因此，在Evict算法中，当Q的长度超过29时，则将超出的数据块写入服务器以保证Q在下一次Lookup操作时不会溢出。Evict算法描述如下：

Evict() //写数据块或哑元块到服务器

1∶m←0

2∶while(Q.getLen()＞29)do{

3∶WriteBlock(); //将Q中队首数据块写入服务器

4∶m←m+1

5∶}

6∶for i=m+1 to 6 do

7∶WriteDummy(); //随机写哑元块到服务器中

8∶return;

第1行至第5行将数据块写入服务器。Evict踢出算法每次写6次服务器，先将缓存队列中的数据块写入服务器，然后用哑元块补足6块（第6行至第7行）。

2.3 洗牌

每执行一次Lookup都会将任意两个数据块读入Q中，当Q长度超过29时，就将超出的数据块写到服务器端的任意位置，实现洗牌操作，这样可将整个洗牌操作分摊到每次Lookup中，避免了集中洗牌造成的突发访问。

2.4 性能

假定存储块大小为64 KB，参考文献[9]与本文性能对比如表2所示。当数据文件小于等于16 TB时，所用客户存储空间小于参考文献[9]，当数据文件大于16 TB时，所需客户存储量超过参考文献[9]。本文算法的优势在于所需服务器存储空间较少，实际性能恒定。参考文献[9]采用集中洗牌，当洗牌时需要大量的数据交换，当客户在读写操作时，若正好遇上洗牌操作，则需要等待很长时间。

表2 参考文献[9]与本文性能对比

2.5 安全

定义2：设y=((op1，u1，data1)，(op2，u2，data2)，…，(opM，uM，dataM))是客户请求访问数据块的一个序列，其长度为M。设A(y)表示存取访问模式，当客户的请求序列是y时，用A(y)表示存取访问服务器的序列。如果对于任何两个客户访问序列y和y′，只要其长度相等，对任何人（除客户本人）来说A(y)和A(y′)都是计算上不可区分的，则称该O-RAM结构是安全的。

在Lookup中，数据块u在服务器上的存储位置是随机分布的，读取u和6次随机读数据块操作混在一起，攻击者很难猜到哪一块是真实的块，并且攻击者很难知道下一次它将存放在哪一个位置。

在访问服务器的过程中可能出现刚被淘汰出的数据块又要被访问的情况。这种情况下，攻击者仍然无法获取有用的信息，因为至少有2/3的数据块是随机选取读到Q中的，最多有1/3的数据块是客户所读的数据块，但Evict算法采用最久未用块淘汰策略，攻击者无法知道所读的块是否为所需的数据块，也无法知道什么时间该块会写入服务器，即攻击者从被踢出后又要被访问的数据块中无法获取有用的信息，因此系统是安全的。

本文提出的常量级访问模式仅需占用线性级服务器存储量就可实现无关访问服务器，但它需要占用客户端存储空间，当文件长度超过16 TB时，比参考文献[9]的算法占用更大的客户端存储空间。下一步工作将在减少占用客户端存储空间方面进行研究，找到一个需求客户空间更少的算法。

参考文献

[1]GOLDREICH O，OSTROVSKY R.Software protection and simulation on oblivious RAMs[J].Journal of the ACM，1996，43(3)：431-473.

[2]GOLDREICH O.Towards a theory of software protection and simulation by oblivious RAMs[C].New York：STOC，1987.

[3]AJTAI M，KOLMOS J，SZEMEREDI E.An O(nlogn)sorting network[C].Boston：STOC，1983.

[4]BATCHER K.Sorting networks and their applications[C].NJ：AFIPS Spring Joint Computing Conference.1968.

[5]PINKAS B，REINMAN T.Oblivious ram revisited[C].California：CRYPTO.2010.

[6]GOODRICH M T，MITZENMACHER M.Privacy-preserving access of outsourced data via oblivious ram simulation[J].Automata，Languagesand Programming，2011(6756)：576-587.

[7]BONEH D，MAZIERES D，POPA R A.Remote oblivious storage：Making oblivious ram practical[EB/OL].[2011-3-30].http：//dspace.mit.edu/bitstream/handle/1721.1/62006/MITCSAIL-TR-2011-018.pdf.

[8]STEFANOV E，SHI E，SONG D.Towards practical oblivious ram[C].California∶NDSS，2012.

[9]SHI E，CHAN T H H，STEFANOV E，et al.Oblivious RAM with o((logn)3)worst-case cost[C].Seoul：ASIACRYPT，2011.