云存储数据完整性验证

杨秀华, 梅圣民, 李 玲, 张海蓉

(吉林大学 a. 大数据和网络管理中心； b. 通信工程学院, 长春 130012)

0 引 言

云存储是网络在线存储模式, 具有可扩展性、 高稳定性的特点, 用户将数据存储于云服务器无需购买和维护存储系统, 降低了系统建设成本和维护成本， 因此其已成为数据存储的发展方向[1]。但由于云存储环境的半置信以及各种不确定因素, 使用户对云存储数据安全产生忧虑, 近年来发生的多起云计算事故加剧了用户的担忧, 即使亚马逊S3服务器也发生过宕机事故。为防止信息泄露和未授权的数据修改, 云存储数据完整性验证是必不可少的[2]。由于网络带宽的限制, 用户将全部数据下载到本地再进行验证无法实现。因此如何实现远程通过随机取回少量数据, 即可高置信概率检验数据完整性的方法得到人们广泛重视。目前研究方案可分为可取回性证明(POR: Proofs of Retrievability) 和数据持有性证明(PDP: Proof of Data Possession)。两类方法的基本思想都是基于采用某种形式的挑战-响应协议结合伪随机采样的概率性检查方法验证数据完整性。POR方案不仅能提供可取回性证明, 而且还可以恢复部分被损坏的数据, 因此它是在半置信云环境下重要的检验方法。

在数据可取回性证明研究方面, Lillibridge等[3]提出了类POR协议。该协议将error-coding应用于文件中, 通过抽样检查的方法验证数据完整性。但该方案没有给出正式定义, 验证时也没有约束限制。Naor等[4]首次提出POR方案, 并给出了正式定义和安全模型。将纠删码应用于文件中, 消息验证码作为检验值, 通过随机检查数据子集验证数据完整性。但该方案将整个文件编码为纠删码中的单个码字, 这样的编码在实际应用中是无效的。Juels等[5]提出了基于岗哨的POR方案, 将一系列随机数作为验证信息加入数据块中, 随机数称作岗哨, 通过挑战-响应协议验证岗哨完整性。该方案支持有限次数的挑战。Shacham等[6]提出了两种新的证明方法。一种方法是基于BLS(Boneh-Lynn-Shacham) 签名, 允许公开验证, 任何人都可以作为检验者； 另一种方案是基于伪随机函数, 只允许私有验证。两种方案都是使用同态认证的属性将同态认证元聚合很小的检验值, 该方案支持无限次数挑战。 An等[7]提出了轻量级的POR方案。将随机数作为验证信息加入编码产生的冗余数据块中, 通过随机数验证数据完整性。

在数据持有性证明研究方面, 谭霜等[8]详细研究了典型的PDP方案, 分析对比各种验证机制及特点, 探讨了未来云存储数据完整性验证的研究方向。毛向杰等[9]提出混合验证方案, 对静态类型数据和动态类型数据分别采取不同的验证方案, 在一定程度上降低了计算成本和通信成本。Ateniese等[10]在传统PDP方案的基础上, 提出动态操作的思想, 并实现了对远程数据部分动态操作。Erway等[11]引入动态数据结构, 支持全动态操作, 但计算开销和通信开销很大。吴颖豪等[12]提出利用双线性技术对远程数据进行完整性验证, 并使用索引表实现对数据的动态操作。史春红等[13]提出了多副本的数据完整性验证方案, 通过对副本哈希数组进行异或运算实现数据的动态更新, 具有一定实用性。王春波等[14]根据数据块生成哈希函数, 然后利用哈希函数计算标记值, 根据标签确定数据块在数据分区的位置, 减少查询索引数据时间。刘峰等[15]提出基于区块链的数据完整性验证方案, 将证明信息和辅助验证信息存储在区块中, 由区块链上的智能合约提供验证服务, 能满足安全性要求。

M-POR方案基于POR, 原始文件经过加密、 伪随机置换以及冗余编码, 然后存储到云服务器。消息验证码作为验证信息。用户通过随机挑选数据块向服务器端发起挑战, 要求服务器返回相应的检验值进行验证。如果文档被修改或损坏, 检验值大概率也被破坏, 服务器端不可能返回正确的检验值, 验证无法通过。只要执行足够数量的挑战, 挑战-响应协议能提供数据完整性证明。笔者提出基于消息验证码的数据可取回性方案M-POR(Proof of Retrievability-Based Message Authentication Codes), 消息验证码作为检验值, 用户通过检验值验证数据完整性。仿真实验证明M-POR方案是安全有效的。

1 M-POR系统定义

1.1 M-POR符号和函数定义

challenge(η,k)→p: 以密钥k和数据块索引η为输入生成挑战信息(位置信息)p输出到服务器端。

verify((p,r·η);k)→(0,1): 验证响应信息r是否是有效的响应, 若结果为1, 验证通过； 而结果为0, 验证失败, 说明数据错误。

extract(η,k,ω)→F: 客户端以数据块索引η、 编码参数ω和密钥k为输入, 向服务器发起一系列挑战, 然后处理响应信息, 如果成功, 可取回文档F； 如果失败, 则通过冗余数据恢复一定数量被损坏的数据块。

Pkey(N): 加密的伪随机置换(PRP: Pseudo Random Permutation), 用于对数据块和冗余块进行伪随机置换。

1.2 文件编码

文件F首先被分割为N块, 每块m位, 然后以l块为一组进行分组, 将数据块分成S组。应用error-correcting-code(n,l,t+1)对分组数据块bi={bi,1,…,bi,l}1≤i≤S进行编码, 编码后每组数据块由l块扩展到n块,t表示每组数据编码后生成的冗余块,t=n-l, 冗余块依照生成的先后顺序组成冗余块序列{vi}1≤i≤s×t。对一个长度为n的分组, 通过冗余编码可以恢复[t/2]被损坏的数据块。

1.3 检验值生成算法

在M-POR方案中, 采用每组数据块追加一个检验值, 第i组的检验值Mi计算方法如下。

以密钥kmac及相应的数据组bi={bi,1,…,bi,l}1≤i≤S为输入, 生成相应的检验值。

Mi=f(kmac,bi)

(1)

将Mi追加到相应的数据组中。由于检验值是通过计算数据块获得, 计算效率高, 此外, 采用一组数据附加一个检验值, 相比每块数据附加一个检验值, 存储成本减至(1+1/l)×N, 降低了存储成本。

1.4 伪随机置换

利用伪随机置换Pkey()对数据块以及冗余块进行置换。数据块置换使数据块随机分发, 服务器无法确定某一个数据块属于哪一组, 冗余块置换使数据块和冗余块无法对应, 增强了系统安全性。

2 M-POR算法

2.1 编码方案

1) 定义数据块的长度为m-bits, 将文件F顺序切割成N块, 文件F构成由N个数据块组成的序列, 该序列表示为{ci}1≤i≤N。长度为m-bits的数据块作为基本存储单元, 加密算法以及RS编码都是针对m-bits数据块进行, 检验值的长度也是m-bits。

3) 将置换后的数据块分组： 以l块为一组, 将数据块分成S组, 表示为{bi}1≤i≤S,bi={bi1,…,bil}1≤i≤S。

4) 利用error-correcting code(n,l,t+1)对每个数据分组进行编码, 产生t个冗余块, 将冗余块放在一起组成冗余块序列{vi}1≤i≤S×t。

5) 以密钥kmac及相应的数据组bi={bi,1,…,bi,l}1≤i≤S的数据为输入, 生成一系列检验值Mi。

6) 使用密钥kenc加密数据组{bi}1≤i≤S, 将检验值Mi追加到相应的数据组。

在编码过程中, 分别对数据块和冗余块进行伪随机置换, 对数据块的置换使服务器或攻击者无法确定某一数据块属于哪一组, 隐藏了数据块之间的边界。对冗余块置换使数据块和冗余块无法一一对应, 有效防止了恶意服务器的欺骗, 增强了文件系统的安全性。此外, 对文件进行冗余编码, 可以检测t个错误, 修复t/2个错误, 增强了算法的纠错能力。

2.2 数据完整性验证算法

M-POR通过挑战-响应-验证算法提供数据完整性证明。验证算法包含challenge()、respond()、verify() 3个函数, 分别对应验证过程的3个阶段。验证算法如下。

1) 挑战阶段。检验者使用challenge()函数随机选择需要验证的数据块, 计算数据块索引, 生成挑战信息(位置信息), 如果每次选择q组数据块, 挑战信息包含q组数据块位置信息, 最后将挑战信息p发送给证明者。

2) 响应阶段。证明者使用云端respond()函数根据挑战信息在云文档中查找数据块, 然后读取附加在数据块后的检验值Mi, 作为响应信息r与数据索引信息p一起返还给检验者。

3) 验证阶段。检验者调用函数verify()验证返还的检验值Mi是否与客户端保存的检验值一致, 一致则返回1), 验证通过； 反之返回0, 说明数据块出现错误。

2.3 数据提取算法

用户首先对服务器端发起数据提取请求, 将要提取数据块的位置信息发送给服务器, 服务器端根据收到的数据位置信息, 在云文档中查找相应的数据块, 返还用户。

服务器返回的数据是编码数据, 数据提取算法利用函数extract()处理编码数据。提取过程如下。

1) 首先对冗余块解密, 然后对冗余块进行伪随机逆置换, 解析出完整的冗余校验码

2) 从数据块中分离检验值Mi, 然后解密数据块。

3) 应用RS-decode对每组编码数据进行解码, 如果数据没有出现错误, 解码成功, 则恢复分组数据块, 如果分组数据出现错误, 且错误数据小于阈值, 则利用冗余数据块进行恢复。重复解码, 直至恢复所有分组数据。如果错误数据比例过大, 则无法恢复, 解码失败。

3 M-POR安全分析

根据M-POR编码方案, 原始文件执行了加密并且进行了伪随机置换, 如果伪随机置换密钥和文件加密密钥是安全的, 则只有按照挑战-响应协议生成的响应才能通过验证。

笔者从两个方面证明M-POR方案是安全的： 1) 证明检验算法是安全的, 任何欺骗的响应都无法通过验证； 2) 编码算法提高了存储文件的安全性。

3.1 检验算法的安全性证明

2) 即使攻击者或恶意服务器提供了正确的检验值Mi, 检验也无法通过。

挑战者向服务器端发起挑战时, 挑战者同时保留数据块的索引信息, 在进行完整性检验时不但要验证检验值是否一致, 而且挑战数据块的索引信息也要一致, 攻击者或服务器提供的有效的检验值Mi或是恶意获得, 或是系统的回放信息, 但无法获得数据块的索引信息, 因而无法通过验证。

3.2 编码算法提高了系统的安全性

根据RS编码理论, 一个包含有N个数据块的编码文件, 当数据出现损坏时, 如果损坏数据的比例小于阈值, 通过冗余块可以修复数据。

综上所述, M-POR方案是安全的。

4 M-POR仿真与性能分析

仿真实验的云环境是在本地搭建伪分布式的Hadoop平台, 采用linux操作系统, 利用不同的Java 进程模拟分布式运行中的各类节点。仿真过程使用Java语言在Eclipse平台下实现。实验在单一节点完成。

采用1 GByte文件进行测试。数据块大小为128-bits, 将1 GByte文件切割成67,108,864块, 采用参数为(255,223,33)Reed-Solomon系统码。分组编码后组成300 936个RS码组。伪随机置换过程采用位置互换完成。

通过分析客户端、 服务器端存储成本、 计算成本以及“挑战-响应-验证”过程中的计算开销评估M-POR算法的性能。

1) 存储成本。服务器存储开销相对原始文件的增加量主要由两部分构成： 冗余编码产生的冗余块以及每个数据组附加的检验值。在M-POR方案中每组追加一个检验值, 通过确定合理的每组数据块的数量, 控制检验块的数量, 从而降低存储成本。

在仿真实验中, 1 GByte文件编码后组成300 936个码组。编码后冗余数据块为9 629 952, 冗余块增加的存储成本约14%, 检验块为300 936, 增加的存储成本约0.44%。

客户端的存储开销主要用于存储检验值以及密钥。检验值是用于验证挑战-响应返回的检验值, 密钥包括伪随机置换密钥、 对称加密密钥以及检验值密钥。

图1 挑战-响应-验证时间成本Fig.1 The time costs of challenge-responding-verifying

2) 计算成本。计算成本包括本地和服务器两部分。客户端的计算成本是M-POR算法编码以及解码所需的时间, 服务器的计算成本是系统在云文档中查找数据块需要的时间。笔者测试了随机选择不同数目数据块时挑战、 响应以及验证过程的计算开销, 如图1所示。

通过图1仿真结果可看到, 随着抽取的数据块数目的不断增加, 挑战、 响应、 验证的时间逐步增加, 其中验证成本增加很小； 而挑战、 响应时间随着挑战数据块数目的增多而逐渐增大； 当数据块数目非常大时(如增加到2 000), 挑战的成本变得与响应的成本相当。

笔者测试了文件编码过程计算开销, 如表1所示, 整个编码过程消耗时间为7 356 ms。其中伪随机置换运算时间为6 793 ms, 时间开销较大, 但伪随机置换提高了算法的安全性。

表1 编码过程各阶段时间开销

5 结 语

笔者针对云存储数据完整性验证方法进行了研究, 提出了基于消息验证码的数据可取回性证明方案M-POR。给出了M-POR的基本模型, 并对数据的编码、 验证、 提取算法进行了详细描述。在编码中采用了数据加密, 伪随机置换以及冗余编码, 提高了算法的安全性能, 可有效抵抗攻击者或恶意服务器的攻击和欺骗。笔者在云平台对M-POR算法进行了测试, 分析了存储成本, 计算成本, 仿真实验证明M-POR方案是安全有效的, 能提供云存储数据完整性证明。

参考文献：

[1]傅颖勋, 罗圣美, 舒继武. 安全云存储系统与关键技术综述 [J]. 计算机研究与发展, 2013, 50(1): 136-145.

FU Yingxun, LUO Shengmei, SHU Jiwu. Survey of Secure Cloud Storage System and Key Technologies [J]. Journal of Computer Research and Development, 2013, 50(1): 136-145.

[2]冯登国, 张敏, 张妍, 等. 云计算安全研究 [J]. 软件学报, 2011, 22(1): 71-83.

FENG Dengguo, ZHANG Min, ZHANG Yan, et al. Study on Cloud Computing Security [J]. Journal of Software, 2011, 22(1): 71-83.

[3]LILLIBRIDGE M, ELNIKETY S, BIRRELL A, et al. A Cooperative Internet Backup Scheme [C]∥In USENIX Annual Technical Conference, General Track 2003. San Antonio, Texas, USA: USENIX Association, 2003: 29-41.

[4]NAOR M, ROTHBLUM G N. The Complexity of Online Memory Checking [C]∥In 46thAnnual IEEE Symposium on Foundations of Computer Science. Pittsburgh, PA, USA: IEEE, 2005: 573-584.

[5]JUELS A, KALISKI B. PORs: Proofs of Retrievability for Large Files [C]∥In Proceedings of CCS’07. Alexandria: ACM Press, 2007: 584-597.

[6]SHACHAM H, WATERS B. Compact Proofs of Retrievability [J]. Journal of Cryptology, 2013, 26(3): 442-483.

[7]AN Baoyu, ZHOU L, GONG Z, et al. Light Weight Proofs of Retrievability in Cloud Archive Storage with Replications [J]. International Journal of Digital Content Technology and Its Applications, 2012, 6(10): 127-135.

[8]谭霜, 贾焰, 韩伟红. 云存储中数据完整性证明研究及进展 [J]. 计算机学报, 2015, 38(1): 164-177.

TAN Shuang, JIA Yan, HAN Weihong. Research and Development of Provable Data Integrity in Cloud Storage [J]. Chinese Journal of Computers, 2015, 38(1): 164-177.

[9]毛向杰, 张品. 云平台数据完整性混合验证方案 [J]. 计算机工程, 2020, 46(10): 46-51.

MAO Xiangjie, ZHANG Pin. Hybrid Verification Scheme for Data Integrity of Cloud Platform [J]. Computer Engineering, 2020, 46(10): 46-51.

[10]ATENIESE G, PIETRO R D, MANCINI L V, TSUDIK G. Scalable and Efficient Provable Data Possession [C]∥In Proceedings of the 4th International Conference on Security and Privacy in Communication Networks. Istanbul, Turkey: Association for Computing Machinery, 2008: 1-10.

[11]ERWAY C, KUPCU A, PAPAMANTHOU C. Dynamic Provable Data Possession [J]. ACM Transactions on Information and System Security, 2015, 17(4): 1-25.

[12]吴颖豪, 凌捷. 一种改进的云存储数据完整性验证方法 [J]. 计算机工程, 2019, 45(3): 36-40.

WU Yinghao, LING Jie. An Improved Data Integrity Verification Method for Cloud Storage [J]. Compute Engineering, 2019, 45(3): 36-40.

[13]史春红, 赖淼麟, 李珊, 等. 云存储中动态多副本数据的完整性验证 [J]. 成都大学学报(自然科学版), 2020, 39(1): 64-68.

SHI Chunhong, LAI Miaolin, LI Shan, et al. Integrity Verification of Dynamic Multiple-Replica Data in Cloud Storage [J]. Journal of Chengdu University (Natural Science Edition), 2020, 39(1): 64-68.

[14]王春波, 底晓强. 基于标签分类的云数据完整性验证审计方案 [J]. 吉林大学学报(工学版), 2021, 51(4): 1364-1369.

WANG Chunbo, DI Xiaoqiang. Cloud Storage Integrity Verification Audit Scheme Based on Label Classification [J]. Journal of Jilin University (Engineering Edition), 2021, 51(4): 1364-1369.

[15]刘峰, 赵俊峰. 基于区块链的云存储数据完整性验证方案 [J]. 应用科学学报, 2021, 39(1): 164-173.

LIU Feng, ZHAO Junfeng. Cloud Storage Data Integrity Verification Scheme Based Blockchain [J]. Journal of Applied Science, 2021, 39(1): 164-173.