multicloudORAM

Multi-CloudObliviousStorage20thACMConferenceonComputerandCommunicationsSecurity(CCS2013)EmilStefanov（埃米尔·斯特凡洛夫）ElaineShi（伊莱恩·施）作者简介•邮箱:[e-mail]•主页:•兴趣：系统安全、隐私、应用密码学；专注于云计算、文件系统、数据库。•教育：加州大学伯克利分校:2009–2014加州，伯克利，计算机科学博士。导师:DawnSong普渡大学(理学学士):西拉法叶校区，2005–2009专业：HonorsComputerScience,数学计算、计算机科学中的数学(3个不同的专业)EmilStefanov（1987-2014）HewasbornApril7th,1987,inSofia,BulgariatoPlamenandPaola(Blagoeva)Stefanov,anddiedinMarch27,2014athishomeinHayward,California.ElaineShi（伊莱恩·施）现为马里兰大学计算机科学系助理教授。•研究方向：安全与隐私、应用密码学、网络与通信、安全存储系统、数据挖掘等。摘要我们提出了一个双云的oblivious存储系统(ORAM)，在客户端与云之间它可实现2.6倍的带宽花费。通过2个或者更多的非连通云分裂出一个ORAM系统，使我们能够让客户端到云的带宽花费至少减少一个数量级，在带宽供应丰富的云之间转换成更高带宽通讯方式。对于限制带宽的客户例如在家里或者移动网络连接，我们的方法使ORAM更加实用。对于我们的双云ORAM系统，提供了一个成熟的执行方案，并且报告的结果是从部署在现实世界的亚马逊EC2和微软Azure得来的。引言存储外包是一个不断增长的行业，它去掉了存储用户维护内部基础设施的负担，并提供规模经济。然而，由于对数据隐私问题的担心，“许多潜在的云计算用户都尚未加入云计算，许多人在大多数情况下只将他们的非敏感数据放在云中”。仅仅依靠加密是不足以确保数据的隐私的，因为访问模式也可以泄漏大量的敏感信息。例如Islam等人，演示基于统计的攻击，利用访问模式成功地推断出大约80%的关于一个加密邮件库的搜索查询。ObliviousRAM(ORAM)概念：ObliviousRAM是Goldreich和Ostrovsky第一次提出的。它一个加密的构造，允许客户端访问存储在不受信任的存储提供商那里的加密数据，而完全隐藏数据访问模式。ORAM保证访问的物理地址序列和请求的实际数据是相互独立的，换言之，物理访问模式没有揭示关于逻辑访问模式的任何信息。为了实现这一点，客户端不断地在存储服务器上重新加密和重组数据块，使用加密来隐藏逻辑访问模式。由于ORAM提供了较高的安全性，因此最近的很多研究使之应用在外包存储中，但是缺点是带宽耗费高，约20X-35X的带宽成本（存取一个块，大约需要转移20-35个块），不利于带宽受限的客户。因此研究人员提出将ORAM和可信硬件结合起来，但可信硬件并没有被广泛部署在当今的云计算平台上。于是，本文提出了一种新的解决方案：Multi-CloudObliviousStorage。1.双云的ORAM带宽资源供应的不对称性•在蜂窝网络或较慢的家庭互联网下，客户端到云带宽是缺乏的。•在主要的云供应商之间网络带宽是足够的（例如亚马逊网络服务和微软蔚蓝）。实验表明，在多个非连通云供应商之间传递数据时，可以将云间通信转换成20x–35x的带宽花费，同时保持客户端到云的带宽花费最小，在典型的参数下大约是2.6X。并且对于隐藏每次访问是读还是写，2X是必要的。我们专注于设计一个最可能接近部署的高度优化的双云方案。我们提供了一个成熟的双云ORAM实现，并已经成功部署在两个主要的云服务提供商，亚马逊网络服务（AWS）和微软Azure。同时使用多个非连通云的想法是自然的，然而如何设计一个可被证明的安全有效的方案是具有挑战性的。主要的挑战是如何避免通过客户端进行数据重组操作，而且还确保安全，防范潜在的可以任意改变规定行为的恶意云。•技术要点我们的主要技术，是在两个云之间随机重组数据。特别地，一个云重组数据块，增加了一个“洋葱”层加密，然后将它们发送到另一个云。以这种方式，一个云观察到了排列变换，另一个云则观察到了这些块的访问，但是没有一个云会获得两者。在下一个回合，两云转换角色。加强诚信行为的云可能是恶意的，我们设计了一种新的交换校验和加密结构。客户端与每个云共享一个秘密校验和函数，使得云能监督彼此的行为。在每一个重组后，每一块约4λ位的校验和，在客户和云之间转移，如此客户端可以验证重组的正确性。上面的，λ=128是安全系数。标准的块大小比λ大得多，举例来说4kb（一个内存页大小）或更大。在重组期间转移全部的块到客户端会招致20x-35x的带宽花费，通过转移每块4λ比特，我们将这部分的花费下降到0.1x到0.2x（共2.6X）。类似于SSS结构，我们的双云ORAM方案要求对于一个有1TB容量的ORAM，客户端存储小于1.5GB的数据（即，小于ORAM容量的0.15%）。特别地，除了缓存个数据块，其中N是总块数，客户也储存每块4字节的元数据。虽然元数据大小在理论上是线性的；它的大小在实践中，通常是相当于或小于个缓存的数据块。这是最可能实现的亚线性客户端存储技术，在早期的作品中运用递归方法描述。这样，我们也可以（递归地）把线性元数据外包给云。然而，在实际中这是不必要的，即使应用递归，在实际设置中递归深度很少超过2至3。除了将客户端云的带宽消耗降低到最小，我们的双云ORAM方案与单云方案相对比较，也差不多将总的带宽消耗一分为二（包括云间和客户端到云通信）。•威胁模型。假定至少有一个云服务提供商诚实，即忠实地执行规定的协议。其他的云可能会恶意偏离该协议。在某个时间之前我们不知道哪个云是恶意的。预防发动拒绝服务（DOS）这种攻击方式的恶意云，不在我们的目标之中。我们也不能防止恶意的云自愿透露其本地状态和视图给诚实的云，这可能让诚实的云了解更多的信息。例如，一个恶意的云可以在一个公共的网站上仅仅发布它的状态和视图协议。然而，我们保证，只要存在一个诚实的云，一个恶意的云就获取不到任何客户端的逻辑访问模式的信息。事实上，任何偏离指定的协议的行为都会立即被客户端检测到。换句话说，通过偏离规定的协议，一个恶意的云只能帮助一个诚实的云获取信息，但他自己获取不到到任何东西。此外，如果他曾经偏离过就会被立即捕捉到。上述直观的安全模型推广到k-cloud设置（K的云需要1个诚实的），在完全的在线版中使用一个基于仿真的定义来正式定义。并且证明了我们的结构在这个基于仿真的完整的在线版本定义下是安全的。2.分区框架我们的算法依赖于分区框架，ORAM结构的划分，是Stefanov、Shi、Song提出的，被称为SSS结构。需要特别注意的是，分区不代表云。事实上，每个分区是跨越多个云的。2.1SSS分区框架介绍：SSS分区框架让我们安全地将ORAM读/写操作，分成在较小的分区的读/写操作，每个较小的分区是一个ORAM本身。该框架由两个主要的技术组成：分区和回收。通过分区，一个较大的，容量为N的ORAM实例，被划分为的较小实例（称为分区），每个容量为。而一个不成熟的分区可以打破安全性，Stefanov等人提出了一种全新的方法，允许分区而不会降低安全性，如下所示。分区框架分区框架//将ORAM分成大小为O(√N)的√N个分区。Read(u)：•查找位置图，确定u被分配给p分区。如果u没有在eviction（回收）缓存中找到：ReadPartition(p,u)。否则如果u在本地eviction(回收)缓存中找到了：ReadPartition(p,⊥)//伪读取•选择一个随机分区p’,添加被u确定的块到eviction(回收)缓存中,并且从逻辑上将u分配到p’分区，•称Evict（回收）了v次，v1，是回收率。Write(u,B):如同Read（u），除了写入到eviction(回收)缓存的块之外，都要被新的块替换。Evict回收：•选择一个随机的分区p•如果一个块B存在于分配给p分区的回收缓存中，调用WritePartition(p,B)。•否则，调用WritePartition(p,⊥)，⊥代表一个虚拟块。图1：SSS分区框架我们的结构使用这种框架来描述ORAMRead和Write操作。依据多云结构的ReadPartition和WritePartition操作。图1阐述了分区框架。在任何时间点，一个块驻留在一个随机分区中。客户端存储位置图来跟踪每一块驻留在哪个分区。访问标识符为u的一个块，客户端首先查找位置图，来确定块u的当前分区p。然后客户端向p分区发出一个ORAM读操作，查找块u。从服务器上读取块，客户端逻辑上地将它分配给一个新的随机分区，而没有直接将这个块写进服务器。相反，这一块暂时地缓存在客户端的本地eviction(回收)缓存中。后台回收进程以Oblivious的方式从回收缓存中回收块返回给服务器。每一次数据访问，随机选择2个分区回收。如果一个块存在于分配给所选分区的回收缓存中，回收一个真正的块；否则，回收一个虚拟块来防止泄漏。2.2ORAM分区：我们的ORAM分区结构是基于SSS结构，这是原始的层次结构的一个变种，但做了各种优化，以面向最大的实际性能。•每个分区由+1个层组成，在那里层i∈{0，1，…..，L-1}可以存储个真实的块，和甚至更多的虚拟块。最大的层，也就是L-1，作为顶层。•我们扩展客户的位置图，来存储每个块的位置元组，其中P是分区，是层，offset表示在层内的偏移量。读客户首先读取位置图找出块的位置元组然后，客户端从p分区的每个层中读取一块。对于层客户端在offset*处读取块。对于其他层，客户端读取一个随机的未读的虚拟块。如果该块在客户端的回收缓存中被找到，则从每一个层中读取一个虚拟块。写向一个分区写回一个块，引起一个重组操作。特别地，让0，1，…..l表示连续的满的填充层，如此，l+1是空的。写回块B导致层0，1，…..l，被重新改组到层l+1中。在单云SSS架构中，重组是通过客户端下载所有的块做到的，排列他们，重新加密，然后把它们返回到服务器。3.在半诚实模型中的基本的双云结构3.1Intuition•减少ORAM重组的开销。在现有的单云的计划中，客户端的带宽开销主要源于重组。客户端周期性地从云下载数据块的一个子集，本地排列、重新加密，写回。在我们的多云的ORAM结构中，我们把重组工作委托给两个云，使客户端到云的带宽使用减到最小。云S1重组一个块的集合，增加了一层加密（也就是，一个“洋葱”层），并将他们发送给S2。当客户需要从那个块的集和中读时，他从S2中提取。以这种方式，云S1知道在重组中用到的排列变换方式，但它并没有看到客户端从S2中请求哪一块。相比之下，S2看到了客户端稍后请求的重组过的块，但它没有被S1应用过的关于排列变换的信息。因此，没有一个云获得了关于客户端逻辑访问模式的任何一点信息（即，“未重组的”）。请注意，为了安全起见在每一个重组后增加洋葱加密层是必要的：如果B块被S1重组然后发送到S2然后再返回S1，我们不想让S1能够连接这两个事件，通过相同的块B，基于块的数据。在完整的在线版本中，我们引入一个后台洋葱去除程序，避免给一个块加入无限数量的洋葱层。•减少ORAM读的开销。现存的单云的ORAM方案在中间重组时读取一个数据块也带来了相当大的带宽开销。例如，一个客户端或许需要在每个分区的个层中读取一个或多个块。在我们的多云的结构中，通过以下方式在读一个块时我们能够显著的减少带宽开销。客户端从S1中请求一组块时（已经重组过的），S1用一个仅仅被S1和客户端知道的排列方式随机排列它们，然后S1把他们发送给S2。最终，客户端通过提供所请求的块的排列索引给S2，从S2请求并且仅下载一个块。3.2云上的数据