Network Is A Local Area Network Engineering Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.


An ad-hoc network is a local area network (LAN) that is built spontaneously as devices connect. Instead of relying on a base station to coordinate the flow of messages to each node in the network, the individual network nodes forward packets to and from each other. In Latin, ad hoc literally means "for this," meaning "for this special purpose".

A routing protocol in such a network finds routes between nodes, allowing a packet to be forwarded through other network nodes towards its destination. In contrast to traditional network routing protocols, for example for wired networks, ad hoc network routing protocols must adapt more quickly, since factors such as significant node movement and changing wireless conditions may result in rapid topology change. This problem of routing in ad hoc networks is an important one, and has been extensively studied. Ad hoc networks are targeted at environments where communicating nodes are mobile, or where wired network deployment is not present or not economical. Many of these applications may run in untrusted environments and may therefore require the use of a secure routing protocol. Furthermore, even when the presence of an attacker is not forseen, a secure ad hoc network routing protocol can also provide resilience against misconfigured nodes. Mission or safety-critical networks can use secure ad hoc routing protocols so that configuration errors, software bugs, or hardware failures do not disturb routing at other nodes.

In this paper, we present a new attack, the rushing attack, which results in denial-of- service when used against all previously published on-demand ad hoc network routing protocols. Specifically, the rushing attack prevents previously published secure on-demand routing protocols to find routes longer than two-hops. Because on-demand protocols generally have lower overhead and faster reaction time than other types of routing based on periodic (proactive) mechanisms, on-demand protocols are better suited for most applications. To defend this important class of protocols against the rushing attack, we develop a generic secure Route Discovery component, called Rushing Attack Prevention (RAP), that can be applied to any existing on-demand routing protocol to allow that protocol to resist the rushing attack.


We introduce here a new attack, which we call the rushing attack, that acts as an effective denial-of-service attack against all currently proposed on-demand ad hoc network routing protocols, including protocols that were designed to be secure. In an on-demand protocol, a node needing a route to a destination floods the network with ROUTE REQUEST packets in an attempt to find a route to the destination. To limit the overhead of this flood, each node typically forwards only one ROUTE REQUEST originating from any Route Discovery. In particular, existing on-demand routing protocols, such as AODV, DSR,LAR, Ariadne, SAODV, ARAN, AODV secured with SUCV, and SRP, only forward the REQUEST that arrives first from each Route Discovery. In the rushing attack, the attacker exploits this property of the operation of Route Discovery. We now describe the rushing attack in terms of its effect on the operation of DSR Route Discovery. other protocols such as AODV, Ariadne, SAODV, and ARAN are vulnerable in the same way.

In the network shown in Figure 1, the initiator node initiates a Route Discovery for the target node. If the ROUTE REQUESTs for this Discovery forwarded by the attacker are the first to reach each neighbor of the target (shown in gray in the figure), then any route discovered by this Route Discovery will include a hop through the attacker. That is, when a neighbor of the target receives the rushed REQUEST from the attacker, it forwards that REQUEST, and will not forward any further REQUESTs from this Route Discovery. When non-attacking REQUESTs arrive later at these nodes, they will discard those legitimate REQUESTs. As a result, the initiator will be unable to discover any usable route containing at least two hops. In general terms, an attacker that can forward ROUTE REQUESTs more quickly than legitimate nodes can do so, can increase the probability that routes that include the attacker will be discovered rather than other valid routes.

A rushing attacker need not have access to vast resources. On demand routing protocols delay ROUTE REQUEST forwarding in two ways. First, Medium Access Control (MAC) protocols generally impose delays between when the packet is handed to the network interface for transmission and when the packet is actually transmitted. In a MAC using carrier-sense multiple access, a node generally performs some type of backoff to avoid collisions; protocols like IEEE 802.11 also impose an interframe spacing time before transmission actually begins. Second, even if the MAC layer does not specify a delay, on-demand protocols generally specify a delay between receiving a REQUEST and forwarding it, in order to avoid collisions of the REQUEST packets. For example, if each node processes the packets it receives in order, and an inefficient REQUEST authentication mechanism is used, the attacker can keep other nodes busy authenticating REQUESTs containing bogus authentication, thus slowing their ability to forward legitimate REQUESTs.

Protocols employing public key techniques are particularly susceptible to these attacks, since they require substantial computation to validate each received REQUEST. A relatively weak attacker can also achieve faster transit of its REQUEST packets by transmitting them at a higher wireless transmission power level, thus reducing the number of nodes that must forward that REQUEST to arrive at the target. Since packet transit time at each hop is dominated by the processing time at the forwarding node, reducing the path to the target by just one hop is likely to provide a significant latency advantage, thus strengthening the attackers position. A more powerful rushing attacker may employ a wormhole to rush packets. In this case, the attacker simply forwards all control packets received at one node to another node in the network. This forms a tunnel in the network, where packets reaching one end of the tunnel are broadcast out the other end. If the tunnel provides significantly faster transit than legitimate forwarders, nodes near one end of the tunnel generally will be unable to discover working routes to the other end of the tunnel, since it will generally discover routes through the tunnel. In general, a wired tunnel will provide faster transit than native wireless forwarding, since node processing delay in forwarding is much longer than the propagation time. The rushing attack applies to all proposed on-demand protocols because such protocols must limit the number of packets that any node will transmit in response to a single Route Discovery.


In this we describe a set of generic mechanisms that together defend against the rushing attack: secure Neighbor Detection, secure route delegation, and randomized ROUTE REQUEST forwarding. We also describe a technique to secure any protocol using an on-demand Route Discovery protocol. In previous on-demand protocols, node B considers node A to be a neighbor when B receives a broadcast message from A. Secure Neighbor Detection, which replaces standard Neighbor Detection, allows each neighbor to verify that the other is within a given maximum transmission range. Once a node A forwarding a ROUTE REQUEST determines that node B is a neighbor (within allowable range), it signs a Route Delegation message, allowing node B to forward the ROUTE REQUEST. When node B determines

that node A is within the allowable range, it signs an Accept Delegation message. Randomized selection of the ROUTE

REQUEST message to forward, which replaces traditional duplicate suppression in on-demand route discovery, ensures that paths that forward REQUESTs with low latency are only slightly more likely to be selected than other paths. Figure 2 shows the basic design of our complete rushing attack prevention mechanis.


We use the following notation:

A or B denote communicating nodes.

A : h R {0,1}l denotes that node A randomly selects an l-bit long nonce h.

A R: (M,H(A || h)) means that node A sends B the message M and the hash of A's identifier concatenated with the nonce h.

A * : (M ,SM) means that node A broadcasts message M with its signature SM.

Secure Route Delegation

In our ROUTE REQUEST propagation, to enable each node to verify that all the secure Neighbor Detection steps were performed between any adjacent pair of nodes in the REQUEST, i.e., verify that both nodes of each adjacent node pair indeed believes to be a neighbor. We achieve this property through a Secure Route Delegation mechanism , S-BGP. S-BGP uses Route Attestations to ensure that each Autonomous System (AS) listed in the BGP AS path is indeed a valid AS. In S-BGP, before sending a route update to its neighbor, the AS signs a route attestation delegating it the right to further propagate the update. This mechanism enables to the nodes to verify that all the secure neighbor detection protocols were executed and that both neighbors believe that they are within transmission range. We describe the protocol based on an example. Consider two neighboring nodes A and B, where A received the current ROUTE REQUEST originating from node S destined for node R with the sequence number id. Node A engages in the secure neighboring detection protocol and finds after the second message that B is indeed within range, so it delegates the ROUTE REQUEST to B as follows:


SMA = Sign(H(MA)) A B : (SMA )

Node A does not need to send the message to B, as B can reconstruct all the fields of the message and verify the signature. The ROUTE DELEGATION message can be bundled together with the last message of the secure Neighbor Detection protocol. If B believes that A is indeed a neighbor within range, B will accept the ROUTE DELEGATION, continue the protocol, and sign another ROUTE DELEGATION with the next neighbor.

Randomized Message Forwarding

The secure Neighbor Detection and secure Route Delegation techniques are not sufficient to thwart the rushing attack, since an adversary

can still get an advantage by forwarding ROUTE REQUESTs very rapidly. We use a random selection technique to minimize the chance that a rushing adversary can dominate all returned routes. In traditional ROUTE REQUEST forwarding, the receiving node immediately forwards the REQUEST and suppresses all subsequent REQUESTs. In our modified flooding, a node first collects a number of REQUESTs, and selects a REQUEST at random to forward. There are thus two parameters to our randomized forwarding technique: first, the number of REQUEST packets to be collected, and second, the algorithm by which timeouts are chosen. Given perfect information, each forwarding node would collect the maximum possible number of REQUESTs before forwarding one, since this approach provides the most effective defense against a rushing attack. However, when the number of REQUESTs is chosen to be too large, randomized forwarding will heavily rely on the timeout to trigger REQUEST forwarding, increasing latency and possibly reducing security.

Secure Route Discovery

Three techniques in concert to prevent the rushing attack: our secure Neighbor Discovery protocol, our secure Route Delegation and delegation acceptance protocol, and randomized selection of which ROUTE REQUEST will be forwarded. The intuition behind Secure Route Discovery is to make the forwarding of REQUEST packets less predictable by buffering the first n REQUESTs received, then randomly choosing one of those REQUESTs. To prevent an attacker from filling too many of these n REQUESTs, since otherwise the attacker could simply rush n copies of a REQUEST, rather than a single REQUEST.

To limit the number of REQUESTs that traverse an attacker, exploit the fact that legitimate nodes forward only one REQUEST

in any Discovery. First, we require that each REQUEST carry a list of nodes traversed by this REQUEST. Second, we require a bidirectional Neighbor Verification for each link represented by this list of nodes, for a total of two signed Neighbor Verifications per hop. Third, to authenticate the node list, we require each node to authenticate the REQUEST it forwards, though it can piggyback this authentication together with the Neighbor Verification that it signs. Finally, we require buffered REQUESTs be duplicate-suppression unique: that is, if the route record of any two REQUESTs contain any node A, the route prefix leading up to (and including) A must be the same. These three requirements constrain an attacker to the extent that an attacker that has compromised m nodes can rush at most m REQUESTs. To prevent replay of old Neighbor Verification messages, each message is tied to a specific Route Discovery. Specifically, when a node S sends a Neighbor Verification for the link from S to R, S signs not just S and R (as in Figure 3), but also ties a unique Route Discovery identifier to the Neighbor Verification.

Integrating Secure Route Discovery with DSR

To integrate rushing prevention with DSR or other secure protocols based on DSR, we limit Route Discovery frequency as in Ariadne. Each time a node forwards a ROUTE REQUEST, it first performs a Secure Neighbor Detection exchange with the previous hop. When it forwards the REQUEST, it includes in the REQUEST a bidirectional Neighbor Verification for the previous hop. As in DSR, the target of a Route Discovery returns a ROUTE REPLY for each distinct ROUTE REQUEST it receives. Each such ROUTE REPLY is sent with a source route selected by reversing the route in the ROUTE REQUEST. This route is likely to work if there are no attackers on the route, since Neighbor Detection only finds bidirectional neighbors.

Simulation Evaluation

To evaluate the overhead of using our secure neighbor discovery mechanism in a non-adversarial environment, scheme is simulated using the ns-2 simulator, using Ariadne as underlying routing protocol. We call this modified protocol RAP (Rushing Attack Prevention).We used the original Ariadne source code , and modified it to use digital signatures based on HORS and geographical leashes for wormhole protection. RAP, on the other hand, would be able to discover working

paths much of the time, and as a result, would generally outperform existing on-demand routing protocols. Figure 5(a) shows the packet Delivery Ratio of the three protocols. DSR delivers between 99:8% and 100% of offered traffic. Ariadne delivers between 95:0% and 100% of offered traffic; a significant improvement over previous simulation results. This suggests that previous simulations used too high a traffic load to fairly evaluate Ariadne in the absence of congestion. Even with this light traffic load, RAP was able to deliver just 7:6% to 47:7% of offered load. This performance is primarily due to congestion. At higher movement speeds (lower pause time), the lower packet delivery ratio is caused by an even higher packet overhead, which results from the on-demand nature of the protocol Figure 5(b) shows the median latency of delivered packets. DSR and Ariadne appear to have zero mean latency, since their median latencies of 4:3ms and 3:8ms respectively are significantly lower than the 1050ms median latency of RAP. Two factors contribute to the higher latency of

RAP: first, congestion increases the time each node must wait to acquire the medium, and second, if a node receives just one ROUTE REQUEST packet from a Route Discovery, it waits a significant amount of time before forwarding that REQUEST in an attempt to collect enough REQUESTs and choose one at random Figures 5(c) and 5(d) show the Packet Overhead and Byte Overhead of the three protocols. At higher pause times, RAP has more than five times as much overhead when it uses five flows. This indicates that the congestion caused by the protocol significantly reduces the usefulness of the routing protocol packets. When congestion is not an issue, we actually expect that overhead should be less than a factor of five, because nodes can cache information they overhear, thus improving efficiency. Our performance evaluation shows that in non-adversarial environments, RAP adds significant costs relative to other secure routing protocols.

Security Analysis

This section discusses the security properties achieved with RAP when n distinct routes (both legitimate and attacking) exist between the originator and each other node in the network. Since routes are required to end in different nodes, an attacker with access to the keys of m compromised nodes can generate at most m distinct, maliciously injected ROUTE REQUESTs for the purpose of denial-of-service. To analyze the probability of a node subverting a Route Discovery, we assume that the attacker rushes m distinct REQUESTs to each node in the network. As a result, each node needs only n-m additional distinct REQUESTs. We also suppose that the network topology of these legitimate requests is represented by Figure 6,

such that the ` hops from the source to the target form a sequence of tiers, such that the n-m neighbors of the source form the first tier, the n-m neighbors of the target form the last tier, and any two adjacent tiers form a complete, bipartite graph.


Other secure routing protocols have been proposed based on periodic (proactive) mechanisms, for wired networks as well as for wireless ad hoc networks. Although these protocols typically are not vulnerable to rushing attacks, such periodic protocols are often less desirable for ad hoc network routing due to their higher overhead and slower adaptivity. Other areas in secure ad hoc network routing have been explored, such as trust establishment , key generation, nodes that maliciously do not forward packets, and security requirements for forwarding nodes.


In this paper, we have described the rushing attack, a novel and powerful attack against on-demand ad hoc network routing protocols. This attack allows an attacker to mount a denial-of-service attack against all previously proposed secure on-demand ad hoc network routing protocols. We have also presented RAP, a new protocol that thwarts the rushing attack. We found that the widely used duplicate suppression technique makes the rushing attack possible, and we designed a new Route Discovery protocol called RAP that replaces the standard mechanism and thwarts the rushing attack. Our approach is generic, so

any protocol that relies on duplicate suppression in Route Discovery can use our results to fend off rushing attacks. More importantly, we demonstrated that there are mechanisms that can defend against the rushing attack, even though all previous attempts at secure on-demand ad hoc network routing protocols have been vulnerable.


[1] Norman Abramson. The ALOHA System—Another Alternative for Computer Communications. In Proceedings of the Fall 1970 AFIPS Computer Conference, pages 281-285, November 1970.

[2] Dirk Balfanz, D. K. Smetters, Paul Stewart, and H. Chi Wong. Talking To Strangers: Authentication in Ad-Hoc Wireless Networks. In Symposium on Network and Distributed Systems Security (NDSS 2002), February 2002.

[3] Stefano Basagni, Kris Herrin, Emilia Rosti, and Danilo Bruschi. Secure Pebblenets. In ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2001), pages 156-163, Long Beach, California, USA, October 2001.

[4] Mihir Bellare, Ran Canetti, and Hugo Krawczyk. HMAC: Keyed-Hashing for Message Authentication. Internet Request for Comment RFC 2104, Internet Engineering Task Force, February 1997.

[5] Kirk A. Bradley, Steven Cheung, Nick Puketza, Biswanath Mukherjee, and Ronald A. Olsson. Detecting Disruptive Routers: A Distributed Network Monitoring Approach. In Proceedings of the IEEE Symposium on Research in Security and Privacy, pages 115-124, May 1998.

[6] Stefan Brands and David Chaum. Distance-Bounding Protocols. In Workshop on

the theory and application of cryptographic techniques on Advances in cryptology — CRYPTO 1994, volume 839 of Lecture Notes in Computer Science, pages 344-359. Springer-Verlag, August 1994.