MANET节点不相交多路径安全源路由协议(

《计算机学报》2009年6期MANET节点不相交多路径安全源路由协议冯涛1，2)郭显1，3)马建峰2)李兴华2)1)（兰州理工大学计算机与通信学院，兰州，730050）2)（西安电子科技大学计算机网络与信息安全教育部重点实验室，西安，710071）3)（甘肃联合大学数学与信息科学学院，兰州，730010）摘要：多路径路由实现是移动Adhoc网络(MANET)可靠运行的有效保证。现有MANET节点不相交多路径路由协议主要关注节点不相交多路径的可实现性和效率问题。针对节点不相交多路径路由协议MNDP协议在主动攻击者安全模型中的安全缺陷，提出了可证明安全的MANET节点不相交多路径动态源路由协议SMNDP协议。SMNDP协议路由请求算法中，建立了中间节点路由请求消息传播策略的检错机制、SMNDP协议路由应答算法中建立了消息防篡改机制和身份认证机制。基于攻陷的网络拓扑模型，扩展了可模糊路由概念，提出了多路径可模糊路由集合概念和节点不相交多路径源路由协议的安全定义，并应用于SMNDP协议的安全分析。SMNDP协议的安全性可以归约为消息认证码和签名机制的安全性。关键词：MANET；MNDP；可证明安全；可模糊路由；SMNDP中图法分类号:TP309MultipleNode-DisjointPathsSecureSourceRoutingForMANETFengTao1,2),GuoXian1,3),MaJian-feng2),LiXing-hua2)1)(SchoolofComputerandCommunication,LanzhouUniversityofTechnology,Lanzhou,730050,China)2)(MinistryofEducationKeyLaboratoryofComputerNetworksandInformationSecurity,XidianUniversity,Xian710071,China)3)(SchoolofComputerandMath,GansuLianheUniversity,Lanzhou730010,China)Abstract:Theimplementationofmultipathroutingprovidesguaranteeforreliablerunningofmobileadhocnetwork(MANET).Mostofexistingnode-disjointmultipathroutingfocusesmainlyonestablishmentissuesofmultiplenode-disjointpathsandefficiencyissuesofidentifyingmultiplenode-disjointpaths.MultipleNode-DisjointPaths(MNDP)hassecurefaultsinthesecuremodelofactiveadversary.Toaddressthisissue,aprovablySecureMultipleNode-DisjointPathssourcerouting(SMNDP)isproposedinthispaper.Error-checkschemeisusedforthetransmissionoftheroutequestinthealogrithmofrouterequestforSMNDP.Inaddition,theschemessuchasthemessageauthenticationandthedigitalsignatureareusedinthealgorithmofroutereplyforSMNDP.Theconceptofplausiblerouteisextendedinthispaper,andthedefinitionof收稿日期:2008--.本课题得到国家“八六三”高技术研究发展计划项目基金(2007AA01Z429)、国家自然科学基金(60573036、60633020、60702059)、甘肃省自然科学基金（2007GS04823）、兰州理工大学博士基金资助.冯涛,男,1970年生,博士,教授,主要研究兴趣为安全协议复合理论,无线传感器网络安全,Email:[e-mail];郭显,男,1971生,博士生,讲师,主要研究兴趣为Adhoc网络安全,Email:[e-mail];马建峰,男,1963生,博士生导师,教授,主要研究领域为计算机安全,密码学，移动与无线网络安全。2计算机学报plausible-routesetisgiven.Andthen,securitydefinitionofmultiplenode-disjointpathsroutingispresented.ThesecurityofSMNDPcanbereducedtothesecurityofthemessageauthenticationcodeandthedigitalsignature.Keywords:MANET,MNDP,provablysecure,plausibleroute,SMNDP.1引言多路径路由实现是移动Adhoc网络（MANET）可靠运行的有效保证。为改进网络的可靠性和吞吐量，多路径路由协议成为近几年MANET邻域的研究热点。多路径路由可以分为3种：节点不相交（Node-Disjoint）多路径、链路不相交（Link-Disjoint）多路径和相交多路径。节点不相交多路径因其各条路径中除源节点和目的节点之外没有其他任何共用节点，因此与链路不相交多路径和相交多路径相比具有更强的容错能力和负载平衡能力。基于流网络（flownetwork）理论，Liu等[1]提出了实现MANET节点不相交多路径集合的新方法，利用多次路由发现协议，设计了k条节点不相交路径的动态源路由协议MNDP（MultipleNode-DisjointPaths）协议。然而，MNDP协议主要关注节点不相交多路径的可实现性和效率问题而没有考虑安全问题，如果存在主动攻击者，该协议不能抵抗active-n-m攻击[2]。安全路由是MANET重要的安全需求，目前提出的几个多路径“安全”路由算法试图解决安全问题，如SecMR[3]、SRP[4]等。然而，都没有用严格的数学方法分析这些协议的安全性而关注的仍是多路径实现问题。文献[4]虽用形式化方法（BAN逻辑）分析了SRP协议的安全性，但文献[5]对SRP协议分析发现，SRP仍存在安全缺陷，并且已证明，路由协议的安全性不经过严格的数学证明是不可靠的。针对无线Adhoc网络，基于攻陷的网络拓扑模型，本文扩展了可模糊路由概念[5-6]，提出了多路径可模糊路由集合概念和节点不相交多路径路由协议的安全定义；基于MNDP协议，提出了MANET节点不相交多路径动态安全源路由协议SMNDP协议。SMNDP协议计算辅助路径的路由请求算法中，建立了中间节点路由请求消息传播策略检错机制；SMNDP协议路由应答算法中，建立了消息的防篡改机制和认证机制。SMNDP协议的安全性可以归约为消息认证码和签名机制的安全性。2节点不相交多路径源路由协议的安全定义2.1攻击者的能力模型通过控制攻陷节点，攻击者能够阻止路由协议完成协议需求的功能。本文假设攻击者能力模型为：1、节点之间用身份相互认证，Sybil攻击无效；2、节点仅能够接收到通信信号强度范围内的其他节点传输的信息，Wormholes攻击无效；3、路由发现过程的源节点和目标节点未被攻陷。攻击者不能修改或控制未攻陷节点之间的所有通信消息；4、攻击者通过攻陷节点实施攻击，并可以使用攻陷节点的所有秘密信息；5、当攻陷节点相邻时，攻击者能用任意攻陷身份假冒这些相邻节点。2.2基于攻陷的网络拓扑模型讨论MANET路由协议之前，假定网络3冯涛等:MANET节点不相交多路径安全源路由协议节点通过邻居发现协议已建立了网络拓扑，实现了MANET的安全自举[7]。基于攻击者能力模型，MANET拓扑模型的无向图G(V,E)可以定义为一个构造(Configrations)[5-6]，简称构造conf，如图1。u*v*gh{F}fedcba{H}{G}{E}{A}{B}{C}{D}{X,Y,Z}{X,Y,Z}图1网络构造根据无线通信链路特点和邻居发现协议，如果能在两个未攻陷节点之间建立无线链路，那么与这两个未攻陷节点相对应的顶点u和v之间有一条边；如果能在一个未攻陷节点和攻陷节点集合V*中的某攻陷节点之间建立一条无线链路的话，那么未攻陷节点和攻陷节点相对应的顶点u和v*之间也有一条边。两个相邻攻陷节点u*和v*之间没有边，它们被看成了攻陷顶点集合V*中的单一顶点。用L表示身份集合，L*表示攻陷身份集合，用身份分配函数D：V→2L（2L是L的幂集）给V中的每个顶点分配身份标识。身份分配函数D定义如下：v∈VD(v)=*lvVLv**\VV，其中l∈L\L*用三元组(G(V,E),V*,D)表示构造conf，假设存在攻击者，那么实黑顶点表示V*中的攻陷顶点（V*中的顶点在图G中不相邻），每个顶点用函数D分配给它的身份集合作标记。实际上，路由协议是该静态网络构造conf上的分布式算法，由于相邻攻陷节点看成了单一攻陷节点，构造conf上的顶点不相交多路径路由协议实际上是指未攻陷节点和不相邻攻陷节点不相交多路径路由协议。2.3可模糊路由集合图1中的身份序列{A,X,E,D}，{A,X,Y,E,D}，{A,X,Y,Z,E,D}等是顶点a,d之间同一条路径路由{a,u*,e,d}，主动攻击者能够使用L*中的所有身份，使身份序列路径路由与顶点序列路径路由不一致。为实现conf上的身份序列路径路由与真实存在的路径路由一致，文献[5-6]建立了可模糊路由概念，本文扩展了可模糊路由概念，提出了多路径可模糊路由集合概念。定义1：可模糊路由（plausibleroute）：假设构造conf=(G(V,E),V*,D)，l1，l2，…，ln是身份序列，如果存在V中的顶点序列v1，v2，…，vk（2≤k≤n）和正整数序列j1，j2，…，jk使得⑴j1+j2+…+jk=n；⑵{1iJl+，2iJl+，…，iiJjl+}D(Vi)（1≤i≤k），如果i=1，Ji=0，如果i1，Ji=j1+j2+…+ji-1；⑶(vi，vi+1)∈E（1≤i≤k）。则称身份序列l1，l2，…，ln是一条可模糊路由。图1中的身份序列{l1,l2,l3,l4,l5,l6}={A,X,Y,Z,E,C}是可模糊路由，因为该序列可被划分成{A}，{X,Y,Z}，{E}和{C}四部分，使得{A}D(a)，{X,Y,Z}D(u*)，{E}D(e)，{C}D(c)，顶点序列a，u*，e和c构成图G中一条简单路径，该例中k=4，j1=1，j2=3，j3=1，j4=1；那么J1=0，J2=j1=1，J3=j1+j2=4，J4=j1+j2+j3=5，因此该身份序列路由{l1,{l2,l3,l4},l5,l6}满足可模糊路由的定义。定义2：可模糊路由集合（plausible-routeset）：对任意构造conf=(G(V,E),V*,D），假设P是图G中任意一对顶点u，v之间多路径路由的集合，如果P满足以下条件：⑴任意pi∈P，pi是一条可模糊路由；⑵任意pi，pj∈P（i≠j），与pi和pj对应的顶点集合分别是Vi和Vj，并且4计算机学报(ViVj)\{u，v}=Φ，即pi和pj是两条除顶点u、v外，顶点不相交的可模糊路由。则称P是顶点u，v之间的可模糊路由集合。如图1中，{{A,G,H,X,Y,Z,F,D}，{A,X,Y,Z,E,D}，{A,B,C,D}}是顶点a和d之间的可模糊路由集合，除源顶点a和d外，它们分别与图1中顶点不相交路径{a,g,h,v*,f,d}、{a,u*,e,d}、{a,b,c,d}对应。2.4路由协议的安全定义定义3：如果对任意构造con