Received 28 July 2014; revised 25 August 2014; accepted 20 September 2014

ABSTRACT

Devices participating in mobile ad hoc networks (MANET) are expected to strictly adhere to a uniform routing protocol to route data packets among themselves. Unfortunately, MANET devices, composed of untrustworthy software and hardware components, expose a large attack surface. This can be exploited by attackers to gain control over one or more devices, and wreak havoc on the MANET subnet. The approach presented in this paper to secure MANETs restricts the attack surface to a single module in MANET devices a trusted MANET module (TMM). TMMs are deliberately constrained to demand only modest memory and computational resources in the interest of further reducing the attack surface. The specific contribution of this paper is a precise characterization of simple TMM functionality suitable for any distance vector based routing protocol, to realize the broad assurance that “any node that fails to abide by the routing protocol will not be able to participate in the MANET”.

Keywords:

Algorithm/Protocol Design and Analysis, Network Protocols, Cryptographic Controls, Mobile Ad-Hoc Networks (MANET), Distance Vector (DV) Protocols, Authenticated Data Structures (ADS)

1. Introduction

A mobile ad hoc network (MANET) [1] is a dynamic subnet constituted of mobile computers (or devices) with limited wireless transmission range. MANET devices rely on each other for routing packets among themselves, and consequently, do not depend on a dedicated routing infrastructure.

A MANET routing protocol is a set of rules which dictate the tasks to be performed by every device in a MANET subnet to enable discovery of multi-hop paths for relaying data packets. Such rules govern processes like discovery of neighbors (devices within limited wireless transmission range), exchange of routing infor- mation between neighbors, maintaining a destination table (DT) and a neighbor table (NT) at every device, using information in the DT and NT to forward data packets, etc.

The rules that govern the actions of a MANET device are typically encoded as software executed by the device. Unintended functionality either deliberately hidden malicious functionality, or accidental bugs-in any component of a mobile device could potentially be exploited by attackers to 1) modify the functionality (routing software) of the device, or 2) modify the information stored by the device (in DT and NT), or 3) expose secrets of the device, thereby enabling the attacker to impersonate the device to advertise arbitrary “routing information”. Attackers could be legitimate owners of a device, or entities who may have exploited some hidden functionality in the device to acquire some extent of control over the device. Many such attackers may even collude together to wreak havoc on the ad hoc subnet.

A practical MANET device can come in several shapes and sizes, ranging from laptops to smart phones to special purpose sensors, constructed using a wide range of hardware/software components. It is obviously far from practical to rule out the presence of undesired functionality in every hardware and software component of every device that could take part in a MANET subnet, or malicious behavior/incompetence in every entity that has the ability to gain control of a device. It is, however, far more practical to assure the integrity of a single component in every device. For example, every MANET device could be required to possess a trustworthy chip/ module.

In the rest of this paper we shall refer to such a module/chip as a trusted MANET module (TMM). It is assumed that secrets protected by TMMs cannot be exposed, and the functionality of TMMs cannot be modified. All other software and hardware in every MANET device, and the user in control of the device (either through legitimate or illegitimate means), are assumed to be untrusted/hostile. The trust in TMMs, and more importantly, only the trust in TMMs, is leveraged to realize the assurance that “any device that does not strictly abide by the protocol will not be able to participate in the MANET”.

1.1. Trusted Computing Base for a MANET Device

For any computing system with a desired set of assurances, the trusted computing base (TCB) “is a small amount of software and hardware we need to rely on” [2] to realize the desired assurances. In other words, the desired assurances can be realized even if all other components of the system misbehave. From this perspective, TMMs can be seen as the TCB for MANET devices. As a specification of the TCB we provide a comprehensive functional description of TMMs.

In general, the lower the complexity of any hardware/software component, the lower the risk of unintended functionality. Towards this end, it is desirable that TMM functionality be deliberately constrained to demand low computational and memory resources to enable consummate verification, and thereby rule out hidden functionality in TMMs. Consequently, TMM functionality is restricted to simple sequences of cryptographic hash and logical operations, and to demand only a small constant memory size for their execution.

In the proposed approach the protocol specific rules to be followed by every MANET device are expressed as a simple algorithm consisting of sequence of logical operations. The TMM functionality necessary to achieve the desired assurances can then be seen as functionality required to a) execute algorithm inside the TMM and b) TMM functionality necessary to assure the integrity of the dynamic inputs and outputs of. While the proposed approach has a broad range of applicability (where rules expressed by algorithm will be different for different application scenarios) in this paper we restrict ourselves to MANET devices adhering to distance vector (DV) based routing protocols.

1.2. Organization

Section 2 sets the background with a review of MANET routing protocols, and attacks on MANET routing that exploit the substantial attack surface exposed by MANET devices. Section 3 provides an overview of the proposed approach in which TMMs serve as the TCB for a MANET node. Section 3.4 outlines protocol specific components of TMM functionality, which include a specification of constants, and an algorithm for distance vector based routing protocols. The inputs to are identified as 3 records (a destination records, and 2 neighbor records), and protocol-specific constants, and the outputs are different types of messages created by the TMMs.

In the proposed approach the dynamic DT and NT are stored by the untrusted device as leaves of two index ordered merkle trees (IOMT). Only the roots of the two trees are tracked by the TMM. Section 4 outlines TMM functionality necessary to maintain an IOMT. Section 5 outlines the architecture of TMM and depicts how different elements of TCB functionality come together to provide the guarantee that devices will that do not strictly abide by protocol specific rules (for modifying NRS and DRs, and sending routing information and data packets consistent with the stored NRS and DRs), will not be able to take part in the MANET. Some relevant work in the area is discussed in Section 6.

2. Background

Any routing protocol can be seen as an extension of two basic routing strategies-distance vector (DV) or link-state (LS) approaches. In LS protocols information regarding a destination is in the form of the state of all links of (to neighbors of). All nodes in the subnet possess the same information regarding.

In DV protocols information regarding is a destination record (DR) that indicates the hop count to, and the next hop in the path to. In general, every node possesses a different DR for destination. Neighbors exchange DRs amongst themselves, and by comparing DRs for a destination obtained from all neighbors, a node can determine its best DR for, which is then stored in a table of DRs-the destination table (DT).

2.1. Distance Vector Protocols

A majority of popular MANET routing protocols are based on the DV approach in which every node maintains a destination table (DT) and a neighbor table (NT). The DT consists of a destination record (DR) for each possible destination. The NT consists of a neighbor record (NR) for each neighbor.

A DR for a destination (mobile device with address) indicates a sequence number, the time of expiry, hop-count to the destination, and the next-hop neighbor in the path to the destination. For an unreachable destination, the hop-count is (an integer constant larger than the maximum allowable hop-count). A “neighbor” of a device is another device to which the existence of a bidirectional path has been confirmed. Neighbors are expected to confirm each other’s continued presence, possibly by exchanging periodic HELLO messages. A neighbor who has has been silent for a long duration may no longer be considered a neighbor.

In all DV protocols, a DR for destination is initiated by, indicating a fresh sequence number, hop count (to itself as), and time of expiry. The next hop is set to itself (or). This DR may then be advertised to all its neighbors. Neighbors of store the DR in their respective tables after incrementing the hop-count field to 1, and setting the next hop as. The stored DR may then be advertised to their neighbors, and so on.

In this fashion, any node in a connected subnet can acquire a DR for destination: a device hops from will have a DR for in it’s table, with hop count. A device can receive a DR for a destination from each of its neighbors. In general, the stored DR is replaced by the received DR if the received DR is fresher, or equally fresh and better.

Ultimately, the purpose of maintaining the DT and NT is to relay data packets. A device which desires to relay a data packet to can do so only if it has a usable DR for. A DR for a destination is considered as usable only if, the DR has not expired, and the next hop continues to be a neighbor. The data packet may now be relayed to the next hop. The device at the next hop can likewise relay the data packet onwards to it’s next hop, indicated in a usable DR for in its DT, and so on, until the data packet reaches. When a device receives a data packet intended for a destination from a neighbor, and finds that it no longer has a usable DR for, it responds by advertising a route error (RERR) packet. may now update it’s stored DR for (by setting) and relay the RERR to it’s upstream neighbor (who had earlier sent the data packet to), and so on.

In proactive DV protocols like destination sequenced DV (DSDV) [3] every node initiates a DR periodically- each time with a higher sequence number. In reactive protocols like ad hoc on demand DV (AODV) [4] , nodes initiate DRs only if they desire to send/receive data to/from another node. For this purpose, a node desiring to send data packets to (and finds that it does not have a usable DR for destination) advertises a route request (RREQ) packet which includes a fresh DR for itself, and it’s unusable DR for. The RREQ is flooded in the subnet. Any node with a usable DR for, (or itself) may include the DR in a route response (RREP) packet which is relayed back to the source.

2.2. Covert and Overt Attacks

Broadly, an attack by a participating device (say,) on a MANET can be seen as an attempt to send a routing/data packet P to a neighbor (say,) where the contents of packet P were not generated in strict compliance with the protocol. Even more generally, an attack may also include the act of not sending a packet P (when the protocol calls for a packet to be sent).

An attack is successful if is unable to distinguish between packets created strictly according to the protocol and packets created in violation of the protocol. If is able to determine that a packet has been created by in violation of the protocol, or that should have sent a packet (when it did not), the attack is deemed unsuccessful (as now has the ability to penalize by no longer entertaining as a neighbor).

Attacks that can be inflicted on a MANET subnet by a participating device can be broadly classified into overt and covert attacks. Overt attacks include incorrect packet formats, and illegal modifications to a relayed DR (for example, changing sequence number, expiry time, or changing hop count in any other way except incrementing by one, etc.). The reason that such attacks are overt is that 1) attacks like incorrect formats can be readily identified, and 2) if suitable cryptographic authentication strategies are used to protect the integrity of DRs advertised by devices, then the receiver of such a packet can readily detect illegal modifications and drop the offending packet.

The main challenges in the practical realization of assurances against overt attacks are two fold. The first stems from the overhead for cryptographic authentication schemes-especially for carrying over authentication over multiple hops. The second is that cryptographic strategies are (ultimately) at most only as strong as the mechanism used for protection of a device’s secrets. The absence of reliable mechanisms to protect secrets assigned to devices from attackers (who may even be the owner of a device) implies that attackers may even share secrets exposed from multiple devices to advertise misleading (but duly authenticated) “routing information” at will.

Unlike overt attacks, covert attacks may not be readily discernible by the receiver of a packet-even with sophisticated cryptographic authentication schemes. Examples of such attacks include 1) replaying DRs that were invalidated (or rendered sub-optimal) due to recent changes in topology; 2) rebroadcasting RREQs (instead of responding with an RREP) when a usable path exists; 3) not relaying data packets, or relaying data packets incorrectly (for example, to a device that is not the next hop in the best DR for the destination); 4) invoking unwarranted RERR packets (even when the link to the next hop is not broken); 5) accepting packets from (or relaying packets to) “neighbors” to whom a bidirectional link does not exist (thereby, making sure that the reverse path will fail), etc. 6) attacks based on misrepresentations of current time; for example, the clock of a device may be modified to make it think that a DR has expired.

The reason that such attacks may not be easily detectable is that in a scenario where a device receives a packet from a device, there is no tangible way for the routing process in a device to confirm that does have a link to it’s neighbor (when claims that the link is broken) or that does have a better path (when advertises a suboptimal path). While it might appear that a fairly sophisticated monitoring process in a neighbor of, (say), which had earlier sent the better path to, may be capable of detecting’s malicious intention it is entirely possible that’s advertisement was not received by (for example, due to collision).

Furthermore, it is also possible for an attacker to exploit collision-avoidance mechanisms used in wireless medium access protocols to send some information to it’s all neighbors while simultaneously ensuring that the information will not be heard by a specific neighbor. For example, can get to know of an impending reception by from a CTS (clear to send) packet from. By transmitting information at a time that overlaps with’s reception, can ensure that it’s suspicion-raising transmission will not be heard by. An attacker can also exploit this ability to carry out other possible attacks like 1) claiming it has lost it’s link to to all its other neighbors (but continue to use as a neighbor for it’s own purposes); 2) faking relay of a data packet or route error packet to the next hop, etc.

From a broad perspective, covert attacks can be seen as replay attacks where the sender is able to make contradictory statements to different entities. Any rogue process in a MANET device may be able to perpetrate such attacks by either modifying the routing process, or hardware drivers, or modifying the contents of the DT/NT, or by modifying MANET parameters like etc. Even a less sophisticated rogue process that does not have the ability to do so, may be able to modify the interpretation of the contents of a DT/NT by resetting the device’s clock.

3. Overview of TMM Based Approach

To our knowledge, the proposed approach is the first to address both overt and covert attacks, under the reasonable assumptions of 1) a secure pre-image resistant cryptographic hash function exists; and 2) every MANET device possesses a TMM that is read-proof and write-proof.

All TMMs are identical except that each have a unique identity, and possess unique secrets which enable any two TMMs to compute a pair-wise secret. Every TMM has a clock which ticks at (very close to) the same frequency. However, the clocks of TMMs are not synchronized. In this paper we shall assume that the identity of the TMM in a device is also. However, to distinguish between the device and it’s TMM, we shall refer to “device” as and “TMM” as.

It is assumed that all components of MANET devices and the user(s) in control of the device are untrusted/ hostile. In other words, the untrusted user/device is able to modify the routing software, and/or the device’s clock, and/or the DT/NT, and may possess complete control over the wireless interface. Not with standing such capabilities attributed to the rogue software/hardware in the device or the user controlling the device, the goal is to ensure that “all devices will indeed abide by the protocol rules”.

Any MANET packet sent by a device to device is accompanied by a corresponding message from TMM to TMM. Pairwise secrets between TMMs are used to compute message authentication codes (MAC) for assuring the integrity of such messages. As devices can not impersonate TMMs, device is required to request it’s TMM to create a message, and deliver the message to device; device is similarly expected to submit the message to it’s TMM and receive an acknowledgement message that can be conveyed back to through.

The TMM approach to secure MANET routing can be seen as consisting of two broad steps: a) representation of protocol rules as a simple algorithm that can be executed even inside the confines of severely resource limited TMMs, and b) ensuring the integrity of inputs and outputs of the algorithm;

Towards the first step we outline an algorithm suitable for any distance vector based protocol. The inputs to the are restricted to one DR for a destination, up to two NRs (corresponding to two neighbors), protocol specific constants, and parameters associated with an event.

An event can be the a message received from another TMM, or a request from the device. The occurrence of an event may necessitate i) a modification to the DR (say, for destination) and/or two NRs (say, for neighbors and) and ii) creation of up to 2 messages-one intended for neighbor and one for. For each type of event (specified by event parameters) the algorithm specifies a) the manner in which a DR for and up to two NRs for and will need to be modified; and b) the type of messages to be created and sent to and.

Towards assuring the integrity of inputs/outputs of it is required to 1a) assure the integrity of all dynamic DRs and NRs stored in the DT/ NT; 2) protect the integrity of the (static) constants, and 3) assure the integrity of messages exchanged between TMMs.

3.1. Integrity of Inputs and Outputs

Resource limited TMMs can not store the entire DT and NT inside their protected boundary. TMMs maintain a succinct summary of the DT and NT in the form of two cryptographic hashes and respectively. More specifically, and are roots of two index ordered merkle trees (IOMT): root corresponding to the DT, with DRs as leaves of the tree, and root corresponding to the NT, with NRs as leaves.

Similar to the Merkle tree [5] , the IOMT is a binary hash tree maintained by an untrusted prover to demonstrate the integrity of dynamic records (also maintained by the prover) to a resource limited verifier that stores only a single cryptographic hash-the root of the tree. For a database with records, the prover stores all records, and in addition, cryptographic hashes, which are nodes of the binary tree, distributed over levels. The verifier stores only a single node-the root of the tree.

In order for a resource limited verifier (for our purposes, the TMM) to be able verify the integrity of any number of dynamic records stored in an untrusted location (the untrusted device), even a plain merkle hash tree can be used. However, to address covert attacks, it is not sufficient for a TMM to be able to merely verify the integrity of a DR for a destination or a neighbor record for a neighbor; it is also essential for the TMM to be able to verify that an NR for or a DR for does not exist. If TMMs can not readily verify non-existence, the untrusted device will be able to hide a DR or NR that does exist, to perpetrate covert attacks. The use of IOMT instead of a plain merkle tree prevents such attacks.

The integrity of constants are assured by including a one-way function of the constants in the process of computing shared secrets between TMMs. Protocol specific constants are used in the process of initializing a TMM to operate in a specific MANET. All TMMs in a MANET will need to be initialized with the same constants, as TMMs initialized with different constants will not be able to agree on a shared secret. Such pairwise secrets are used for computing message authentication codes (MAC) for TMM messages to assure the integrity of messages in transit.

However, protecting the integrity of messages in transit is not sufficient. It is also necessary to have proactive strategies to guarantee that messages created by a TMM for consumption of TMM are actually delivered to TMM. Note that in the path between the two TMMs and are two untrusted middle-men the devices and that house the TMMs, who can easily drop messages.

This issue is addressed by employing “locks”. A lock is a special field in the NR. When a TMM sends a message to a TMM it sets the lock in the NR of. The lock can be reset only if an acknow- ledgement is received from. As TMM messages can not be impersonated the acknowledgement from can be provided to only if the message from was actually delivered to. If the lock is not reset, will no longer consider as a neighbor. It does not matter if the misbehaving device (that dropped the message) was or. Both and will stop regarding each other as neighbors, and thus, will not be able to exchange messages.

3.2. Records and Messages

From the perspective of a TMM, a record is of the form, and is associated with a record hash

(1)

A destination record (DR) for a destination is of the form where the four values are the sequence number, time of expiry, hop count, and next hop. The DR for a destination is created by TMM. As the clocks of different TMMs are not synchronized, the time of expiry is in terms of the clock of the TMM of the device in which the DR is stored. A DR with sequence number 0 is interpreted as a empty record.

The NR for a neighbor specifies 3 values (time neighbor was last-heard-from, the offset of the neighbor’s clock, and lock (the fourth value is always zero, and is ignored). Once again, all values of time are according to the clock of the TMM in the device storing the NR. An NR with first field is interpreted as an empty record.

TMMs exchange authenticated messages (authenticated using pairwise secrets) of three types-HLO messages, DR messages that convey a DR, or data messages that convey the hash of a data packet. All messages have a common format

(2)

where is the identity of the sender (TMM that created the message), is the type of message (HLO, DR or DATA); is a time-stamp of the sender, is an acknowledgement field, which is 0 for a spon- taneous message, and for an ACK, set to the time-stamp of the message that is acknowledged. The value is the identify of a destination, and is a cryptographic hash.

In DR messages is destination that created the DR conveyed by the message. In DATA messages is the ultimate destination of the data packet whose hash is conveyed by the message. In HLO messages. In a DR messages the value is the record hash of the received DR for. In a DATA message is a one way function of the source of the data packet and the hash of the data packet.

3.3. TMM Functions

The functional components of TMM can be broadly classified into a) IOMT functions that enable the TMM to maintain two virtual databases-a DT and NT-by storing only the IOMT roots; b) mutual authentication functions; and c) protocol specific functionality expressed as an algorithm executed inside TMMs.

These functional components are accessed through interfaces exposed by the TMM. IOMT related functions, and that perform simple sequences of hash operations and issue various types of self-memoranda. A self-memoranda issued by a TMM to itself (for use at a later time) is authenticated using a secret known only to the TMM.

Function is used to initialize a TMM to operate in a MANET. Function is used to notify the TMM of the occurrence of an “event”. An event can be receipt of a message from another TMM, or a request from the device (for example to send a DR, initiate a data packet, remove a stale DR/NR, etc); stores event (message) specific parameters like, , , , , and the event time (time at which the occurrence of the event was notified) in a reserved event register E inside the TMM.

Function which executes. Inputs to include two DRs for (a stored DR and a received DR) and two NRs (for and). Depending on the nature of the event, execution of may result in the modification of up to the three records (a DR and two NRs). Accordingly, updates the IOMT roots and creates messages dictated by two outputs and of algorithm.

Inputs to also include self-memoranda which simultaneously enable the TMM to 1) verify the consistency of the DRs and NRs against the current IOMT roots, and 2) modify the roots in accordance with the changes to the DR/NRs resulting from execution of. ensures that only DRs/NRs consistent with the current IOMT state can be provided as inputs and modified only as specified by the algorithm. On completion of the device is expected modify the DR and two NRs in exactly the same manner. If not, the DR and the NRs will no longer be recognized as consistent with the IOMT roots stored inside the TMM (as inconsistent DRs cannot be advertised to other devices or used for forwarding data packets; and no messages will be accepted from/sent to neighbors with inconsistent NRs). The device is also expected send the messages to and. If not, an acknowledgement from can not be submitted to the TMM (as TMM messages can not be faked) to reset the lock in the neighbor record of, which will result in the loss of the link to.

3.4. Distance Vector Algorithm

Protocol specific components of the TMM based approach include a specification of constants, and the algorithm (Figure 1). The inputs to include a DR for two NRs (and), event related parameters, and constants and. If the implication is that no DR has been provided as input (if no NR for is provided). it signifies an empty DR. implies an empty NR for. implies self-DR (as is the TMM identity). Most often, the neighbor is the source of a event (or), and the neighbor is the next hop in the DR for (or) .

In the algorithm in Figure 1 the events can be classified into three broad categories: 1) request from the device (, lines 3 - 16); 2) message from (or, lines 1 - 2 and 17 - 29) and 3) message from (, lines 30 - 33). Exection of may result in the modification of the DR/NRs and two outputs and which specify the nature of the message to be sent to and respectively.

The constant is the maximum permitted round trip time to recognize the existence of a neighbor. If (empty record for) and if the received message from is an ack., such that, a successful handshake has occurred (lines 1 - 2). The time according to the sender is roughly in terms of the receivers clock. The clock offset of the sender is then. .

Adding a NR for after a successful handshake causes the NR for to change from. Once a NR has been added, the neighbor is expected to periodically affirm it’s continued presence by sending messages (HLO messages if there is no reason the send other messages). On receipt of a message from with a time stamp the last-heard-from field is updated to.

The value is the maximum period of silence. If the time stamp in the NR for is older than a duration, will no longer be considered an active neighbor. Messages will not be accepted from inactive neighbors. Consequently, their time-stamps can not be updated. However, an NR for an inactive neighbor can not be removed as soon as they become inactive. If no ack. is outstanding a stale NR for can be removed if has been inactive for duration. If the neighbor has been inactive due to failure to send an

acknowledgement, the inactive NR is retained for duration (lines 3 - 5). The reason for retaining a stale NR of for some duration is to ensure that can not be added back as a neighbor (after performing a handshake).

DR and DATA messages can be sent only to active neighbors, and only if the neighbor does not have the lock set. A neighbor is active at event time if. To send a DR message to to send the DR for a value is set to 1. To send the DR to the value is set to 1. When a DR or DATA message is sent to active neighbor with, the lock is set to. Later, when an ack. is received from with, the lock is reset.

An acknowledgement for a DR/DATA message from can be sent by setting or. Specifically, implies a simple acknowledgement (the only purpose of which is to reset the lock). is a DR message that simultaneously acknowledges a received message and conveys a DR. implies initiation of a DATA message to; implies relaying a DATA message to.

For example, when a DATA message is received from to indicating as the destination, if the DR for is usable, and the next hop is active, then a simple acknowledgement is sent to (by setting); to forward the DATA message to the value is set to 5. However, if no valid DR for exists, the acknowledgement sent to also conveys the bad DR for so that can update it’s DR for (as the DR has been invalidated). Similarly, when an invalid DR message is received for and the stored DR is good, the good DR is sent along with the ack.

Creating a new DR for itself implies incrementing the monotonic counter and using it as the sequence number for the freshly created DR. The time of expiry is set to. Hop count is set to 0, and next hop is set to itself (line 7). The self DR can be sent to if is active (line 8).

Lines 9 - 13 depicts events for which DR needs to be updated on request by the device: setting height to in an expired DR (line 10); deleting an expired DR (line 11); setting hop count to as the next hop is inactive (line 12).

Lines 13 - 15 depicts events for sending a DR to an active neighbor (line 13); initiate a data packet to by creating a DATA message to next hop in a valid DR (lines 14 - 15).

Lines 17 - 29 correspond to events where a message has been received from active neighbor. Update time stamp if no lock has been set, or if the message is an ack. that clears the lock (line 18); DATA message with the receiver as the destination; send ack to (line 19). DR message (line 20 - 24), updated and acknowledged as the received DR is better or fresher (lines 21 - 22). When a DR is updated the expiry time is converted from the sender’s clock to receiver clock. If the stored DR is better (line 23), ack with stored DR only if has no outstanding acks (else a simple ack is sent-line 24).

DATA message (lines 25 to 27) from with which is not an ack; relayed to the next hop (if a path exists to) along with an ack to (or); if path does not exist DR message is sent to as ack.

Lines 30 - 33 is the source of a DR message. The DR is updated (lines 31-32) if fresher or equally fresh. The time stamp is updated and an ack created. can be the source of DR messages under three conditions: 1) when no DR currently exists and the DR supplied by makes the next hop; 2) when provides an update (which could be a shorter or longer path); or c) if in response to a DATA message sent to the next hop, a DR message is received (route error).

4. Index Ordered Merkle Tree

A binary Merkle hash tree is constructed using a pre-image resistant hash function (for example, SHA-1). A tree with leaves has nodes distributed over levels, where. At level 0 are leaf-nodes: one corresponding to each leaf (a database record), typically derived by hashing the leaf. At level 1 are nodes, each computed by hashing together a pair of adjacent nodes in level 0. More generally, level has nodes computed by hashing a corresponding pair of nodes in level, and so on, till we have a lone node at level―the root of the binary tree.

4.1. IOMT Leaves and Nodes

An IOMT is very similar to a merkle tree except for the imposition of a special structure for every leaf. The leaves of an IOMT take the form

(3)

where is the index of a record bound to the leaf, is the next index, and is the record-hash for a record corresponding to index. Every leaf points to the leaf with the next higher index; the leaf with the highest index wraps around and points to the leaf with the lowest index. If then the record bound to index is empty.

Corresponding to a leaf is a leaf node computed as. A leaf bound to an empty record (third field zero) is a “place holder” for the index.

Two sibling nodes and in the same level of the binary tree are hashed together to compute their common parent as

(4)

At level of an IOMT with leaves are leaf nodes-one for each leaf. Level 1 of the tree has nodes, level 2 has nodes, and so on. The lone node at level is the root of the tree.

Prover and Verifier: The prover stores all records, leaves, and nodes. The verifier stores only the root of the tree. For purposes of this paper, the prover is the untrusted device; records are DRs/NRs in the DT/NT maintained by the device. The verifier is the TMM in the device.

In the tree maintained by the prover, if a node at level is an ancestor of a node at level, the prover can readily can readily identify a set of nodes, such that repeated applications of starting with will result in. Let us denote by, such a sequence of operations. If the hash function is pre-image resistant it is guaranteed that (given), it is not feasible to determine or satisfying or.

Thus, if the root of the IOMT is, and if the verifier (TMM) is provided values required to verify that is a child of (or), the TMM is convinced of the existence of record with record-hash for index 4. Simultaneously, the existence of a leaf also conveys to the TMM, the non-existence of any leaf with index that falls between 4 and 7. Likewise, the existence of a leaf (say) (with a wrapped around pointer) indicates that no leaf exists for an index greater than 7, or less than 2.

Inserting/deleting a place holder does not affect the integrity of the NT/DT. However, the roots before and after insertion of a place holder are different. Two roots and one before insertion/deletion and one after insertion/deletion of a place holder are considered as equivalent roots.

4.2. IOMT Functions

TMMs expose a function (Figure 2) that performs operations verify the existence of a specific relationship――between two nodes and. Having verified that is a child of in an IOMT, outputs a self-certificate (a memorandum to itself) to remind itself that “it has been verified by me that is a child of.” Such self-certificates are authenticated using a secret―a secret that is ran- domly generated every time a TMM is powered on/initialized.

This secret is used to compute message authentication codes (MAC) for such self-memoranda. Three type of self-memoranda are issued by TMM functions.

(5)

A function takes a node, and a set of complementary nodes, and a value (which may be the same as), and computes, and to issue a certificate binding and. Function combines up to 3 certificates issued by to issue a certificate. generates equivalence certificates for roots before and after insertion/deletion of a place holder.

Function combines three certificates to issue a certificate. From certificates and it follows that is a common parent of leaf nodes and (and if and, then). From the third certificate, as is an ancestor of it is simultaneously an ancestor of and, and thus, if and then.

verifies equivalence relations that involve insertion or deletion of place-holders. Consider a scenario where an IOMT includes two leaves: a leaf for index, viz., , and a place-holder for an index, of the form. If the place holder for is to be removed, then the leaf for index should be modified to, and the leaf should be replaced with an empty leaf. In other words, to delete the place holder, a tree with nodes and a node should be replaced with and (leaf-hash of an empty leaf is 0). Now, given a certificate (or) it can be inferred that changing a root from is equivalent to removing a place-holder.

If the input is zero, this function assumes that one of the two equivalent roots is zero, and the other corresponds to a tree with a lone place-holder. As the root of a tree with a single leaf is the same as the leaf hash, in this case the other root is.

Note that if changing an IOMT root from corresponds to deleting a place-holder, changing an IOMT root from corresponds to inserting a place-holder. The TMM does not care if an equivalence certificate is being used to insert/delete a place holder, or care about the index that is deleted/inserted.

Two IOMT roots and are stored in internal registers of TMMs. Such roots can be modified due to different events using, by providing appropriate and certificates. The IOMT roots can also be changed to an equivalent root (for purposes of inserting/deleting place holders in either tree).

Specifically, function exposed by TMMs can be used to insert or delete place holders in the DR tree with root or NR tree with root.

Form the perspective of TMMs a self-certificate satisfying is proof that is leaf node in the DR tree. Now, if there exists values (say) satisfying, the TMM concludes that is the hash of record in the DR tree. Similarly, a self certificate satisfying along with IOMT leaves and that are pre-images of and respectively, and records and that are pre-images of record hashes and respectively, can be provided as proof of existence of two NRs for neighbors and in the NT.

A DR is of the form and an NR if of the form (the fourth value is not used in NRs). As we shall see in the next section such certificates are used by to simultaneously verify the integrity of IOMT leaves before they are modified against the current root, and modify the root according to the modification to the records by function.

5. TMM Architecture

TMMs are resource limited modules that have only modest computational and storage abilities. They perform only simple logical operations necessary to execute and hash operations required to maintain IOMTs, compute pairwise secrets, and MACs.

Figure 3 depicts the internal registers of TMMs. Protected non-volatile registers are reserved for the TMM identity, a secret issued by a trusted key distribution center (KDC), and a monotonic counter. The self-identity is used for creating DRs for. Every time a DR is created, or whenever a TMM is initialized, the monotonic counter is incremented. The secret is used for computing pairwise secrets shared with other TMMs.

The volatile registers include the IOMT roots and. TMMs possess a volatile clock tick counter which can be set to any value when a TMM is powered on/initialized, and thereafter, incremented at the same rate in all TMMs. is the self-secret generated whenever a TMM is initialized (which is used for self-MACs). Contents of the event register E, and input register I and constants C are used by algorithm to modify records in the input register, and set values and.

A function initializes a TMM and sets the contents of a registers C and, sets the clock to a value provided by the device, initializes the roots of the NT and DT to zero, increments the monotonic counter, and generates a new self-secret using a random sequence generator RSG().

5.1. Mutual Authentication

Several low complexity key distribution schemes exist to facilitate computation of pairwise keys between two entities. The Modified Leighton Micali Scheme (MLS) [6] is well suited for dynamic networks with a soft limit on the maximum network size. In MLS scheme every node needs to store a single secret, and a pairwise public value corresponding to every node that was inducted earlier into the network. At a time a network has grown to (say) a million entities, the worst case storage requirement is for the last entity inducted into the network, which will need to store a secret and 999,999 public values. The 1000th entity will need to store only 999 public values.

Even if each public value is 16 bytes long, the worst case storage for a network that is expected to support up to 10 million entities is only 160 MB. In practice, as storage-especially unprotected storage-is indeed an inexpensive resource, even for mobile devices. Thus MLS, which requires only a single hash operation to compute a pairwise secret is especially well suited for computing pairwise secret between TMMs. The TMM needs to store only a single secret. The public values can be acquired (from the network operator) and stored by the untrusted device.

The secret is used by TMM to compute shared secrets with other TMMs. Specifically, any two TMMs and can using their respective KDC secrets and to compute a common secret

(6)

where and are pairwise public values made available to the untrusted devices that house TMM and respectively. If MLS is used to compute the pairwise secret only one of the two nodes (or) requires access to a public value; the other node employs the public value of 0 (if, then; if then).

The MAC secret shared between two TMMs and is a function of, the respective monotonic counter values and, and a value used to initialize all TMMs taking part in the same application (for example, TMMs in all devices taking part in the same MANET). The value is a one-way function of protocol-specific constants.

The MAC secret used by TMM for computing MACs for outgoing messages to TMM, and the MAC secret used by TMM for verifying MACs for messages from are computed as

(7)

If the MAC secret employed for a message is, the MAC for the message created by, viz., is computed as

(8)

Note that as the MAC secret if a function of, TMMs initialized with different values of will not agree on the MAC secret (and thus cannot exchange messages). Furthermore, as is a function of the session counters and, a message generated when the counters of the sender and receiver were and can not be replayed if either or has been modified.

Receiving Messages: TMMs accept messages from other TMMs, or request from the device, and store contents of the message/request in the event register

(9)

Note that apart from the contents of the message, the time at which the message was submitted is also recorded in the field as the “event time.”

A function accepts messages from a neighbor, verifies the MAC and stores the message contents in register R. In addition, can also be used to create HLO messages―either on request by the device, or as an acknowledgement for a received HLO message. If is invoked with message source this is construed as a request from the device that conveys a type of request and a value. If is invoked with input MAC set to zero, this is interpreted as a request to create a HLO message for a neighbor. Else, the contents of the message are verified to be consistent with the MAC. If consistent the message register R is populated. In addition, if the message is of type HLO, then a MAC for an acknowledgement message with time stamp is created.

5.2. Updating TMM State Using

Function is invoked to notify the TMM of the occurrence of an event-either a message received from another TMM, or a request from the device, and populate event register E in the TMM. Processing the event involves execution of, which requires access to a currently stored DR for a destination, a received DR for consistent with (if the event is a DR message), currently stored NRs for up to two neighbors and, and protocol specific constants. After processing the event, the end result is a change in the TMM state, and creation of up to two message (one for and one for).

As the response to the event may require modification of 3 records, the TMM will expect a certificate that simultaneously certifies the integrity of the current state (before the event) and future state (after processing the event) of a DR for, and a certificate that simultaneously certifies the integrity of the current state (before the event) and future state (after processing the event) of two NRs (and). Specifically, the certificate instructs the TMM as to how the IOMT root should be changed due to the change to the DR; the certificate instructs the TMM as to how the IOMT root should be changed due to the change to the NRs and.

The register I is used to store other inputs necessary to process an event by executing. Specifically, the inputs include 1) a leaf from the DT IOMT for a destination, except that instead of the third value, the pre-image is provided as input; 2) a record consistent with value in the received DR message; and 3) two IOMT leaves (and) from the NT tree; once again, instead of the value, the pre-images are provided;

The contents of the input register are provided as inputs to a function which makes the appropriate changes to records and, accordingly modifies TMM state, and outputs MACs for messages. Apart from contents of the input register, other inputs to are a ) the next states and; and b) a certificate and a certificate.

Function verifies that if the message is of type DR, then the record is consistent with and notes down the current record hashes and of the three records provided as inputs, and copies the contents of the leaves to the input register I.

The protocol specific function performs necessary modifications to the records. expects specific pre-conditions to be satisfied, failing which return error and terminates. On successful execution of the DR and two NRs may be modified. In addition, instructs the types of messages to be sent to and by setting values and.

Till this point had simply assumed that the leaves for and provided as inputs were consistent with the current IOMT roots. The four values and and simultaneously permits the TMM to verify this assumption, and modify the IOMT roots in accordance with the changes made to the DR and two NRs.

By providing contents of a leaf in the DT and two leaves in the NT, the device claims that such such leaves are consistent with the IOMT roots and respectively. Let, , and. Specifically, if and (where is the record hash after modification of the record in response to the event) then the certificate should satisfy. Similarly, if the leaf hashes corresponding to and are and before the event, and and after the event, the certificate should satisfy or.

If the preconditions (before execution of) and post conditions (after execution) are consistent with the current state and the next state the IOMT roots are modified to.

Finally, output messages are created depending on the values and. Inputs and (and) to are necessary for computing the MAC secret to be used for the message to (). Recall that are spontaneous (not ACK) messages: instructs creation of a DR message. instructs creation of a DATA message to initiate a data packet to. instructs creation of a DATA message to relay a received DATA message to the next hop. are acknowledgments; is a simple acknow- ledgement; is a DR message that simultaneously acknowledges a received DR/DATA message and conveys a DR.

5.3. Deploying TMM Based MANETs

For MANET secured using TMMs every device has a TMM. A (perhaps off-line) administrator/operator of the MANET specifies the constants to be used. The off-line administrator is also responsible for ensuring that every device has access to public values necessary to facilitate computation of pairwise secrets between TMMs in devices.

To operate in a MANET the device is required to initialize it’s TMM. At this point the device has no records, and the IOMT roots are zero. From this point onwards the device has to maintain it’s DT/NT and the corresponding IOMTs to be in sync with the roots stored inside the TMM. Any number of place holders can be added in either tree by using certificate generation functions to create equivalence certificates and using to modify the IOMT roots accordingly.

As soon as a TMM is initialized the device can use to perform handshakes with TMMs in neighbors, and then invoke to insert neighbor records. Once a TMM recognizes neighbors, the TMMs own DRs can be incremented, and sent to active neighbors. Whenever a message is received from a neighbor the device submits the message to it’s TMM using and invokes to modify the TMM state/create messages. Before is invoked, as the device is aware of the precise changes that should be made to a DR and two NRs, the device can use IOMT functions to generate the necessary and certificates.

The broad assurance that all devices taking part in a MANET will modify DRs and NRs in exactly the same manner as dictated by the protocol (algorithm) is enforced as follows:

1) Only TMMs initialized with the same set of protocol-specific constants will agree on a pairwise secret. This feature is used to assure the integrity of protocol-specific constants.

2) IOMTs are used to ensure that only DRs/NRs consistent with the IOMT roots stored inside the TMM will be considered as valid;

3) As the function can not be modified, the DR/NRs consistent with the current IOMT roots can be modified only according to the algorithm.

4) After modification of the records the device is forced to modify it’s copy of the records in the same way.

5) If messages mandated by are not delivered by the device, the device can not retain the intended recipients of such messages as neighbors.

6. Related Work and Conclusions

Devices taking part in MANET offer an enormous attack surface that can be exploited by attackers. Specifically, hidden malicious functionality in component of the MANET device could be exploited to illegally modify 1) the MANET software, or 2) the DT/NT or the device’s clock, or expose secrets protected by the device to advertise arbitrary routing information, and/or construct clone devices with arbitrary functionality. Current efforts to secure MANETs simply ignore a wide range of attacks stemming from such issues. In the proposed approach to secure MANETs all such attacks are side stepped as no component of the device is trusted in the first place.

Prior efforts in the literature that attempt to secure MANET by leveraging a trustworthy computing module include [7] [8] that attempt to offer some assurances regarding the medium access control layer; the “nuglets of currency” approach in [9] ; the Bloom filter [10] approach in [11] , and the predecessor of the current work in [12] .

In [7] , the wireless transceiver is assumed to be inside a trusted boundary; in [8] the wireless driver is executed inside a trusted boundary. In [9] , nuglets of currency are maintained inside the trusted boundary; they are incremented/decremented based on selfish/selfless acts performed by the device. However, [9] does not address specific mechanisms that will enable a trusted module to unambiguously infer that the associated device has indeed performed a selfish/selfless task.

Gaines et al. [11] argued that mechanisms to guarantee integrity of MANET require resource limited trusted modules to be able to vouch for the integrity of destination table and neighbor table stored by the device. They also recognized the need for the trusted module to identify non existence of routing information. For this purpose, [11] suggested the use of Bloom filters to store succinct summaries of routing records.

In [12] the authors employed an index order merkle tree (IOMT) for keeping track of routing records. The specific improvements in this paper compared to [12] are extending assurance to relay of data packets, and locking mechanism to ensure that messages are not dropped by untrusted middle-men. The proposed approach can be easily extended to other routing protocols by specifying an alternate set of rules in place of. Our ongoing research efforts are directed towards identifying such rules for other routing protocols, and even applications that are totally unrelated to routing.

References