Efficient Certification Path Discovery for MANET

The formation protocol starts when a given node, say 0 sends a HELLO message to its neighbours stating that it wants to initiate a tree-based trust relationship with them. Taking ad hoc on-demand distance vector (AODV) [24] as example, this is a Route Reply (RREP) with TTL = 1. For the moment, assume that there is no preestablished trust among all or some of the network nodes that comprise the MANET. So, the adjacent nodes may decide to accept the invitation or simply reject it. Accepting such an invitation from a given node means that the invited (peer) node is willing to proceed with a mutual-certification process with the initiator. The purpose of the protocol is to form a binary tree of trust between all network entities. Therefore, each node can provide certificates to a maximum of two neighboring nodes. All nodes have a public, private key pair created locally, so for every node pair each part signs the public key of the other using its private key and sends the result towards the other part. This tree forming procedure depicted in Figure 1 continues cascading requests from the root of the tree ( 0) down to the leafs. Assuming that the network is dense enough the probability of having some—willing to participate—nodes (as 12 in Figure 1) left out of this process is negligible.

Figure 1(a) depicts the initial state of the network as well as each node's signal range. At some point, 0 initiates the protocol by sending pairwise-certification requests towards 1, 2 and 3 correspondingly. The latter nodes agree to participate, so they are pairwise-certified with 0. After that, they send pairwise-certification requests towards their neighbours, for example, 3 invites 4, 5 and 6. This situation is illustrated in Figure 1(b). The protocol continues until the binary tree depicted in Figure 1(c) is finally formed. When a given parent-node has completed the mutual-certification procedure with two child-nodes, it will drop any similar request coming from its neighbours. For example, in Figure 1(b) node 0 sends requests to 1, 2, and 3 but drops the reply from 3 since 1 and 2 have answered quicker to its request and have already been added in the binary tree. If a child-node has already been mutually-certified with a parent-node ignores post-dated pairwise certification requests send by others. To do so, each node must send in its HELLO messages its current state in the tree, that is, the bit 0 or 1 for non-members and members correspondingly. This is necessary in order to avoid redundant pairwise-certifications or loops between the leafs of the same tree. For instance, as 6 has already established a relationship with 2, drops the request originating from 3. It is worth noting that all nodes are supposed to be equal and the notation "parent" or "child" denotes their position in the tree. It is also stressed that for unsecured communications the nodes can use any possible available route. For example, if 5 is in the range of 9 they can exchange data directly.

However, to establish a secure relationship they must first obtain the certificate one another via the binary tree of trust, to setup a symmetric session key, and finally communicate directly as the case may be.

As already mentioned in Section 2 the main question of the certification procedure remains: "how can a node be convinced that a given public key, say K( 0) truly belongs to node 0, so as to proceed with certification?" And, if certification succeeds, how one can rest assured that a certified node will continue to obey the network rules? Whilst all the approaches mentioned in Section 2 for initializing trust can be applied in our case, we assume a "friendship-based" and "commitment-driven" solution. That is, trustworthiness among nodes may depend on the existing friendship of users participating in the network. If two users, say Alice and Bob, are friends, they trust each other and their respective devices can exchange their public keys. There may be numerous reasons for a node Alice to believe that she is binding the Bob's public key to the real Bob and not Malloy. For example, nodes Alice and Bob may have exchanged their public keys via a side channel (e.g., over an infrared channel) at the time of a given physical encounter. As presented in [25], we can assume a bidirectional trustworthiness between two nodes, meaning that, if Alice trusts Bob, then Bob trusts Alice as well. This assumption stems from the statistical analysis of the Web of trust showing that about 2/3 of the links in the large strongly connected social network are bidirectional [26].

Overall, we can say that every node commits itself to the scheme; to be friendly, disciplinarian and behave legitimately. Otherwise, it will be isolated from the tree of trust and would not be able to send any packet via its neighbours. Also, to increase the level of trustworthiness, initially, every node may certify any other for a short period of time, say for a couple of hours. After that, if the "postulant" node proves good intentions, its certificate is renewed with a greater validity period. It is worth noting that detecting misbehaving nodes among one-hop nodes is quite easy due to the broadcast nature of wireless communications. The detection of misbehaving nodes can also be enforced using a reputation rating or recommendation system based on observation and/or second-hand information as discussed in Section 2. An already certified node must present a valid certificate to get a new one. Otherwise, the renewal procedure fails and implicitly the node is forced to disjoin from the network. Even though the proposed method imposes increased node overhead during its first stages, balances some time later after achieving a relative high degree of trust level between all the participants.

The binary tree-based scheme described in the previous subsection, can be easily parallelized in order to improve efficiency. Instead of launching the protocol from a given node, one can initiate the protocol by using simultaneously two or more nodes. The number of these nodes can be parameterized in the whole network. Every such root node leads to the construction of a small binary tree (which can be considered as a small cluster) and all these subtrees can be linked together through their root nodes forming a bigger network of trust. Linking different binary trees into one also implies that every node on each tree carries also the unique identity of the tree, that is, the IP address of the root.

Consider for example, the network in Figure 2(a). Suppose that nodes 0, 4, and 11 are randomly selected and they start the execution of the binary tree-based scheme. After, the first step of the protocol, three subtrees have been created (see Figure 2(b)). Every subtree should have a unique tree_ID, for example, the IP address of the root node. When a node receives an invitation from one of its neighbours, it should check whether this node has the same tree_ID. If the communicating nodes' tree_IDs are the same, then the invited node does not accept the invitation (otherwise a cycle would be formed). In the case that the tree_IDs are different, then both nodes agree randomly in one of the tree_IDs and inform all the other nodes in the two subtrees in order to all adopt the same tree_ID. For example, in Figure 2(c) node 8 has sent an invitation to node 11. The latter has accepted it, since 8 and 11 belong to different subtrees, and the rest of the nodes are notified that they belong now in the same binary tree. After that, if 8 sends an invitation to its other neighbour ( 5), then this request will be denied since both nodes belong now in the same subtree.

However, there is another one parameter that should be taken care of in order to guarantee that a binary tree is created. A node that has already accepted three invitations should not accept another one, even in the case that this request is coming from a different subtree node. If this restriction is not satisfied, then the formed tree would not be binary. When all nodes in the network have been visited (Figure 2(c)), a node having two adjacent edges should be chosen to be the root. For example, if node 4 is chosen in Figure 2(c) then the formed tree is the one depicted in Figure 2(d). Generally, this scheme performs faster when compared to those described in the previous subsection. However, this comes at a cost in complexity, that is, the merging process of different subtrees.

According to the proposed schemes the join and leave procedures are straightforward. Briefly, when a node leaves or an entrant joins the network only a branch of the tree is affected. More specifically, supposing that 4 in Figure 1(c) leaves the community, for example, moves out of range, nodes 8, 5 will seek parent in 3 or 6 depending on the topology and signal strength.

On the other hand, thinking of a scenario where 12 joins the network near the range of 3 it will establish a relationship with either 3, 5, 6, or 9. It is implied that in the rare case a newcomer cannot immediately find an association it must wait for some time until some other node roams out of that specific coverage area (a parent loses one child). In such occasions there is always the possibility for the node to roam to a new position until it finds a pair.

Lastly, the most complex leave situation is when the root node, say 0 in Figure 1(c), leaves the tree for some reason. Then 1 or 2, that is, the nodes closer to him, must replace 0. Assuming that 1 takes over the role of the root it must abandon 3, keep the connection with 4, and establish a direct relationship with 2. Consequently, 3 must seek for another parent. Even in this case, the join procedure is expected to complete after very few interactions, that is, new mutual-certifications between the corresponding nodes. A performance evaluation of join and leave for our scheme is given in Section 7.

Works in the first category are based on some kind of Trusted Third Party (TTP), for example, special PKI servers, and Kerberos to issue and distribute digital certificates and public key pairs. The authors in [1] were the first to propose a partially distributed Certification Authority (CA) consisted of servers, combiners, and a dealer. Their scheme was based on threshold cryptography, that is, assuming that all partial signatures are collected a newcomer can compute the complete signature locally to acquire the public key certificate. In [3] the authors also propose a distributed CA based on threshold cryptography. They distribute the CA functionality over specially selected nodes based on the security and the physical characteristics of nodes. The selected nodes are called MObile Certificate Authority (MOCA) servers. Communication overheads are reduced by caching routes to MOCA servers. Work in [28] proposes the so called Distributed CerTification Authority with probabilisTic frEshness for ad hoc networks (DICTATE) scheme. DICTATE is based on a combination of threshold and identity-based cryptosystems to guarantee the security, availability, and scalability of the certification function. To do so, it employs a hierarchical CA between one "mother" CA residing in the wired network, and a group of distributed CA in ad hoc network. Also, ensures that the distributed CA always processes a certificate update request in a finite amount of time and that an adversary cannot forge a certificate. Moreover, it guarantees that the same entity responds to a query request with the most recent version of the queried certificate in a certain probability.

The authors in [29] present IKM an ID-based Key Management system as a novel combination of ID-based and threshold cryptography. Actually, IKM is a certificateless solution in that public keys of mobile nodes are directly derivable from their known IDs plus some common information. Therefore, IKM eliminates the need for certificate-based authenticated public-key distribution indispensable in conventional public-key management schemes. Also, IKM features a novel construction method of ID-based public/private keys. Work in [30] proposes a solution of a distributed CA based on threshold cryptography as well. The authors derive their idea from the fact that in distributed CA when the number of neighbors of a node, also called node degree, reduces there is a substantial increase in the certification service delays. Their solution is based on the observation that when the node degree varies, the delays involved in obtaining certificates may be reduced by dynamically varying the threshold value. This can dynamically adjust the threshold value by monitoring the average node degree of the network and thereby prevent an increase in certification service delay. The authors in [31] suggest a CA cluster-based architecture by dividing the network into clusters. Eventually, each cluster head is able to maintain a CA information table, which contains a list of CA nodes in the local cluster as well as in the other ones. The distributed CA information is maintained among cluster heads, which reduces service response delay and the overall system overhead. Work in [32] proposes a system called mixed NETworks Trust infrastRUcture baSed on Threshold cryptography (NetTRUST). NetTRUST uses two CAs that ensure public key management, that is, central CAs in wired network, and mobile CAs in ad hoc network. Mobile CA servers emulate the CA role by using a ( ) scheme, and the central CA servers delegate the CA role to mobile CA servers by using a ( ) scheme. NetTRUST is decentralized, supports node mobility, and resists against mobile CA failures.

On the other hand, in infrastructureless or fully distributed solutions, like the one we propose here, security does not rely on TTPs or special kind of servers but on self-organization of nodes. Here, trust is usually propagated through a trust graph like the one employed by the well known PGP model. The authors of [33] propose a self-organized trust model for MANETs, in which trust among nodes is derived via physical contact. According to the authors every node issues public key certificates to other trustworthy nodes from its own domain. Nodes can authenticate each others using chains of trust. All nodes are assumed to store as many certificates as possible. In this model, trust establishment is originating from "offline trust relationships, which in turn are generated from general social relationships. A modified version of [33] is proposed in [34]. The authors introduce a boot server in order to initialize the system. This server calculates and distributes to each node a list of bindings (identifiers and public keys) and each of them generates the corresponding certificates. Upon that, a web-of-trust relationships is generated leading to a fully distributed system, that is, all nodes authenticate themselves via certificates chains. In [6] the authors describe an on-demand, fully localized, and hop-by-hop public key management scheme for MANETs. According to their method the network nodes self-generate public/private key pairs, issue certificates to any adjacent nodes, keep these certificates in their certificate repositories, and provide authentication service adaptively and quickly to the dynamic topology of the network without relying on any centralized entities. Another work that does not use threshold cryptography but assumes a self-organized PKI among the nodes of a MANET as proposed by [5] is given in [7]. The authors propose a protocol that establishes a virtual hierarchy in a peer-to-peer PKI. This protocol is suitable for the dynamic environments of MANETs since it is executed in a short time. Their protocol does not require to issue new certificates among PKI entities, facilitates the certification path discovery process and the maximum path length can be adapted to the characteristics of mobile terminals with limited processing and storage capacity. A very recent work that proposes a fully distributed public key certificate management system based on a hybrid approach, that is, in trust graphs and threshold cryptography, is given in [8]. The described solution permits users to issue public key certificates and to perform authentication via certificates' chains without the presence of any centralized management or trusted authorities. Due to the use of threshold cryptography the proposed system is able to resist against false public keys certification.

Work in [35] is also based on web-of-trust approach. Here, nodes act as CAs without the presence of any TTP. The system divides the network into clusters, such that nodes are assigned into different groups with unique identifiers. Authentication can be performed in a distributed manner, and newcomers are introduced by any trustable nodes of the same group. Nodes in the network monitor the behavior of each other and continuously update their trust tables. This endures the false certificate issued by dishonest users and malicious nodes, and avoids them to be selected as introducing nodes. The approach described in [36] is also based on distributed clustering and relies on trust values metric and behavior monitoring in order to distribute the role of certification authority (CA) in each cluster. It employs fully self-organized security and monitoring process to supervise behaviors of nodes with low trust level. Furthermore, the authors introduce a new concept to protect CAs and avoid the single point of failure in each cluster. Another Cluster-based approach is presented in [9]. The authors propose a practical model of public key certificate chain for MANET. Their scheme does not rely on a central server, but rather on Cluster-Based Routing Protocol (CBRP). CBRP is used to issue certificates in a distributed fashion. The certificates are chained effectively and the signed messages can be transferred over a certificate chain.

In order to evaluate the proposed scheme we employ the well known NS/2 simulator [37]. However, we were forced to implement several additional routines either in TCL or C++ as follows.

The pseudocode for each one of the aforementioned routines is given in the appendix. The source code is also available upon request from the authors.

The simulation parameters are given in Table 2. We simulated 6 different scenarios in total by varying the number and the topology of nodes randomly. Specifically, we used 8, 20, 40, 60, 80, and 100 nodes for each scenario accordingly. A sample topology for the last 4 scenarios is depicted in Figure 5. The purpose of the evaluation is three-fold: (a) to estimate the overall time to construct the binary-tree under different scenarios, (b) to estimate the overall time to reconstruct the tree after leave and join events, and (c) to estimate the network time required to build up a certification chain.

Figure 6 depicts the overall time needed to construct the binary tree depending on the scenario. The time seems to significantly increase when the number of nodes in the network grows; for example, from 20 to 60 one can spot an additional time penalty of 29 seconds. This is actually expected but it is not the only time-affecting parameter. The density (topology) of the nodes and the distance between them also affects the overall time to build up the binary tree structure. This can be inferred from the plot as the time of 29.7 seconds needed for 60 nodes unexpectedly diminishes to 17.2 when the number of nodes becomes 80. Therefore, it is projected that the time needed to construct the tree will be affected by two major factors; firstly the number of nodes participating in the network, and secondly the exact topology of the network.

The tree reconstruction times after multiple join and leave events happening nearly at the same time are given in Table 3 (see the fourth line of Table 3 in each scenario). We consider 3 different scenarios where a 10, 20, and 30% of randomly chosen tree nodes are involved in join or leave operations almost simultaneously. Each scenario considers 6 variations according to the number of nodes in the tree as the case may be. The recorded total times seem to be highly spanned in some cases, for example, for the 40 nodes case and the 20% variation the time is 0.26 seconds but for the 30% it climbs to 7.33. The same situation is perceived for several other scenarios, for example, for the 80 nodes case there is a large difference of approximately 12.5 seconds between the 10, 20% variations and the 30% one. On the other hand, we must consider the fact that these times are severely affected by the tree topology and the randomness of the scenario, that is, how many nodes leave/join the tree each time and the exact position of every node involved in a leave/join incident. These factors may affect one or several other nodes depending on the case. That is, if the root node leaves the tree then it is expected to affect several other nodes (see Section 3.3). Of course, this is not the case for a leaf node. Also note that the 30% scenario is not common even in highly dynamic MANETs, but it is considered here as an overstressing case.

The aforementioned situation of—in some cases—high deviations in the results is confirmed by the timings and associated metrics provided in Table 3. The third line of the table gives the total number of roundtrip messages required in each subscenario to reconstruct the tree. These messages were sent from all the affected nodes (i.e., nodes that lost their parent and/or others seeking to join the tree) in each sub-scenario in order for them to (re)join the binary tree. Note that an affected node may send one or more messages towards other nodes in an effort to eventually (re) join the tree. For instance, the 8 nodes case and the 10% variation as executed (1 node left) led to a total of 9 messages to be sent. These 9 messages required 0.08 seconds (75.5 milliseconds) altogether ending up to reforming the binary tree structure. For the 20 nodes scenario and the 10% variation only 3 messages were required and thus the overall time diminishes to 0.03 seconds (31.7 milliseconds). However, as the tree grows and the percentage of simultaneously join/leave incidents increases the number of messages required to reconstruct the tree tend—as a general rule—to augment. For example, the 100 nodes scenario with the 20, 30% variations required 89 messages to rebuild the binary tree, while the 10% variation triggered 60 messages from affected nodes. Also, message roundtrip times may differ significantly from sub-scenario to sub-scenario, and in some cases present unexpected peaks. This is justified by the unreliability of the wireless medium and channel allocation mechanisms (in our case these conditions are provided by NS/2). Besides, this situation is confirmed by the mean and standard deviation times given in the fifth and sixth line of Table 3 respectively. For instance, the 80 nodes scenario and the 30% variation produces a standard variation time of almost 1 second. Nevertheless, the spread of node message timings around the mean time is not certain to grow as the number of nodes increases. Therefore, we provide an 80 percent confidence interval metric to provide a better estimation of the range within which the true value of the statistic parameters of Table 3 lie. Generally, one can say that these timings heavily depend on the randomness of each scenario and the topology of the tree as noted again earlier.

Figure 7 presents the overall time needed for two nodes to exchange their certificates as described in Section 4. More specifically, from an edge leaf node to another; taking Figure 1 as an example from 11 to 10. This time is also proportional to the number of nodes in the network, that is, the depth of tree. Here, we only consider the network time to fulfill such a request for the worst case scenario. This is justified by the fact that the cryptographic functions (see Section 4) involved heavily rely on the device employed as the case may be. This gives one the advantage to easily recalculate the total times when changing the hardware characteristics of a device or the security algorithm employed. For instance, when speaking for modern processors, for example, an Intel Core 2 1.83 GHz processor under Windows Vista in 32-bit mode an RSA 1024 plain signature/verification requires 1.48 and 0.07 milliseconds, respectively, (see http://​www.​cryptopp.​com/​benchmarks.​html). For a rather obsolete mobile device like the Sharp Zaurus SL-5500G (206MHz Intel SA-1110 StrongARM) the RSA 1024 plain generation/verification time is 78.0 and 4.3 milliseconds, respectively, [38]. Additional signature generation timings for different hardware settings and key lengths can be found in [39]. In a nutshell we can argue that our scheme requires few hundreds of milliseconds to build up a certificate chain between two nodes. This is because the network time is minimized due to the binary-tree structure (i.e., for 80 nodes it only requires 143 ms), while the public key operations take up the biggest portion requiring two signature operations per node except the initiator and the peer. However, in all cases, the signature verification time can be considered negligible. Overall, the binary tree formation procedure and maintenance may be time consuming but it really compensates when certificate exchange comes into play.