LightWeightNetworkCodingbasedKeyDistribution.doc

精品論文light weight network coding based key distributionscheme for manetsjianwei liu1, abdur rashid sangi1, ruiying du2, qianhong wu25(1. school of electronics & information engineering, beihang university, beijing 100191;2. school of computer science, wuhan university, wuhan 430072)abstract: along with other advantages, throughput enrichment is considered a main advantage provided by network coding. it is a lightweight, efficient, easy to implement technique that can be used to resolve security related issues in resource constraint wireless ad hoc networks. to utilize the10advantages of network coding, we present a lightweight key distribution scheme based on inherent security property of network coding. our novel scheme is a combination of simple xor network coding operations and message authentication codes (macs) to achieve data confidentiality and guarantee the integrity of the distributed keys, respectively. a thorough security analysis is given toexplain the effectiveness of our scheme against eavesdropping and impersonation attacks as well as15with few reasonable assumptions, it could withstand more intelligent attacks i.e. node compromising and brute force attacks. this scheme requires adequate amount of memory and we have also discussed memory aspects of our scheme. simulation analysis proved that while key exchange between two nodes in same cluster, this scheme achieved more than 95% key delivery ratio with an ignorable average delay of 2 m.s. 58% key delivery ratio was achieved while the key was exchanged between20two nodes in different clusters and the average delay was around 10 m.s.keywords: network coding; key distribution scheme; message authentication code (mac); wireless ad hoc network; network simulator-2.0introduction25since network coding approach was first proposed by r. ahlswede, li, cai and yeung in their pioneering work in 2000 1, few further studies have begun to investigate how to exploit the network coding idea to design secure lightweight protocols for a lot of applications. a few of papers deal with network coding security problems. l. lima, j. p. vilela, p. f. oliveira and j. barros discussed the attacks and countermeasures in wireless network coding 2. j. dong et al30identify some security threats and challenges in several network coding-based systems proposed for unicast in wireless network3. p. f. oliveria and j. barros proposed a secret key distribution protocol for wireless networks based on network coding4 and c. gkantsidis and p.r. roddriguez proposed a large scale contents distribution scheme 5 in network scenarios. j. p. vilela, l. lima and j. barros proposed a low-complexity cryptographic scheme6 based on random linear network35coding 7. z. yu, y. wei, b. ramkumar and y. guan proposed an efficient xor network coding scheme to combat against pollution attacks8. s. jaggi, m. langberg, s. katti, t. ho, d. katabi, and m. medard proposed the algorithms to resist byzantine attacks9.while in mobile ad hoc network, its dynamic network topology, multi-hop, decentralized and self-organizing properties pose even more serious security challenges than those in static40networks10. one of the most important problems is how to distribute and update secret keys toensure secure communication among all participating nodes. a network coding-based protocol is proposed for wireless sensor network11. in this scheme, the authors suppose that there is a mobile node in the static sensor network. obviously, the scheme can not meet the security requirements in ad hoc network, because all nodes in ad hoc network are mobile, and so-called neighbors of any45node are not fixed any more.foundations: specialized research fund for the doctoral program of higher education (no. 20091102110004); national basic research program of china (973 program) foundation(no.2012cb315905)brief author introduction:liu jianwei, (1964 -), male, professor and doctoral supervisor. main research:security of wireless and mobile communication network and computer network. e-mail: - 15 -figure 1 shows a cluster-based topology of a general multi-hop wireless ad hoc communication network, where the black dots indicate the clusterheads and the black linesindicates the communication route from node a to node b.50fig.1 manets cluster-based topology.fig.2 a hierarchical network topologyin this paper, we propose a new key distribution scheme for mobile ad hoc network. our scheme is based on network coding paradigm. the scheme allows any pair of node to setup a shared key through a multi-hop route, efficiently.55our scheme adopts a trusted third party (ttp) to pre-install a secret key and all padded key materials of the other nodes to each ad hoc node in the initialization stage. each node only knows its own secret key. besides, it also keeps an encrypted version of keys of all other nodes pre-installed by ttp in the initialization stage. after the initialization stage, end-to-end key distribution can be performed efficiently based on network coding paradigm.60memory requirement is an overhead but without storing these secret keys, this scheme would needs an online mechanism to distribute these secret keys when required. burden to include data communication in resource constraint network would be more as compared to the nominal memory that our scheme require on each node. memory advancements are introduced frequently and it is becoming easy to install a big amount of compact memory day by day.65we did not find an exact similar technique that used cluster topology, network coding and message authentication code to devise key distribution scheme. authors in 4 11 proposed a key distribution scheme that uses network coding. unlike this scheme, our scheme requires less memory space on each participating nodes and does not expect a mobile (super) node to bootstrapthe participating network nodes.70the rest of the paper is organized as follows: we explain the symbols we use in the paper in section ii, and security model as well as some reasonable assumptions in section iii. we propose our scheme in section iv and analyze its security and performance in section v. section vi concludes the paper.1notation and symbol75before we begin to describe our proposed schemes, we explain the symbols used in the paper.table 1 lists the symbols and their corresponding meanings in our scheme.80tab.1 notation and symbols.symbol descriptionki idi aij h(x)rimacithe secret key of i-th ad hoc node the identifier of i-th ad hoc noderandom number between i-th and j-th ad hoc node generated by ttpsecure hash function used to generate a macrandom challenge generated by i-th ad hoc node message authentication code using i-th nodes key| message concatenation operationh lp, | p |l-th clusterheadglobal key pool and its size859095100105110115nmaximum number of ad hoc nodessk shared secret key between two ad hoc nodes2security model2.1 network topology modelwe consider a cluster-based ad hoc hierarchical network topology. a subset of the network nodes is selected to serve as the network backbone over which essential network control functions are supported. the approach to topology control is often called clustering, and consists of selecting a set of clusterheads in a way that every node is associated with a clusterhead, and clusterheads are connected with each other directly or by means of gateways, so that the union of gateways and clusterheads constitute a connected backbone. once elected, the clusterheads and the gateways help reduce the complexity of maintaining topology information, and can simplify such essential functions as routing, bandwidth allocation, channel access, power control or virtual-circuit support. for clustering to be effective, the links and nodes that are part of the backbone (i.e., clusterheads, gateways, and the links that connect them) must be close to minimumand must also be connected 12.from figure 2, we can learn that each clusterhead has control ability over all the other normal nodes within the cluster. the clusterheads are connected with each other to perform traffic delivery among nodes in different clusters. the characteristics of cluster-based topology of ad hoc network can be leveraged to distribute secret keys based on network coding paradigm.2.2 network topology modelwe consider the security threats posed by an attacker in ad hoc network have the following characteristics:1) it can eavesdrop every wireless link in the network;2) it has full access to all data traffic and can perform analysis upon receiving the traffic.3) it knows all the cryptographic algorithms used in the network, but it has limited computing resources and thus unable to break the cryptographic primitives.4) it can inject bogus traffic, and modify traffic to launch impersonation attack.5) it can capture some ad hoc nodes and extract authentication/encryption keys from the compromised nodes.our goal is to design a network coding-based scheme that can efficiently set up a secret key between two communication nodes, or set up a conference key among a group of nodes. we particularly address that the 2-layer topology should be adopted for ad hoc network, which can be greatly benefited from xor operations in network coding paradigm.1201251301351401451501552.3 initial assumptionswe make some reasonable assumptions for the scheme.1)in the initialization stage, there exists an offline trusted third party (ttp) in the network.2)each ad hoc node has enough memory to store all the encrypted keys of all network nodes.3)one clusterhead knows all identifiers of nodes within its jurisdiction and can route the traffic to other clusterhead, and the latter will deliver the data to the designated node in the other cluster.clearly, the first and the third assumptions are not difficult for us to understand. some people may argue that the second assumption seems unreasonable, because terminals of ad hoc network have limited memory resource. actually, unlike wireless sensor network, mobile ad hoc network usually has limited number of nodes under some military or industry scenarios, i.e., military rescue action and geological prospecting and exploration. we suppose that the secret key size is of128 bits (16 bytes), and the node identifier is of 16 bits (2 bytes, which can represent to themaximum 65536 ad hoc nodes), then the memory needed at each node to store the secret keys for such big number of nodes would only be approximately 1m bytes. it is obviously affordable for a mobile ad hoc node with the technical advancement of storage device.3key distribution scheme using network coding for manetsthe in this section, a new key distribution scheme is proposed based on network coding paradigm. as the xor operations are used in the scheme, so it requires only a few lightweight computations and provides a level of security of probabilistic key sharing scheme13. in the following paragraph, we will describe 3 phases in detail.3.1 the framework for key distribution in ad hoc networkbefore describing our proposed scheme, we first propose a framework for securely distributing secret keys in mobile ad hoc network.our proposed scheme includes 3 phases. the first one is the initialization phase. the second one is the key distribution phase. and the third one is the key updating phase.- initialization phase: in this phase, we suppose there is an offline trusted third party (ttp) in ad hoc network, which is responsible to setup security parameter, such as generating secret key for each node, and choose cryptographic hash functions and algorithms. the ttp will initialize every ad hoc node and injects the security data into its memory. once this phase is finished, all network nodes are ready for deployment.- key distribution phase: two kinds of protocols will be executed based on whether two communication nodes belong to a same cluster or not. if the two nodes belong to the same cluster, then key distribution can be easily done by the aid of the clusterhead. whereas, if the two nodes belong to different clusters, the key distribution will be realized by the aid of two different clusterheads, which take the effect of gateways.- key updating phase: when ad hoc network topology changes dynamically or there are newnodes entering the network, new keys should be securely and efficiently distributed. when an ad hoc node wants to update its current secret key, it needs to send an update request to its clusterhead. then key updating procedure will be executed with the aid of clusterheads.3.2 detailed procedure of our key distribution schemewe assume that 2-layer hierarchical topology model is adopted, and the clusterheads can be160165170elected through a recommendation algorithm automatically12, and every ad hoc node is associated with a clusterhead. thus, once any pair of node wants to setup a common secret key and communicate securely, they must first contact their own clusterheads. the clusterheads with the help of gateways can compute and deliver data between the two communication nodes.there are two cases here.in the first case, both nodes are associated with one same clusterhead. in the second case, both nodes are associated with two different clusterheads. therefore, we will propose two different key distribution protocols to meet the above two cases. case 1: both ad hoc nodes belong to the same clusterhead.fig.3 protocol for two ad hoc nodes associated with the same clusterhead.- initialization phase: the offline ttp in the network generates a secret key k i p , where p isthe large key pool generated by ttp, and the corresponding identifiersid i , i 0 , l , n 1 foreach ad hoc node. ttp stores a list of an encrypted version of the other nodes keysk j a ij , j = 0 , l , i 1 , i + 1 , l , n 1(notice thata ij = a ji) into nodeialone with all175180corresponding identifiers of the ad hoc nodes. then ttp choose a secure hash function h ( x ) .note that, after the initialization phase, each node only knows its own secret key and the encrypted version of other nodes. this will minimize the risk of secret key leakage when one node is captured and compromised.- key distribution phase: after ad hoc node deployment, there are two cases that have alreadybeen mentioned above.1) nodea sendsachallengerandomra ,amessageauthenticationcodemac a = h ( ra | k a ( k b a ab )andida , idbto its clusterheadhl , l 1,l, n , wheren is the current maximum number of clusterheads in ad hoc network.2) when clusterhead h lreceive the message from node a , it first checks ifnode a and185node b are associated with it.if the two nodes belong to the same cluster, thenh l recordsra , maca , ida , idband deliversida , idbto node b.3) when node b receivesida , idb , node b knows that a wants to communicate with it.then it sends a challenge random rbandmac b = h (rb | k b ( k a a ab )to h l .4) h lfirst performs a simple table look-up and then uses network coding paradigm to broadcast190the value ofra rb | mac a mac b .r r r = r 5) uponreceivingthemessage,nodea computesaabbandmac a mac a mac b = mac b , and then computesmac b = h(rb | k a ( k b a ab ) ;r r r = r mac mac mac = macnode b computesbaba andba b a , and thencomputesmaca = h(ra | kb (ka aab) .1956) nodea verifies to confirm ifmacb = macb; node b verifies to confirm ifmaca = maca .if they are equal, then both node a and node b will compute a sharedsk = h(ka kb aab | ra | rb)secret key.case 2: both ad hoc nodes belong to two different clusterheads. figure 4 shows the protocol.1) node a initiates the protocol by sending a challenge randomra , a message authentication200codemac a = h ( ra | k a ( k b a ab )andida , idbto its clusterheadhl , l 1,l, n .this step is same as that of the first protocol.205fig.4. protocol for two ad hoc nodes associated with two differ