基于双线性对的物联网远程数据完整性验证算法

李超良^{1, 2}，刘琴³，王国军¹

(1. 中南大学 信息科学与工程学院，湖南 长沙，410083；

2. 湖南商学院 计算机与信息工程系，湖南 长沙，410205；

3. 湖南大学 信息科学与工程学院，湖南 长沙，410082)

摘要：针对物联网中数据完整性验证的需求，基于BLS短签名，提出一种基于双线性对的动态、远程、异地数据完整性检测算法DRDA。该检测算法建立进行远程检测的系统模型；定义算法及包含的主要过程与函数；设计适合物联网环境的远程数据、动态完整性检测算法，并对数据修改、删除等操作进行详细描述。理论分析表明：该算法可抵抗多种攻击，保护用户隐私。仿真实验结果表明：与有的DPDP方案相比，DRDA算法能动态实现数据完整性验证，平均通信开销要减小40 kB，在用户端计算时间平均减少260 ms，在服务器端平均认证时间减少1 ms。

关键词：双线性对；远程数据；完整性验证；动态

中图分类号：TP393             文献标志码：A         文章编号：1672-7207(2014)11-3824-08

Integrity verification algorithm for remote data in Internet of Things based on bilinear pairings

LI Chaoliang¹_’ ², LIU Qin³, WANG Guojun¹

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;

2. School of Computer and Information Engineering, Hunan University of Commerce, Changsha 410205, China;

3. College of Information Science and Engineering, Hunan University, Changsha 410082, China)

Abstract: According to the demand of dynamic detection in Internet of Things, a dynamic and remote detection algorithm (DRDA) with privacy preserving was proposed, which was based on BLS signature and bilinear pairings. This algorithm was to establish the system model suitable for remote detection, define several functions and procedures of algorithm, and propose an integrity detection algorithm for dynamic and remote data, which can be used in Internet of Things. Finally, several related operations, such as deletion and insertion, were described in detail. The theoretical analysis shows that the proposed algorithm can not only detect the integrity of a remote object’s number dynamically, but also preserve the clients’ privacy and resist several attacks. The simulation experiments show that compared with DPDP, and the DRDA can detect the integrity of data dynamically, the communication cost of the DRDA decreases by 40 kB, computation time decreases by 260 ms in client and authentication time decreases by 1 ms in server averagely.

Key words: bilinear pairings; remote data; integrity verification; dynamic

物联网是继计算机、互联网之后，世界信息产业的第三次浪潮，是计算机技术和通讯技术深度融合的产物。物联网是通过射频识别技术 (RFID)，按约定协议，把相关物品与互联网连接起来，进行信息的交互及通讯，以实现物品的智能化识别、管理、监控的一种网络技术^[1]。目前，许多企业采用国际化生产、销售的经营模式，为加强管理，就必须对存放在远程、异地的仓库中的商品在进、出仓库以及日常管理中进行完整性检测，防止丢失、损耗等情况的发生。具体来说，主要有如下几方面的需求：1) 实时快速地对远程、异地的待售商品进行动态管理；2) 引入数据安全访问机制^[2]、用户检索隐私保护机制，实现数据的安全访问；3) 对检测过程中的信息进行签名，实现加密处理，保护用户隐私。当前，利用物联网技术对商品进行有效管理，实现商品数量完整性验证，已成为物联网领域一个重要的研究热点，国内外的许多学者已提出多种管理方案。朱炜玲等^[3]采用对称加密算法及hash函数设计了一个能实现标签快速认证的协议，具有较低的计算量及较好的安全性。Liang等^[4]提出一种基于分布式预测的安全可靠的路由模型。Lin等^[5]基于节点随机图提出一种协作的认证机制, 但这几种结构均不能直接应用于本文所研究远程数据完整性检测的环境。哈希锁^[6]是一种典型的非树形结构的方法，该方法用标签ID的哈希值来标识标签，缺陷在于该哈希值会导致隐私泄露，且搜索效率较低。Li等^[7]提出一种能保护隐私的轻量级算法，但是这类方法存在标签反馈信息发生碰撞的缺陷。谢磊等^[8]以RFID的数据管理为切入点，在宏观层面从算法、协议以及性能3个方面对RFID中的防冲突算法、认证技术及隐私保护协议进行阐述及分析。Li等^[9]基于中国剩余定理提出了一种批量的、快速实现商品数量完整性检测的方案，这种批量的检测方案，所需要的时间与商品的数量无关，检测时间大幅降低。面向移动的计算环境，郭云川等^[10]基于混杂类型检测的安全π演算，提出了一种统一的安全形式模型，能保障移动计算中数据的机密性及完整性。Shacham等^[11]基于云计算环境提出了一种支持静态对象数量检测的远程检测方案，但这2种方案的效率都不太高。上述的检测方案对于商品数量变化不太频繁的情况，具有较好的检测效果，如果商品数量经常发生变化，上述方案则不能进行有效处理，且存在商品信息泄漏的危险。针对物联网环境中目前已有检测算法不能有效地对商品数量进行动态检测的不足，本文基于改进的BLS签名方案，提出一种以双线性对为验证手段、以MHT为存储结构，在没有可信第三方参与的情况下实现快速、动态、远程商品数量完整性检测的算法 DRDA，该算法能实现远程、动态的对象数量完整性检测，抵抗信息窃取等多种攻击，有效地保护用户隐私。

1  相关理论

1) Merkle Hash Tree (MHT)：MHT是一种能够安全、有效地判别叶子节点对象属性的二叉树^[12]，广泛地应用于身份认证。在本文中，对MHT的功能进行扩展，使得MHT不仅能认证数据的完整性，也能认证tag数据的位置。

2) BLS签名^[13]：设G是一个阶为素数q的群，g是G的1个生成元。x是1个整数，公钥为。对于信息m以及随机数u，签名可以表示成。

3) 双线性对：也称双线性映射，是一种实现加密、解密的重要技术^[14]。假设G是一个循环群，g是群G的一个生成元。G_T是一个乘法群，e表示一个可计算的双线性映射，即e：，且满足以下3个属性：

① 双线性：，对于2个任意的整数a和b，有；

② 非退化：，满足；

③ 可计算性：，存在有效的算法，能计算出。

2  DRDA算法

2.1  应用模型

本文研究内容的应用场景主要包含2类对象：企业用户(CLIENT)、云计算服务器(SERVER)。企业用户表示从事跨国生产、经营、销售的公司。云计算服务器能够进行信息的存储、计算，通过与用户之间的信息传递，实现商品数量完整性检测，对商品进行有效管理。

跨国企业生产的产品在全球范围存放、销售，为了对这些处于远程、异地的仓库中的商品进行快速、有效的管理，防止偷盗、损毁等情况的发生，就必须频繁地对这些仓库中的商品数量进行检测，以保证其完整性。用户主要操作过程如下：对商品信息进行加密，将信息上传给服务器，在服务器的协助下，进行相关数据信息的认证，实现完整性检测；云计算服务器，主要作用有3个：1) 存储企业用户存放在仓库中的商品信息；2) 随着仓库中存储的商品的改变，根据用户的要求对存储在云服务器中的商品信息进行更新，以适应快速查询的需求；3) 响应用户请求，对所存储的商品进行动态、随机完整性检测。

2.2  符号定义

表1列出了DRDA算法中用到的一些主要变量，并对每个符号的意义进行了说明。

表1  DRDA算法符号及意义

Table 1  Symbols and explanation of DRDA

2.3  过程定义

下面对本文所提出的动态检测算法需要用到的一些函数进行详细描述。

1) 。该函数由用户执行。输入为用户私钥s及由tag信息组成的文件F，输出为文件的签名s及MHT树根R的签名S_s(h(R))。其中F=(F₁, …, F_i,…, F_n)，F_i表示第i个标签中的数据，s=(s₁,…, s_i,…, s_n)，s_i表示对第i个文件F_i的签名，h(R)为MHT的叶子节点的取值。

2) 。该函数由服务器执行。输入为文件F及签名s，输出为文件F的完整性证明A。

3) 。该函数由用户执行。用户收到完整性证明A后，根据公钥p来验证文件的完整性，如果没有被篡改，输出true，否则输出false。

4) 。该函数由服务器执行。服务器在收到用户的更新请求后，根据原来的文件F及签名s 输出一个新的文件，签名及证明。

5) 。该函数由用户执行。用户收到新的证明后，根据公钥，验证更新的正确性。如果错误，输出false, 否则输出true, 给出新的签名。

2.4  算法设计

下面从数据完整性验证和数据动态更新2个方面描述算法的主要思想：在物联网中，每个商品都贴有一个标签(tag)，标签中保存有该商品的主要信息，如产地、商品名、生产日期、保质期、主要构成成分等。每个标签中的原始信息看成是一个小文件F_i，多个小文件构成一个较大的文件F=(F₁,…, F_i,…, F_n)。

2.4.1  数据完整性检测

假设G是一个循环群，G_T是一个乘法群，g是群G的一个生成元，e表示你一个可计算的双线性映射，即e:G×G | G_T。假设G和G_T中的离散对数问题是难以求解的。H和h是2个hash函数，h:{0,1}^*→G，H是一个加密的hash函数。方案的执行过程描述如下。

算法初始化：用户选择一个随机数α作为自己的私钥，计算β=α×g作为公钥，私钥s=(α)，公钥p=(β)。

信息块签名S_g(s,F)：用户利用每个tag_i信息文件块F_i的哈希值h(F_i)作为MHT叶子节点的值，构建MHT，MHT的树根用R表示。然后，用户用私钥α给每个tag_i信息块F_i签名，得到每个标签数据所对应的信息块对应的签名。对于多个签名用集合F＝表示。树根签名为。然后，将发送给服务器进行完整性检测。

完整性检测：根据CLIENT的要求，通过和服务器的信息交互，实现商品动态完整性检测。具体过程描述如下：CLIENT首先选择一个随机整数c，构建一个具有c个整数的集合，表示为，假设s₁≤…≤s_c。对于集合I中的每个元素i，均相应地选择一个随机整数v_i，组成一个“查询”二元组{(i,v_i)} (s₁≤i≤s_c)，该“查询”二元组{(i,v_i)}表示需要查询信息块中第i个信息。然后将该查询信息发送给服务器进行完整性查询。

生成完整性证明：收到用户发送的“查询”请求后，服务器计算出下式：

              (1)

此外，服务器提供给用户在计算MHT的根节点时所需要的从所需查询的叶子节点到R的路径上的所有节点及其兄弟节点的信息，其完整性证明标志为A= 。

验证完整性：收到服务器返还的完整性证明A，用户根据收到的信息，计算根节点的R，然后判定下式是否相等：

         (2)

若式(2)不成立，则表明通过计算服务器返回的信息而得到的根节点的值与本地存储的根节点的信息不符，说明服务器所存储的信息遭到未被授权的修改，完整性遭到破坏；若式(2)成立，则说明根节点正确，为了验证路径信息的正确性，用户还需要验证下式是否成立：

           (3)

若式(3)成立，则说明从所需要查询的叶子节点到根节点的整条路径上的所有节点信息均是正确的、完整的，没有遭到非法的篡改；否则，表明这些路径信息遭受恶意修改。该协议的具体图示如图1所示。

2.4.2  数据动态更新

有效地进行数据的动态完整性检测而需要进行的

标签数据操作，包括标签数据修改(M)、标签数据节点插入(I)、标签数据节点删除(D)。

标签节点数据修改：在物联网中，需要经常对标签中的数据进行修改，一种常用的操作就是将某个特定的标签节点数据用一个新的数据代替。具体过程如下所述：如果用户需要将第i个标签的数据F_i修改成，需要进行如下操作，具体过程如图2所示：首先，针对新的标签数据，用户计算其对应的签名，然后，构建查询消息四元组, 并且将该四元组发送给服务器(其中M表示需要进行在MHT中进行修改操作)。服务器在收到要进行修改的操作请求后，运行预先定义的方法。

具体过程如下：1) 将需要修改的标签的数据由F_i修改为；2) 将签名改成并输出；3) 将MHT中第i个叶子节点值由修改为，并根据更新后的叶子节点值构建新的MHT树，计算新的根节点(图3)；4) 服务器返还给用户一个新证明标志(表示MHT中从更新后的叶子节点到根节点的路径上的节点及其兄弟节点信息)。用户收到服务器发送的数据更新证明A_u后，根据收到的信息()产生新的根节点R，通过计算下列等式(4)验证新节点R的正确性。如果等式(4)不成立，输出false, 否则用户通过()计算新的根节点并与进行比较，若不相等，则输出false，否则输出true，并将签名后的新节点值发给服务器更新数据。

图1  完整性检测协议

Fig. 1  Protocol of integrity verification

图2  数据更新协议

Fig. 2  Protocol of data update

           (4)

标签数据插入：标签数据修改，不改变MHT的结构，相对来说比较简单。而标签数据插入，需要将一块数据插入到MHT中，从而会改变整个树的结构。用户需要在MHT第i个叶子节点F_i后插入1个新的标签数据。过程大致如下：1) 用户给新的标签数据签名得到；2) 构建通知服务器插入的四元组，并将该四元组发送给服务器。服务器收到用户的插入请求后，运行进行数据更新，具体过程如下：1) 服务器存储，在MHT的叶子节点后插入1个新的节点；2) 将签名加入到签名集合并且输出新的签名集合；(3) 根据MHT产生节点；(4) 服务器返回插入更新证明 。具体过程如图4所示。

如图4所示，在叶子节点后插入1个新的节点，只需要在MHT中插入新的节点及节点c，。收到服务器返还的数据插入更新证明后，用户使用产生根节点R, 并且通过判定式(5)是否相等来验证根节点R。

          (5)

若式(5)不成立，则输出false，否则，用户利用信息计算新的节点并将该值与进行比较，若不相等，则输出false，否则输出true，用户将新节点签名修改成，发送给服务器进行 更新。

标签数据删除：数据删除与数据插入操作是相反的，即删除一个特定的数据块，并且将该数据后面的数据节点往上一层移动，产生新的根节点。具体细节与节点修改、插入类似。图5所示为标签数据节点删除的示意图。

图3  数据修改

Fig. 3  Data modification

图4  数据插入

Fig. 4  Data insertion

图5  数据删除

Fig. 5  Data deletion

3  算法安全性分析

本文所使用的签名方案来自于BLS签名^[13]与Shacham等^[11]的方案。由于Shacham等^[11]已经证明该签名方案在安全性上可以归约为CDH问题，所以，本文的签名方案是安全的，具体的证明过程见文献[11]。下面将讨论具有远程数据完整性检测、更新功能的动态完整性检测算法在检测过程和数据更新过程中存在的一些攻击行为，分析方案的安全性。

3.1  完整性检测中的攻击行为

SERVER收到CLIENT提交的查询请求信息二元组{(i,v_i)}后，经过计算，返还给用户的1个表示信息完整、没有被非法篡改的标记 ，用户根据下式是否成立，来判断数据的完整性。在传输过程中，若完整性标记A被攻击者获取，即假设攻击者能得到，而公钥 ()是已知的，则由于CDH计算的困难性，由及b不能计算出，从而可以保护数据的安全；若攻击者获取了完整标记，则由于哈希计算的单向性，从无法得到F_i，在一定程度上保护了用户隐私。

3.2  数据更新中的攻击行为

CLIENT在计算好需要更新的标签的签名后，将需要包含标签节点的位置、需要进行的操作、文件的哈希值及签名的四元组传送给SERVER，如果在传送过程中，该四元组中的及被攻击者窃取，由于解决CDH问题的困难性，攻击者无法破解，从而无法冒充SERVER计算新的根节点及其签名。若攻击者截取了SERVER传送给CLIENT的更新标识 ，则也会被CLIENT识别。因为CLIENT将根据收到的信息产生新的根节点R，并且需要验证是否成立。攻击者仅仅知道h(R)及b，在不知道私钥的情况下，由于CDH问题的困难性，计算h(R)×b是困难的，从而保证了数据更新的安全。从上述攻击可以看出，本文提出的签名方案可以保障用户信息的安全、保护用户隐私。

4  实验验证及分析

4.1  评估实验参数设置

采用VC编写了一个模拟程序，用于测试几种能够实现完整性检测的算法CIDA^[9]，PoR^[11]，DPDP^[15]以及本文提出的算法DRDA在是否支持动态检测、服务器的计算复杂度、用户的计算复杂性及存储复杂度等属性进行比较。程序通过一台配置为Intel Pentium Dual E2180 2.00 GHz CPU、内存为1 GB、硬盘容量为160 GB的台式机进行运行，数据包大小变化，从1 kB开始，直到最大的128 kB，在通信开销上的最终值取50次运行结果的平均值。

4.2  实验结果及分析

表2所示为4种完整性检测算法在是否支持动态的完整性检测、计算过程中服务器端、可信第三方的计算复杂度及存储复杂度4个方面的不同数值。从表2可知，前面2种算法CID及PoR只适用于检测对象没有变化的情况，不适合对象动态变化的情况，而后面2种算法DPDP及DRDA则能很好地支持动态检测，具有更广泛的实用性。PoR由于不支持动态检测，不需要存储过多的数据，因此，具有较低的计算复杂度及存储复杂度，而后2种算法DPDP及DRDA支持动态检测，需要对数据的动态变化包括更新数据、修改数据及删除数据等操作进行验证，以便确认数据修改主体的合法性及数据的完整性，因而需要较大的计算复杂度。

表2 不同检测算法性能比较

Table 2  Performance of different detection algorithms

表3所示为2种主要的动态完整性检测算法DRDA及DPDP在CLIENT及SERVER 2端，在检测正确率、平均通信开销、验证数据完整性所需要的时间、对数据进行动态调整所需要时间等方面进行比较，从表3可知：2个方案的检测正确率均比较高，达到了98%以上，由于DRDA采用了优化的BLS短签名方案，计算复杂度较低，因而需要的平均通信开销比算法DPDP的要低，认证所需要的时间及动态数据操作所需要的时间比算法DPDP的要少。

图6所示为2种支持动态完整性检测的方案DPDP与DRDA在处理不同大小的数据包时所需要的通信开销的差异。从图6可见：在处理相同大小的数据包时，本文所提出的算法DRDA比DPDP所需要的通信开销要小；当数据包的大小接近18 kB和24 kB时，2种算法DPDP和DRDA所需要的通信开销是最小的，若超过这一数量，则通信开销增长较快，基本呈现线性增长的态势；当算法处理的数据包小于这一最小临界点时，则2种算法均能获得较低的通讯开销，具有较好的性能。

表3  不同检测算法数据包计算时间

Table 3  Time comparison of different detection algorithms

图6  不同算法开销比较

Fig. 6  Comparison of different algorithms

5  结论

1) 针对物联网环境中需要对远程数据进行有效管理的需求提出一种DRDA算法，该算法以双线性对验证为基础，以MHT作为存储结构，能够实现数据的动态完整性检测。

2) 该算法的实现只需要用户及服务器2个实体，不需要第三方参与，减少了模型及计算复杂性。

3) DRDA算法能进行远程、动态完整性检测，保护用户隐私信息、抵抗多种攻击。

4) DRDA算法在验证大小为24 kB左右的数据包时，所需要的通信开销最小；整体上来说，验证相同大小的数据包时，DRDA算法所需要的通信开销平均比DPDP要小40 kB，具有较好的计算性能。

参考文献：

[1] Chui M, Lffler M, Roberts R. The internet of things[J]. Mckinsey Quarterly, 2010, 2: 1-9.

[2] LIU Qin, WANG Guojun, WU Jie. Secure and privacy preserving keyword search for cloud storage[J]. Journal of Network and Computer Applications (JNCA), 2012, 35(3): 927-933.

[3] 朱炜玲, 喻建平. 物联网RFID系统隐私保护三方认证协议[J]. 深圳大学学报(理工版), 2012, 29(2): 95-99.

ZHU Weiling, YU Jianping. A privacy preserving three-party authentication protocol for RFID systems in the internet of things[J]. Journal of Shenzhen University (Science and Engineering), 2012, 29(2): 95-99.

[4] LIANG Xiaohui, LI Xu, SHEN Qinghua, et al. Exploiting prediction to enable secure and reliable routing in wireless body area networks[C]// Proceedings of the 31st Annual IEEE Conference on Computer Communications (INFOCOM2012), Orlando, Florida, USA: IEEE, 2012: 388-396.

[5] LIN Xiaodong, ZHU Haojin, LIANG Xiaohui, et al. Becan: A bandwidth-efficient cooperative authentication scheme for filtering injected false data in wireless sensor networks[J]. IEEE Transaction on Parallel and Distributed Systems, 2012, 23(1): 32-43

[6] Sarma S, Weis S A, Engels D W. RFID systems and security and privacy implications[C]// Proceedings of the 4th International Workshop on Cryptographic Hardware and Embedded Systems (CHES2002), Berlin: Springer-Verlag, 2003: 454-469.

[7] LI Tao, LUO Wen, MO Zhen, et al. Privacy-preserving RFID authentication based on cryptographically encoding[C]// Proceedings of the 31st Annual IEEE Conference on Computer Communications (INFOCOM2012), Orlando, Florida, USA: IEEE, 2012: 2174-2182.

[8] 谢磊, 殷亚凤, 陈曦, 等. RFID数据管理: 算法、协议与性能评测[J]. 计算机学报, 2013, 36(3): 457-470.

XIE Lei, YIN Yafeng, CHEN Xi, et al. RFID data management: algorithm, protocols and performance evaluation[J]. Chinese Journal of Computers, 2013, 36(3): 457-470.

[9] LI Chaoliang, WANG Guojun. A light-weight commodity integrity detection algorithm based on Chinese remainder theorem[C]// Proceedings of Trust, Security and Privacy in Computing and Communications (TrustCom2012), Liverpool, UK: IEEE, 2012: 1018-1023.

[10] 郭云川, 方滨兴, 殷丽华, 等. 一种面向移动计算的机密性与完整性模型[J]. 计算机学报, 2013, 36(7): 2024-2032.

GUO Yunchuan, FANG Binxing, YIN Lihua, et al. A security model for confidentiality and integrity in mobile computing[J]. Chinese Journal of Computers, 2013, 36(7): 1424-1432.

[11] Shacham H, Waters B. Compact proofs of retrievability[J]. Journal of Cryptology, 2013, 26(3): 442-483.

[12] Merkle R C. Protocol for public key cryptosystems[C]// Proceedings of IEEE Symposium on Security and Privacy. Piscataway, NJ: IEEE, 1980: 122-134.

[13] Okamoto T, Pointcheval D. The gap problems: A new class of problem for the security of cryptographic primitives[J]. Public Key Cryptography, PKC 2001, volume 1992 of LNCS, 104-118.

[14] Boneh D, Lynn B, Shacham H. Short signatures from the weil pairing[M]. Advances in Cryptology, Berlin: Springer, 2001: 514-532.

[15] Erway C, Kupcu A, Papamanthou C, et al. Dynamic provable data possession[R]. Proceedings of the 16th ACM Conference on Computer and Communication Security, New York: ACM, 2009: 213-222.

(编辑  邓履翔)

收稿日期：2014-02-02；修回日期：2014-05-06

基金项目(Foundation item)：国家自然科学基金资助项目(61073037，61272496，61272151)；教育部博士点基金资助项目(20110162110043) (Projects(61073037, 61272496, 61272151) supported by the National Natural Science Foundation of China; Project(20110162110043) supported by the Doctoral Foundation of Ministry of Education, China)

通信作者：李超良(1972-)，男，湖南湘潭人，博士研究生，从事物联网安全及隐私保护研究；电话：13975173138；E-mail: li_chaoliang@163.com