基于双向散列链具有撤销能力的自愈组密钥分发机制

《基于双向散列链具有撤销能力的自愈组密钥分发机制》由会员分享，可在线阅读，更多相关《基于双向散列链具有撤销能力的自愈组密钥分发机制（5页珍藏版）》请在装配图网上搜索。

1、第6期杜春来等：基于双向散列链具有撤销能力的自愈组密钥分发机制37基于双向散列链具有撤销能力的自愈组密钥分发机制杜春来1,2，胡铭曾2，张宏莉2，张冬艳2（1. 北方工业大学 信息工程学院，北京 100144；2. 哈尔滨工业大学 计算机网络与信息安全技术研究中心，黑龙江 哈尔滨 150001）摘 要：提出了一种MANET中基于双向散列链具有撤销能力的自愈组密钥分发机制。通过建立会话密钥之间的冗余关联，实现了在不增加管理节点负担的情况下，合法节点利用当前广播信息和自身秘密信息自主恢复由于网络原因遗失会话的组密钥。利用撤销多项式管理者实现了对节点的撤销能力，此外赋予节点与其生命期相对应的秘密掩码

2、值集合。安全分析和效率分析表明在保证安全属性的前提下，降低了通信开销和存储开销。关键词：组密钥发布；自愈；双向散列链；移动自组网中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2009)06-0033-05Self-healing group key distribution scheme with revocation based on dual directional hash chainDU Chun-lai1,2, HU Ming-zeng2, ZHANG Hong-li2, ZHANG Dong-yan2(1. College of Information En

3、gineering North China University of Technology, Beijing 100144, China;2. Research Center of Computer Network and Information Security Technology, Harbin Institute of Technology, Harbin 150001)Abstract: A self-healing group key distribution scheme with revocation in MANET using dual directional hash

4、chain was proposed. The association relation between different session keys was built. By means of broadcast information and own secrets, the legal nodes which lost some legal session keys due to network faults could be capable of recovering such lost session keys on their own, without requiring add

5、itional transmission from the group manager. The group manager could revoke the group nodes by revocation polynomial. Node was endowed with a set of masking secret according to its lifecycle. Through the security and efficiency analysis, the key distribution scheme reduces communication cost and sto

6、rage cost yet still achieves security property.Key words: group key distribution; self-healing; dual directional hash chain; MANET1 引言收稿日期：2008-06-21；修回日期：2008-12-01基金项目：国家高技术研究发展计划（“863”计划）基金资助项目（2007AA01Z446, 2007AA01Z442）Foundation Item: The National High Technology Research and Development Progr

7、am of China (863 Program)(2007AA01Z446, 2007AA01Z442)移动自组网(MANET, mobile ad hoc network)是一种在没有固定基础设施的条件下，由系统中的通信节点通过分布式协议互连起来的网络系统。在无线通信方式中，信号的物理覆盖能力使得某些通信节点需要借助其他节点作为中继转发信息才能实现有效通信。组密钥保证了无线网络中传输信息的安全。节点的移动性导致MANET的拓扑不固定，同时无线网络的窄带宽和节点的有限能量特性，使得无法将有线网络的安全研究成果直接应用在无线网络中，故此无线网络中的密钥管理是保证MANET安全的3大研究任务之一

8、1。在MANET中，组密钥具有很强的实效性。当某些节点因故暂时离开网络，当其再次连通的情况下，其本身所持有的组密钥已变更为历史组密钥，需要再次向相应管理节点提出申请。如果这类节点为了恢复中断期间错过的历史加密信息，需要向管理节点询问相关密钥信息，则会加重管理节点的负担，特别是当一定数量的合法用户同时重新连通时，在管理节点会造成局部时间内通信量增大，甚至阻塞脆弱的带宽，造成拒绝服务攻击现象。在移动自组网中，因各种原因节点不可避免地会出现不能连通的情况。在合法节点重新连通的情况下，如何降低出现如上现象的可能性？途径是减少重新连通的合法节点对管理节点的问询次数，也就是重新连通的合法节点仅仅从管理节点

9、获得当前组密钥信息，就可以借助自身的秘密和历史密钥的冗余信息获得遗失的组密钥，这就是密钥的自愈问题。目前这个方向在密钥管理领域处于一个新兴地位217。本文针对此问题提出了一种具有节点撤销能力的基于双向散列链结构的组密钥分发机制。在满足组密钥的可计算性、可撤销属性和自愈属性以及保证节点身份匿名性的同时，降低了网络的通信开销和用户的存储开销。2 国内外研究现状针对密钥的自愈问题，2002年Staddon 2首次提出了自愈的密钥分发机制，利用当前密钥信息中包含历史密钥冗余关联信息，使得重新连通节点不借助管理节点可以独立地恢复错过的密钥。与Staddon中秘密的掩码公式W(x)=f(x)+S(N,x)

10、需要发布tt掩码插值点矩阵不同，Liu3的掩码公式W(x)=g(x)f(x)+ h(x)中的掩码公式为h(x)，仅仅发布撤销节点集合R加t个插值点。以上2者的历史密钥的冗余方式相同，为p1(x),p2(x), pj(x),qj(x), qj+1(x),qm(x)。Blundo46提出方案的掩码公式zj=Kj+hj(0)，也需要发布t个插值点，但其历史密钥冗余方式为z1+ z2, , z1+ zj-1, zj，由此可以追溯历史所有的密钥信息。Hong7采用Liu的掩码方案，但其历史密钥冗余方式由Blundo5中的方式进化为p1(x)+p2(x),p2(x)+p3(x), , pj-2(x)+pj

11、-1(x), pj(x)。Germn Sez 8,9采用向量空间秘密共享机制来分发密钥和实现密钥自愈功能，将密钥掩码值Zj=Kj+(D)Tuj 在比特结构下一分为二成为Zj=(xj,yj)，构造广播冗余结构B1j=(Xj,Yj)，然后节点利用向量空间秘密共享原理获得当前及历史组密钥。Zou10对Aj(x)的设计，使合法节点从Wj(x)中提取到正确的Pj(x)，而非法节点会运算得到随机值，无法从Wj(x)中提取到正确的Pj(x)。More11提出了滑动窗口的密钥自愈机制，广播信息的正中间是当前密钥信息，前后扩展个会话的历史和将来密钥信息。Dutta1214不再将组密钥分成2个多项式之和，而是直接

12、对组密钥Kj进行掩码：j(x)=Aj(x)Kj+ (x, sidj)，在文献12中历史密钥关联冗余方式为1(x)+2(x),j-2(x)+j-1(x),j(x)，文献13,14中Kj=Ej(Kj-1)，广播的历史密钥关联冗余方式为EKj(1),EKj(j-1),EKj(j)，但文献14将密钥Kj掩码变更为j(x)=Aj(x)Kj+sidj(x)。在文献1517中都引入了双向散列链结构，文献15中将密钥分成两散列值之和：Kj=前向散列值+后向散列值，对后向散列值进行掩码，由于采用散列链结构，故不需要广播冗余密钥关联信息，在自愈过程中，只要做相应的散列就能得到相应的历史组密钥，从开销分析，优于以上

13、组密钥分发机制。文献16,17也引入了双向散列链结构，提出了基于时限的组密钥分发机制，从开销上也优于文献214中的机制，其另外还有一个用于密钥自愈的后向散列函数值列RKj，和相应前后向散列值共同作用生成相应的组密钥，由于RK是后向的，所以能保证恢复遗失的历史组密钥，但是RK序列是固定的，所以只能实现节点的被动时限撤销，在不重建RK序列的条件下，管理节点无法主动撤销。3 基于双向散列链的自愈密钥发布机制本文受文献10启发，但在保证安全的前提下效率高于文献10。设定MANET的会话数为m，t次多项式h(x)=a0+a1x+atxt(mod q)，x,aiFq, i=0,1,t，记H()为散列函数且

14、H(x) j=H(H(x) j-1)，同样规定H()的定义域和值域在有限域Fq中。3.1 双向散列链结构管理节点从有限域Fq中随机选择前向密钥种子(FS, forward seed)和后向密钥种子(BS, backward seed)，分别反复做散列运算得到2列散列值链：FHC (forward hash chain)和BHC(backward hash chain)。从图1可以看出，深色部分保证了小于t1时刻前向信息的安全性和大于t2时刻后向信息的安全性。组密钥等于2个散列链中对应会话的相应散列值之和，即Kj=H(FS)j+H(BS)m-j+1。只有获得同一会话相应的2个散列值才能计算得到相

15、应的组密钥。图1 双向散列链结构3.2 机制描述设节点集合U=u1,u2,un，节点ui的生命期记为LFil,v会话l,会话v，其中1lvm，限定每个会话的合法节点(不含撤销节点)的数目不大于t。1) 建立： 管理节点首先建立双向散列链结构(如图1所示)，选择m个独立不相关t次多项式h1(x),h2(x), hm(x)； 通过安全信道向节点ui发送赋予其的秘密身份Idi与其生命期相对应的秘密Si=hl(Idi),hl+1(Idi), hv(Idi)和SFKi=H(FS)l。2) 广播： 管理节点选择会话j的组密钥Kj=H(FS)j+H(BS)m-j+1；随机选择混淆数值Zj，设BKj=H(BS

16、)m-j+1设U=U撤销的节点，计算Aj(x)= Zj|U|i=1(xIdi)+1 uiU；计算Wj(x)=Aj(x) BKj+hj(x)； 广播Wj(x)。3) 组密钥的计算：节点ui接到会话j的广播信息Wj(x)后，利用自身秘密hj(Idi) 计算BKj=Wj(Idi) hj(Idi)/Aj(Idi)；计算当前会话的前向散列值FKj=H(SFKi)j-l=H(FS)j；Kj=FKj+BKj。4) 新节点加入： 节点ui在会话j期间加入MANET； 管理节点首先赋予其一个秘密身份Idi，计算并通过秘密信道向其发送秘密Si=hj(Idi),hj+1(Idi), hv(Idi)、Idi和SFKi

17、=H(FS)j。5) 密钥的自愈：生命期为j1,j3的节点ui会话j2中收到广播信息多项式Wj2(x)，当节点遗失会话j(j1 j j2j3)组密钥的情况下，通过如下过程可以恢复Kj。 从Wj2(Idi)中解得BKj2=H(BS)mj2+1，对BKj2反复做散列运算直到BKj=H(BKj2)j2j =H(BS)m-j+1； 利用自身所保存的前向散列值秘密计算会话j的前向散列值FKj=H(SFKi) j-j1=H(FS)j； Kj=FKj+BKj。4 安全及效率分析4.1 安全分析定理1 第3节提出的基于双向散列链的自愈密钥发布机制实现了密钥的自愈能力，保证合法节点正确计算密钥能力和管理节点的撤

18、销能力。证明 密钥的自愈能力显然可以从第3节密钥自愈部分的推导得出结论。同样，合法节点正确计算密钥能力显然可以从第3节密钥的计算部分得出结论。管理节点的撤销能力就是确保被撤销的节点不具有正确解算组密钥的能力，此时被撤销节点的生命期与当前会话存在交集，即节点在其生命期未结束的情况下被管理节点强制撤销。 设j1j3j4j5j2，生命期为j1,j2的节点ui在会话j4阶段被管理节点撤销，但ui希望参与会话j5的通信。由于ui在加入通信组的时候，获得管理节点通过安全信道发送的前向FKj1，对其做相应散列运算就可以得到会话j5的对应FKj5，故此ui能否获得BKj5就成为关键。如果利用已知的后向BKj3

19、推导BKj5，由于散列函数的不可逆性质，使之成为不可能。但由于ui拥有的秘密hj5(Idi)依然有效，故对广播信息Wj5(x)做运算Wj5(Idi)-hj5(Idi)提取Aj5(Idi) BKj5，至此ui能否解得正确的BKj5将取决于Aj5(Idi)的值是否为1。管理节点生成BKj5的系数多项式Aj5(x)=Zj5 |U|l=1(x-Idl)+1，式中的Zj5为混淆随机值，确保即使在组节点没有发生变化的情况下生成的系数多项式也不同。其有性质：当ujU时，Aj5(Idj) =1；反之ujU时，Aj5(Idj)1。由于被撤销节点ujU，故Aj5(Idi)1，于是无法从Aj5(Idi)BKj5中解

20、得正确的BKj5，进而解算得到错误的组密钥。管理节点的撤销能力得证。定理2 第3节提出基于双向散列链的自愈密钥发布机制实现了节点身份的匿名性。证明 节点ui在加入MANET时获得一个与之对应的秘密身份Idi，而非是公开标志ui；另外在广播公式中的系统多项式Aj(x)的构成采用当前非撤销节点，这样免去了以往文献中需要广播撤销节点标志而暴露节点身份信息的弊端，故本文提出的机制实现了节点身份的匿名性。4.2 效率分析4.2.1 广播的通信开销由于广播信息W(x)中系数多项式采用非撤销节点，所以不需要向MANET中的节点广播撤销节点信息，同时，由于采用了双向散列链结构，使当前和历史组密钥之间的关联关系

21、暗含在散列链结构中，通过双向散列链结构可推导合法的历史组密钥，故此省去了其他文献中需要传递的冗余密钥信息，于是管理节点产生的广播信息仅仅为W(x)，其广播通信开销为O(t+1)lgq)。4.2.2 节点的存储开销生命期为LFil,v的节点ui在加入MANET时，管理者通过安全信道向其传送被赋予的秘密身份Idi与其生命期相对应的秘密掩码值Si=hl(Idi),hl+1(Idi), hv(Idi)和SFKi；故节点存储开销为O(v-l+3)lgq)。4.2.3 效率对比表1给出了本文密钥分发机制与其他机制的效率对比，文献17与HBT树结构结合，故不参与对比，文献16从节点的撤销方式来看，仅仅为时限

22、退出，故不参与对比。从表1中可以看出本文提出的机制有很好的通信开销和存储开销，具体为：通信开销优于除文献15外的其他机制，但由于节点仅仅存储与其生命期对应的信息，故此存储开销优于文献15中的机制。表1效率对比机制列表通信开销节点存储开销文献2(mt2+2mt+m+t)lgq(m-j+1)2lgq文献3(m+j+1)t+(m+1)lgq2(m-j+1)lgq文献4(jt+jt2)lgqmlgq文献5(2tj+j)lgq(m-j+1)lgq文献7(tj+j-t-1)lgq(m-j+1)lgq文献81+(t+1)(m-1-t/2)lgq(m-j+1)lgq文献9t(m2-m+2)/2lgqt(m-j

23、+1)lgq文献102j(t+1lgq2lgq文献11(t2+t)lgqmilgq文献12(tj+j-t-1)lgq(t+1)lgq文献13(t+1+j)lgq3lgq文献14(t+j)lgq(t+1)lgq文献15(t+1)lgq(m-j+1)lgq本文机制(t+1)lgq(v-l+3)lgq5 结束语针对MANET的自愈密钥问题，本文提出了一种MANET中基于双向散列链具有撤销能力的自愈密钥分发机制。采用密码学中的“一次一密”思想，针对一个会话密钥唯一对应一个掩码多项式。由于采用了散列链结构，将密钥之间的关联关系建立在其上，即利用散列结构的特性隐含了密钥之间的关联关系，使得在广播信息中不存

24、在明显的广播密钥关联冗余部分，减少了通信量。同时在撤销系数多项式中用非撤销节点取代撤销节点，故不需要广播撤销节点信息，在减少通信量的同时，实现了节点的匿名性。安全分析和效率分析表明在保证安全属性的前提下，降低了通信开销和存储开销。参考文献：1胡华平, 胡光明, 董攀等. 大规模移动自组网络安全技术综述J. 计算机研究与发展, 2007,44(4):545-552. HU H P, HU G M, DONG P, et al. Survey of security technology for large scale MANETJ. Journal of Computer Research an

25、d Development, 2007,44(4): 545-552.2STADDON J, MINER S, FRANKLIN M, et al. Self-healing key distribution with revocationA. Proceedings of the 2002 IEEE Symposium on Research in Security and Privacy (S&P02)C. Berkeley, CA, 2002. 241-257.3LIU D G, NING P, SUN K. Efficient self-healing group key distri

26、bution with revocation capabilityA. Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS 2003)C. Washington, DC, United States, 2003. 231-240.4BLUNDO C, DARCO P, LISTO M. A new self-healing key distribution schemeA. Proceedings of the 8th IEEE Symposium on Computers an

27、d Communications (ISCC2003)C. Antalya, Turkey, 2003. 803-808.5BLUNDO C, DARCO P, LISTO M. Design of self-healing key distribution schemes J. Designs, Codes and Cryptography. 2004, 32(1-2):15-44.6BLUNDO C, DARCO P, DE S A. On self-healing key distribution schemesJ. IEEE Transactions on information Th

28、eory, 2006, 52(12):5455-5467.7HONG D, KANG J S. An efficient key distribution scheme with self-healing propertyJ. IEEE Communications Letters, 2005, 9(8): 759-761.8SEZ G. On threshold self-healing key distribution schemesA. Proceedings of Cryptography and Coding 2005C. Cirencester, United Kingdom, 2

29、005. 340-354.9SEZ G. Self-healing key distribution schemes with sponsorizationA. Proceedings of CMS 2005C. Salzburg, Austria, 2005. 22-31.10ZOU X K, DAI Y S. A Robust and Stateless self-healing group key management schemeA. Proceedings of ICCT 06C. Guilin, China, 2006. 1-4.11MORE S M, MALKIN M, STAD

30、DON J, et al. Sliding-window self-healing key distributionA. Proceedings of the ACM Workshop on Survivable and Self-Regenerative Systems (In Association with 10th ACM Conference on Computer Communications Security)C. Fairfax, VA, United States, 2003. 82-90.12DUTTA R, MUKHOPADHYAY S. Designing scalab

31、le self-healing key distribution schemes with revocation capabilityA. Proceedings of ISPA2007C. Niagara Falls, ON, Canada, 2007. 419-430.13DUTTA R, WU Y D, MUKHOPADHYAY S. Constant storage self-healing key distribution with revocation in wireless sensor networkA. Proceedings of ICC07C. Glasgow, Scot

32、land, United Kingdom, 2007. 1323-1328.14DUTTA R, MUKHOPADHYAY S. Improved self-healing key distribution with revocation in wireless sensor networkA. Proceedings of 2007 IEEE Wireless Communications and Networking Conference, WCNC 2007C. Kowloon, China, 2007. 2965-2970.15DUTTA R, CHANG E C, MUKHOPADH

33、YAY S. Efficient self-healing key distribution with revocation for wireless sensor networks using one way key chainsA. Proceedings of ACNS2007C. Zhuhai, China, 2007. 385-400.16JIANG Y X, LIN C, SHI M H, et al. Self-healing group key distribution with time-limited node revocation for wireless sensor

34、networksJ. Ad Hoc Networks, 2007, 5(1):14-23.17SHI M H; SHEN X M, JIANG Y X, et al. Self-healing group-wise key distribution schemes with time-limited node revocation for wireless sensor networksJ. IEEE Wireless Communications, 2007, 14(5): 38-46.作者简介：杜春来（1975-），男，河北涞水人，北方工业大学讲师，主要研究方向为网络与信息安全、移动自组网络。胡铭曾（1935-），男，江苏江阴人，哈尔滨工业大学教授、博士生导师，主要研究方向为高级系统结构、并行计算与网络安全。张宏莉（1973-），女，吉林榆树人，哈尔滨工业大学教授、博士生导师，主要研究方向为网络与信息安全、网络测量与仿真、网格计算。张冬艳（1975-），女，黑龙江哈尔滨人，哈尔滨工业大学副教授、硕士生导师，主要研究方向为计算机网络与信息安全。