Chinese Journal of Computers   Full Text
Title	Multiple Node-Disjoint Paths Secure Source Routing for MANET
Authors	FENG Tao1),2) GUO Xian1),3) MA Jian-Feng2) LI Xing-Hua2)
Address	1)(School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050) 2)(Key Laboratory of Computer Networks and Information Security of Ministry of Education, Xidian University, Xi’an 710071) 3) (School of Computer and Mathematics, Gansu Lianhe University, Lanzhou 730010)
Year	2009
Issue	No.6(1126—1133)
Abstract &   Background	Abstract The implementation of multipath routing provides guarantee for reliable running of mobile Ad hoc network (MANET). Most of existing node-disjoint multipath routing focuses mainly on establishment issues of multiple node-disjoint paths and efficiency issues of identifying multiple node-disjoint paths. Multiple Node-Disjoint Paths (MNDP) has secure faults in the secure model of active adversary. To address this issue, a provably Secure Multiple Node-Disjoint Paths source routing (SMNDP) is proposed in this paper. Error-check scheme is used for the transmission of the route quest in the algorithm of route request for SMNDP. In addition, the schemes such as the message authentication and the digital signature are used in the algorithm of route reply for SMNDP. The concept of plausible route is extended in this paper, and the definition of plausible-route set is given. And then, security definition of multiple node-disjoint paths routing is presented. The security of SMNDP can be reduced to the security of the message authentication code and the digital signature. Keywords MANET； MNDP； provably secure； plausible route； SMNDP Background Routing is a basic functionality for multi-hop mobile ad hoc networks (MANETs). These networks are decentralized, with nodes acting both as hosts and routers, forwarding packets for nodes that are not in transmission range of each other. Generally, routing is classified into two main classes: single-path routing and multi-path routing. Compared with single-path routing, multi-path routing has advantages in fault-tolerance and load sharing etc. So, multi-path routing has recently attracted extensive attentions. We are mainly concerned with the security of multiple node-disjoint paths, because security is also one of important problems for MANETs. There is no algorithm till date that claims to identify a maximal set of node-disjoint paths between a given source and a destination in a single route discovery. In fact, Ash et al. have proved that computing a maximal set of node-disjoint paths, from a list of paths traversed by different copies of a route request query, either at the source or at the destination, is an NP-complete problem. Based on flow-network theory, Liu et al. proposed a new method that identifies the maximal set of node-disjoint paths and designed a Multiple Node-Disjoint Paths routing called MNDP. MNDP computes node-disjoint paths in multiple route discoveries and in an incremental fashion. However, if there exists the active adversary, MNDP can’t defend against active-n-m attack, it focuses mainly on efficiency problem and implement of multi-path routing. To address the security issue, we propose a provably Security Multiple Node-Disjoint Paths (SMNDP) source routing based on MNDP. In SMNDP, we introduce error-check and cryptographic mechanisms. These two schemes provide guarantees to identify node-disjoint paths even if there exists the active adversary in the network. We analyze the security of SMNDP with a rigorous mathematical method. This work is supported by the National Natural Science Foundation of China under grant Nos.60573036, 60633020, 60702059, National High Technology Research and Development Program (863 Program) of China under grant No.2007AA01Z429 and the Natural Science Grand Foundation of Gansu No.2007GS0482, the Ph.D. Programs Foundation of Lanzhou University of Technology No.BS14200901.