Abstract
The establishment of a Public Key Infrastructure(PKI) in Mobile Ad Hoc Networks (MANETs) is considered adifficult task because of the intrinsic characteristics of thesenetworks. The absence of centralized services and the possiblenetwork partitions make traditional security solutions notstraightforwardly applicable in MANETs. In this paper, wepropose a public key management scheme based on a binary treeformation of the network’s nodes. Using the binary treestructure, certificate chains are easily built betweencommunicating nodes that are multi-hops away and thecumbersome problem of certificate chain discovery is avoided.We argue that our mechanism has several advantages oversimilar solutions, especially when a fair balancing betweensecurity and performance is terminus.
I. INTRODUCTION
Mobile ad hoc networks (MANETs) are currentlyemployed in many areas of interest and their self-organizednature is a challenge for researchers who wish to implementgeneral-purpose protocols in these networks. While manyrouting protocols have been proposed in the literature forMANETs the establishment of a public key infrastructure(PKI) in these networks has gathered little attention so far.The absence of any fixed infrastructure and centralizedauthorities makes public key management for MANETs avery difficult task from both an algorithmic and computationalpoint of view. The main problem of any public key basedsecurity system is to make the public key of a node availableto another by proving in the same time the authenticity of thiskey. The solution to this problem in wired, general-purposenetworks comes from the use of on-line or off-line servers thatissue certificates to the nodes of the network. In MANETs theabsence of centralized services and the possible networkpartitions makes this problem very difficult. Recently, somepublic key management schemes for MANETs have beenproposed. These schemes are classified in two categories. Thefirst approach uses a set of nodes as servers which can providepartial certificates to a combiner by utilizing the concepts ofthreshold secret sharing [2]-[4]. The second category is basedon the web of trust approach [5],[6]. In this approach, everynode issues certificates to the nodes it trusts. By consideringevery issued certificate as an edge, a certification graph isformed. If two nodes wish to exchange their public keys andform a common secret, they find a certification path in thegraph and they can in this way authenticate each other.However, the major disadvantage of this approach is thecumbersome problem of finding a certification path in thegraph. A solution to this problem is proposed in [7] where avirtual hierarchy is built among the nodes in the graph.In this paper we propose an approach similar to [8] which isbased on a binary tree formation of the network’s nodes.Specifically, two alternative methods for binary tree formationare proposed each one having its pros and cons. Using thisstructure, the certificate path discovery problem is avoidedand the place of each node in the tree can be easily found.Moreover, the frequent join and leave events in the networkare efficiently handled by modifying the tree structure whereit is needed. In a nutshell, the proposed scheme has severaladvantages over other similar solutions, being more effectivein terms of join and leave procedures, path discovery,certificate management and performance, especially whensecurity is not of top priority. On the other hand, whensecurity is at stake, we offer a modified version of theproposed scheme which can deliver robust security servicesand effectively identify Denial of Service (DoS) attacks notaddressed by similar mechanisms until now. Last but not least,we discuss some methods for establishing initial trust betweenthe nodes of a MANET. Whilst this issue is very important, asit globally affects nodes’ trustworthiness, it is not adequatelyaddressed in the literature so far. The rest of the paper isorganized as follows. In Section II we show how trust can beinitially established between two nodes, while in Section IIIwe present our binary tree based protocol, consisting of twoalternative tree formation mechanisms. The certificate chaindiscovery procedure is presented in Section IV. Section Vprovides a comparison with other similar methods, while lastsection offers concluding thoughts and some pointers to futurework.II. ESTABLISHING INITIAL TRUST BETWEEN NODESMost works in the field of public key management assumeeither that some sort of trust among network entities existsbeforehand or that the nodes proceed with pairwisecertification blindly. After certification, if a node is detectedto behave aggressively or does not obey to the network rulesthen its certificate is revoked or left expired. Clearly,establishing trust among network nodes in a MANET is a verychallenging issue. Usually there is no external prior context atall among the participating entities. Bootstrapping from anexisting infrastructure or exploiting proximity for expressingindexicality, as they are presented in [9], can furnish partialsolutions towards solving this problem. trust and ad-hoc networks can be thought in a sense ascontradicting terms.In many cases however, it is necessary to initialize securityfrom the scratch for protecting subsequent interactions withinthe system. In this context, using proofs of work ininitialization of trust, and reputation systems can assist inestablishing a certain degree of trustworthiness according tothe first approach also known as “proof of work” (PoW)[10],[11]. The objective behind PoW systems is that a verifierV can make sure that a prover P has successfully performed acertain computational task. The basic characteristic of a PoWsystem is that creating the proof must entail a predictableamount of work, while verifying the proof must bestraightforward. Of course such schemes cannot fullyguarantee that a node can be trusted but they assist inautomatically exclude some of the bad peers from joining thenetwork.When no centralized authority exists, as in the case ofMANET, one method towards deriving positive conclusionswhether a given node can be trusted is to employ a reputationrating system [9],[12]. The reputation ratings can be based ondirect experience or recommendations by others in thenetwork community or a combination of the two. On the otherhand, while reputation systems work acceptably well incentralized realms their application in MANET scenariosrequire a decentralized reputation system, which in turn bringsseveral issues in the foreground mostly related with therecommendations exchange system design and the avoidanceof Sybil attacks. Some other answers to the basic question“Who trust whom in a MANET and why?” do exist in termsof device authentication [13]. Yet, such solutions mandate inmany cases some a priori configured trust relationshipbetween the participating nodes. For example, every devicejoining the network can carry a device certificate proving itsgenuineness. Nevertheless, this requires a PKI infrastructureto sign all the certificates during the so-called networkinitialization phase. The same problem applies in the case oftrusted computing fashioned solutions. In our opinionestablishing trust among network entities in a MANETremains very much an open research problem.III. PROPOSED SOLUTIONSIn this section we will describe two similar solutions forbuilding a binary tree of trust between the nodes of anyMANET. The binary tree approach can greatly contribute topath discovery process optimization, and thus can facilitatethe acquisition of certificate chain between the involved nodes.The first one starts from a single randomly chosen node, e.g.,the root of the tree and continues cascading until all willingto-participate nodes join the tree. The other one hastens theformation of the binary tree by starting simultaneously fromseveral different nodes.
A. The binary tree based scheme
The forming protocol starts when a given node, say N0sends a special (extended) HELLO message (this is actually aRREP with TTL = 1) to its neighbours stating that it wants toinitiate a tree-based trust relationship with them. Naturally, asthere is no pre-established trust among any network nodes in atypical MANET, the adjacent nodes can accept the invitationor simply reject it. Accepting such an invitation from a givennode means that the invited node is willing to proceed with amutual-certification process with the initiator. The purpose ofthe protocol is to form a binary tree of trust between allnetwork entities. So, each node can provide certificates to amaximum of two neighboring nodes. All nodes have a {public,private} key pair created locally, so for every node pair eachpart signs the public key of the other using its private key andsends the result towards the other part. This tree formingprocedure depicted in Figure 1 continues cascading requestsfrom the root of the tree (N0) down to the leafs. Assumingthat the network is dense enough the probability of havingsome - willing to participate - nodes left out of this process isnegligible. Figure 1_I depicts the initial state of the network as well aseach node’s signal range. At some point, N0 initiates theprotocol by sending pairwise-certification requests towardsN1, N2 and N3 correspondingly. The latter nodes agree toparticipate, so they are pairwise-certified with N0. After that,they send pairwise-certification requests towards theirneighbours, e.g., N3 invites N4, N5 and N6. This situation isillustrated in Figure 1_II. The protocol continues until thebinary tree depicted in Figure 1_III is formed. When a givenparent-node has completed the mutual-certification procedurewith two child-nodes, it will drop any similar request comingfrom its neighbours. For example, in Figure 1_II node N0sends requests to N1, N2 and N3 but drops the reply from N3since N1 and N2 have answered quicker to its request andhave already been added in the binary tree. In case a childnodehas already mutually-certified with a parent-nodeignores post-dated pairwise certification requests send byothers. To accomplish this each node must send in its HELLOmessages its state in the tree, i.e., the bit 0 or 1 for nonmembersand members correspondingly. This is necessary inorder to avoid redundant pairwise-certifications or loopsbetween the leafs of the same tree. For instance, as N6 has setup already a relationship with N2, drops the requestoriginating from N3. It is worth noting that all nodes aresupposed to be equal and the notation “parent” or “child”denotes their position in the tree. It is also stressed that forunsecured communications the nodes can use any possibleavailable route. For example, if N5 is in the range of N9 theycan exchange data directly.However, to establish a secure relationship they must firstobtain the certificate one another via the binary tree of trust, tosetup a symmetric session key, and finally communicatedirectly as the case may be.As already mentioned in Section II the main question of thecertification procedure remains: “how can a node beconvinced that a given public key, say K(N0) truly belongs tonode N0, so as to proceed with certification?” Whilst all theaforementioned solutions can be applied in our case, we adopta “commitment-driven” solution. That is, every node commitsitself to the scheme; to be disciplinarian and behavelegitimately. Therefore, initially, every node certifies the otherfor a sort period of time, say for some hours. After that, if theaspirant node proves good intentions its certificate is renewedwith a greater validity period. It is worth noting that detectingmisbehaving nodes among one-hop nodes is quite easy due tothe broadcast nature of wireless communications. Thecertified node must present a valid certificate to get a new one.Otherwise, the renewal procedure fails. Even though theproposed method imposes increased node overhead during itsfirst stages, balances some time later after achieving a relativehigh degree of trust level between all participants.
B. The parallelized binary tree based scheme
The binary tree based scheme described in the previoussection, can be easily parallelized in order to improveefficiency. Instead of starting the protocol with a given node,one can initiate the protocol by using two or more nodes. Thenumber of these nodes can be a parameter in the wholenetwork. Every such root node leads to the construction of asmall binary tree (which can be considered as a small cluster)and all these trees can be linked together by their root nodesforming a bigger network of trust. Linking different binarytrees into one also implies that every node on each tree carriesalso the unique identity of the tree, i.e., the IP address of theroot.Consider for example, the network in Figure 2_I. Supposethat nodes N0, N4 and N11 are randomly selected and theystart the execution of the binary tree based scheme. After, thefirst step of the protocol, three subtrees have been created (seeFigure 2_II). Every subtree should have a unique tree_ID e.g.,the IP address of the root node. When a node accepts aninvitation from one of its neighbours, it should check whetherthis node has the same tree_ID. If the two nodes' tree_IDs arethe same, then the invited node does not accept the invitation(otherwise a cycle would be formed). In the case that thetree_IDs are different, then both nodes agree randomly in oneof the tree_IDs and inform all the other nodes in the twosubtrees in order to all adopt the same tree_ID. For example,in Figure 2_III node N8 has sent an invitation to node N11,node N11 has accepted it (since N8 and N11 belong todifferent subtrees) and the rest of the nodes are notified thatthey belong now in the same binary tree. If N8 sends aninvitation now to its other neighbour (N5), then this requestwill be denied since N8 and N5 belong now in the samesubtree.However, there is another one parameter that should betaken care of in order to guarantee that a binary tree is created.A node having accepted three invitations should not acceptanother one, even in the case that this request is coming froma different subtree node. If this restriction is not satisfied, thenthe formed tree would not be binary. When all nodes in thenetwork have been visited (Figure 2_III), a node having twoadjacent edges should be chosen to be the root. For example,if node N4 is chosen in Figure 2_III then the formed tree is theone in Figure 2_IV. Generally, this scheme performs fasterwhen compared to those described in the previous subsection.However, this comes at a cost in complexity, i.e., the mergingprocess of different subtrees.
Download full report
http://icsd.aegean.gr/infosec_base/downl...y-tree.pdf
