Route Authentication And Misdirection Detection Protocol Computer Science 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.

Abstract-The internet was originally designed to be trustworthy, reliable and extensible, while its infrastructure, mainly the routing mechanisms, was not constructed with security in mind. Moreover, routers are subject to malicious attacks that can harm individual users and hinder network operations. One of the subtle attacks is that a malicious router may collaborate in the control-plane and leave routing protocols operating properly to bypass the control-plane countermeasures and then targets the data-plane. Thus, it could forward packets to routes that are inconsistent with advertised ones in the control-plane, leading to so- called "misdirection" attack. In this paper, we focus on the misdirection attack launched in data-plane phase and propose a route authentication and misdirection protocol, RAMD, to authenticate the forwarding route before delivering data, and detect malicious routers that could misdirect traffic within autonomous systems that apply link-state routing protocols (e.g. OSPF).

Keywords: misdirection, secure data forwarding, detecting malicious routers, data-plane attacks.


Today, the rapid growth of the internet and continuing increase of many critical services such as web applications (e.g. e-mail, e-commerce) and real-time applications (e.g. Video conferencing, voice-over-IP (VoIP)) rely on the internet infrastructure to provide them with reliable, efficient and secure communications. However, the routing protocols that the internet is based on were originally designed to operate in a completely trusted and open environment, assuming no malicious nodes or attacking behavior, whereas, routing infrastructure was not constructed with security in mind [2], [3]. As a result, routers are subject to malicious attacks targeting not only a single subnet or individual users, but also the overall network performance [4].

However, attacks on routing protocols can be launched either in the control-plane i.e. the part where routers implements the routing protocols to exchange control and update messages that discover the topology and select the shortest paths, or in the data-plane i.e. the part where routers forward data along the computed paths [17].

Much research has focused on securing routing infrastructure by implementing countermeasures in control-plane. However, the researchers in [18], [20] argue that simply protecting control-plane is insufficient to secure data forwarding. An adversary could break into a router, leaving routing protocols operate properly in order to bypass the control-plane countermeasures and then target the data-plane. Thus, he can corrupt forwarding tables to meet his needs or install access control lists that arbitrarily or selectively misdirect data traffic to a route which is not the best or could even be the worst. As a consequence, misdirection attack results in significant network performance degradation, in particular, for critical applications (e.g. real-time applications),in addition to causing deliberate security violation by misdirecting traffic to a black-whole or monitoring point, besides disrupting network availability through DDoS attack [8].

The main goal of our work is to provide a lightweight, efficient and secure protocol to defend against traffic misdirection attack launched in data-plane phase. So we present the route authentication and misdirection detection (RAMD) protocol to authenticate the forwarding routes before delivering data, and detect the malicious routers that could misdirect traffic within Autonomous Systems (AS) that apply link-state routing protocols (e.g. OSPF [1]).

Our protocol is based on both probing and filtering techniques. In general, the aim of probing techniques [20-22] is to discover the forwarding route by sending probing packet to check for consistency with advertised routes, and detect the packet forwarding misbehavior. While the filtering techniques [23-25] aims to block packets with forged source address. So, our protocol requires the source to send a probe packet (called route authentication packet (RAP)) to the destination in order to authenticate the route before sending data, and update the filtering tables (called route authentication tables (RAT)) at every router along the selected route. Therefore, if the route is authenticated, the misdirected packets will be detected and the malicious routers that misdirect traffic will be addressed accordingly.

The rest of this paper is organized as follows: Section II describes our assumptions and threat model. Section III discusses related work, Sections IV discusses the traffic misdirection attack and its impacts on both network performance and security; Section V details the RAMD protocol, Section VI discuss the fault detection process, section VII discuss the response to detected malicious routers and section VIII presents paper conclusion and future work.


We assume link-state routing protocol (e.g. OSPF) in which routes maintain an identical link-state database (LSDB) and utilize it to recognize the complete image of internal network topology, so a router can calculate the shortest/valid route and determine the nodes sequence from source to destination, in addition to recognizing address spaces (networks prefixes or connected subnets) of each participating router along the route.

Also, we assume all routers en route to the destination operate with consistent LSDB, so any traffic misdirection caused by malicious or misconfigured nodes could be detected. Also, the attacker may compromise one or more routers in a network and has full-access control over those malicious routers, so he can modify the forwarding table or apply the desired access control list to attack data packet forwarding. Moreover, an active attacker may violate the detection protocol by modifying, dropping or misdirecting RAP to remain undetected; this type of attack is detected and addressed accordingly. Also, we assume each router is configured with a secret shared key with all other parties to assure the integrity and authentication of RAP by calculating the message authentication code (MAC) (e.g. using HMAC [19] over MD5 [6]) instead of digital signatures as they are computationally expensive to generate and verify. The distribution of symmetric keys is outside the scope of this work, however they can be provided by other approaches such as [16], [17]. Besides, we treat misconfiguration of routers as a security compromise and address them accordingly.


In general, the misdirection attack may occur as a result of attacks in control-plane or data-plane. In control-plane the adversary may send spoofed routing updates and accordingly cause false or "poison" routing tables, so the packets will be misdirected to incorrect routes.

Much research has been proposed to securing the control-plane by assuring the integrity and authenticity of routing updates messages [9-15]. Instead, we focus on defending against attacks in data-plane where a malicious node participates cooperatively in the control-plane to appear as trustworthy, but doesn't forward data packets correctly according to agreed-upon routing tables.

The earliest research on fault-tolerant forwarding is presented by Perlman [27], [28]. Perlman proposed a novel method for robust routing on top of the link state protocol based on source routing, digitally signed route-setup packets, reserved buffers. However, the protocol implementation details are left open. Subsequently, much research has been proposed to secure data-plane and detect malicious routers misbehavior such as passive monitoring and active probing techniques. Subramanian et al.'s [29] propose Listen protocol which passively monitors the data-plane at TCP level by comparing TCP Data and Acknowledgment packets to test the state of a route. This approach checks for gross connectivity only and can't detect whether packets have been dropped, modified or misdirected by malicious router(s). Bradley et al. [30] propose WATCHERS protocol that utilizes the conservation of flow principle to detect malicious routers that drop or misdirect packets. The conservation of flow principle states that all data bytes sent into a node, and not destined for that node, are expected to exit this node. So, the node can use counters to monitor traffic flow. By comparing with the counters of neighboring nodes, a node can detect which neighbor drops or diverts packets. This approach requires the existence of at least one good neighbor to an adversarial router. Hughes et al. [31] reviews the WATCHERS protocol and discusses several attacks that defeat the protocol, followed with suggestions for improvements to make the use of conservation of flow valid. On the other hand, active probing techniques require the source to send a hop- by- hop probes to discover the route and detect malicious routing. Traceroute [32] is a probing tool which is typically used to discover the route and obtain end-to-end statistics such as packet latency, loss, and route availability. However this tool assumes trust and cooperation between participating routers. Otherwise, a malicious router could appear misleading behavior by selectively allow the traceroute packets to pass through while dropping data traffic.

Padmanabhan and Sim [21] present secure traceroute protocol to securely trace the route and avoid an attacker to identify the probe packets (by using secret identifiers embedded in packets in order to single out those packets as probes). Hence, enabling end hosts or routers to detect and locate the source of routing misbehavior. Avramopoulos and Rexford [22] present Stealth probing mechanism that monitors the availability of paths in a secure (stealth) fashion by using IPsec to create an encrypted tunnel between two end-routers and send both data and probe packets into the tunnel. Thus, the adversary cannot drop the data packets without dropping the probe packets as well, making it difficult to evade detection. However, per the authors, the mechanism doesn't prevent traffic misdirection attacks. Also, this scheme incurs high computation and communication overhead. Avramopoulos et al. [33] present HSER protocol to detect and respond to malicious nodes. The protocol is based on source routing, hop-by-hop authentication, destination acknowledgment, sequence numbers; timeouts and fault announcements (FA) to detect dropped or misdirected packets. HSER requires each router to compute message authentication code (MAC) and fingerprint on a per packet basis, where the MAC is computed by the source n-times (where n: is the route length) and also, recomputed by each router en route to verify packet integrity .Moreover, a fingerprint of receiving packet is stored for a period of time. Therefore, HSER provides reliable end-to-end connections but the computation and communication overhead of this approach is quite high. X. Yang et al. [34] present SFMD protocol, which is an amendment to HSER, where intermediate nodes only need to perform one hash computation to a received packet, and the computation of MAC is only limited to source and destination. Based on their simulation, SFMD is more efficient than HSER, and could be suitable for wireless ad hoc networks.

On the other hand, RAMD is based on both probing and filtering techniques. The probing technique is similar to that's used in HSER and SFMD but does not require computation of fingerprints or MACs on a per packet basis. The use of MAC is limited only on RAPs to assure integrity and authenticity of them. In addition, we don't require storing fingerprints of data packets; consequently, a notable increase in performance and decrease in overhead will be obtained.

Fig1. Example of traffic misdirection attack. Assume the shortest path from A to I is: A-B-E-H-I which is initially calculated by router A using SPF algorithm. If router E is being malicious, it may misdirect the traffic to an invalid route A-B-E-F-G-I which is not the shortest or optimal routing path.In addition, rather than using cryptography-based techniques which incur high computation and communication overheads, RAMD utilizes the filtering techniques to detect misdirection attack in data-plane phase. However, the aim of filtering techniques is to block packets with forged source address. Some examples include Ingress Filtering [23], RPF [24], SAVE [25] and HCF [35].

Besides, the filtering technique we use is similar to SAVE with some substantial modifications. SAVE builds incoming (filtering) tables at each router en route, these tables include two main fields: source address spaces and valid incoming interface. The router can verify whether each received packet has arrived from the expected incoming interface according to the packet's source address, so the packets with forged source address could be blocked. In contrast to SAVE, RAMD builds RATs which include three main fields: source address spaces, destination address spaces and valid incoming interface. Also, updating of these tables is performed in a secure manner to avoid corrupting them by appending forged addresses. Therefore, SAVE is used to prevent IP spoofing attack, whereas RAMD is used to prevent both IP spoofing and misdirection attack.


In misdirecting attack, a malicious router may divert data traffic to an alternative path rather than a shortest optimal path calculated by a shortest path algorithm (e.g. Dijkstra algorithm [5]). So, the malicious router may misdirect to a path which is not the best or could even be the worst. This leads to significant network performance degradation, in particular, for critical applications (e.g. real-time applications), in addition to causing deliberate security violation. An example of traffic misdirection attack is illustrated in figure1.

In general, the impact of traffic misdirection attack may include [7]:

Sub-optimal Routing: here, the main objective of the attacker is to misdirect the incoming traffic to increase the latency, hence, in real time applications as video streaming and VoIP, the performance of the network is a critical issue, and so, incorrect routing path may cause the traffic to traverse on Sub-optimal paths that are either congested or longer than the optimal or shortest paths. As a result, network performance may be degraded leading to undesired operation of real time applications.

Congestion: flooding some route with high traffic will lead to so-called artificial congestion. So, the data could be lost as routers connecting the congested link will drop packets. However, this artificial congestion will not be solved by traditional control mechanisms.

Overwhelmed Host: By sending numerous number of spoofed packets to a victim node, this node will become overwhelmed and the running services will be no longer available. Moreover, the attacker may cause the system to shut down and thus prevent legitimate users from using system services. One of the prominent attacks that exploit traffic misdirection to overwhelm the victim node is Distributed Denial-of-Service Attacks (DDoS).

Looping: when packets are periodically forwarded among the same set of routers the Looping will occur. This can be caused when router A sends data to router B, which sends data to router C, which sends data back to router A. Therefore, this loop will continue until the Time to Live (TTL) value expires in TCP/IP.

Access to Data: A malicious router can misdirect the traffic to other nodes that benefit him to gain unauthorized access to data which would otherwise be inaccessible by original routing path.


Basic Approach

In general, routers rely on the destination address to forward packets without validating whether the incoming packet has been traveling through the correct path or not. Therefore, if it possible to determine which source and destination addresses that are allowed to communicate each other through a specific router, then this router can simply determine whether the incoming packet is in the correct path or not. Accordingly, it can prevent many attacks such as IP spoofing, DDoS, and misdirection attacks.

The basic idea of our protocol works as follows: every router en route to destination can build a filtering table (or RAT), appending to it the valid source and destination address spaces in addition to the valid incoming interfaces. Depending on this table, the router can verify whether the incoming packet has arrived from the expected incoming interface according to the packet's source and destination addresses. Therefore, we have two challenges in our protocol design: (1) How to build secure RATs to ensure that the packets will traverse only the correct paths and detect malicious routers that misdirect traffic. (2) How to react to routing updates and distinguish between normal routes changes and routes misdirection attack. To accomplish that, we can integrate both probing and filtering techniques, whereas, the source can initiate a probe packet called route authentication request (RREQ) carrying the nodes sequence from source to destination and waits for route authentication reply (RREP) from destination. This aims at authenticating the forwarding route before delivering data by verifying that the actual route is consistent with the route advertised in the control-plane phase, in addition to updating RATs at every router en route to destination. Besides, our protocol employs timers to enable routers to detect misdirection attack and react to routing changes.

Protocol Properties

To be secure, lightweight and efficient, our protocol should have the following Properties:

It should guarantee both authentication and integrity of route authentication packets with low computation and communication overhead. So, the message authentication code (MAC) (e.g., HMAC) could be used instead of digital signatures as they are computationally expensive to generate and verify.

It should be lightweight and avoid using online cryptographic operations at data packets delivery. Instead, the use of cryptography is limited to route authentication packets only.

It should immediately respond to routing changes and then update filtering tables only at routers that notice change in the nodes sequence of a route to a specific destination.

It should guarantee that the route authentication packets will pass through the same routers that data packets use to reach their destination in order to authenticate the path before sending data and create trusted filtering tables at those routers.

It should thwart replay attack; otherwise an attacker could intercept a valid route authentication packet and replay it to flood a destination, leading to DoS attack.

Protocol Details

Consider the shortest route vector R from source R1 to destination Rn is represented as follows: R =< R1, R2..., Rn >. So, we can define:

The route length || R || = n

The source R1 = R[1]

The destination Rn = R[n]

The corresponding addresses space vector S of R is:

S = < S1, S2…, Sn >.

So, whenever the source R1 has data to send to destination Rn, it firstly checks whether Rn exists in its RAT. If so, R1 can send data immediately assuming that this route has been authenticated. Otherwise, R1 starts the route authentication process by initiating RREQ packet to authenticate the route before sending data, and then setting a timer (TR) for RREP packet from Rn. The format of RREQ/RREP packet is summarized in Figure 2. The RREQ packet fields are set as follows: The Flag is set to ROUTE_REQUEST. The Sequence Number is set to RREQ sequence number to indicate packet version. (A newer RREQ has higher sequence number). The Nonce is set to a nonce value to defend against replay attack. (Every generated RREP packet has a fresh nonce value). The Nodes List is set to R. The MACs List is set to: {MAC12 MAC13… MAC1n}. Note: MAC1n is computed first and MAC12 is computed last. Where MAC1i is the computation of the message authentication code (MAC) using the secret key shared between R1 and Ri over the shaded fields in figure 2, and all existing MAC1j { j= i+1, i+2, ...n}.

When an intermediate node Ri receives the RREQ packet, it checks the following conditions:

Check whether the RREQ packet is valid by calculating the corresponding MAC1i. If the RREQ is valid, then it checks whether the RREQ is misdirected or not by validating next conditions.

Check whether Ri is included in the Nodes_List field at location k = 256-TTL (or if Ri = R[k]).

Check whether the previous hop Ri -1 equals to R[k-1].

Check whether the shortest sub-path from Ri to Rn (calculated by Ri) equals to <R[k], R[k+1]…, R[n]>.

Note: Based on the prosperity of Dijkstra algorithm: a sub-path of a shortest path is also a

shortest path, so each intermediate router Ri can utilize the RREQ sent by R1 to authenticate the sub-path from Ri to Rn without requiring to send additional RREQ. Ri just needs to validate condition 4.

If the above conditions hold, then Ri assures that the RREQ packet is valid and no malicious node has misdirected the traffic. Therefore, it forwards the RREQ packet to next hop and sets a timer (TR) for the RREP packet from Rn.

When Rn receives the RREQ, it checks conditions 1, 2 and 3 if they hold, then it responds with RREP packet to R1 along the reverse route < Rn, Rn-1...,R1 >. The RREP packet fields are set as follows: The Flag is set to ROUTE_REPLY. The Sequence Number, Nonce and Nodes List are set to the same corresponding values in the received RREQ packet. The MACs List is set to: {MACn1 MACn2… MACn(n-1)}Note: MACn1 is computed first and MACn(n-1) is computed last. Where MACni is the computation of MAC using the secret key shared between Rn and Ri over the shaded fields in figure 2, and all existing MACnj { j = 1, 2, ...,i-1}.

When Ri receives the RREP packet, it validates it by calculating the corresponding MACni ,if valid, Ri updates its RAT by appending the source address spaces <S1, S2…, Si-1 > to the Sources field and destination address space <Si+1,Si+2…,Sn> to the Destinations field and the ID of interface connecting Ri and Ri-1 to the valid incoming interface field.(Note R1 appends destination address spaces only, and Rn appends both source address spaces and incoming interface only).

Fig2. The RREQ/RREP packet format

On the other hand, the route may be changed as a result of normal routing changes or due to misdirection attack. Therefore, the route authentication process may not operate properly in the presence of routing updates due to inconsistent LSDB between routers for a period of time. To solve this problem, we can employ the routing updates timer (TU), whereas, every router receives routing updates will set this timer to give other routers enough time to update their LSDB and enable them to recognize the actual malicious nodes and avoid wrongfully accusing the well-behaving nodes as malicious So, if TU is set, then R1 can only start the route authentication process after TU expires. If the route authentication process is running and the routing updates are being received, then the router will set TU and cancel the present timer TR (if set). Also, the normal routing updates may cause the route to change or may not, so when Ri receives routing updates and concludes that the route to Rn hasn't been changed (by checking conditions 4) then the running authentication process will proceed normally and no need to restart it. Otherwise, if TU expires and the route is changed then Ri terminates the route authentication process without reporting faults.

However, if TU is not set (there is no routing update) and any of the following conditions doesn't hold: (1) RREQ/RREP is invalid (condition 1 doesn't hold). (2) RREQ is dropped (TR expires without receiving RREP). (3) RREQ is misdirected (condition 2, 3 or 4 doesn't hold). This means that the route authentication process fails as a result of misdirection attack. Therefore, the fault detection process is triggered to detect the faulty link or faulty router as described in fault detection section. However, the algorithms used by the source R1 and the intermediate/destination router Ri for the route authentication process are shown in figure 5 and figure 6 respectively.


In general, the malicious router could misdirect traffic passively or actively. In passive misdirection attack, the malicious router can misdirect traffic arbitrarily or selectively without violating the rules of the detection protocol. Otherwise, in active misdirection attack, the malicious router can misdirect traffic and seeks to sabotage the route authentication process by violating the detection protocol rules (e.g. dropping, modifying, or misdirecting RREQ/REEP packets) to evade detection.

Detecting active misdirection attack

If the route authentication process has completed successfully, then any malicious router en route to destination will be detected. Therefore, an active attacker will do his best to violate the protocol operation by dropping, modifying or misdirecting RREQ/REEP packets to keep undetected. So, whenever the router detects an active misdirection attack and the timer TU is not set, then it floods FA (with format shown in figure 3) and sets the fault code based on the following case number:

Fig3. The format of FA in active misdirection attack. The Flag is set to FA_Active , the Sequences Number and Nodes List fields are set to the corresponding values in the current received RREQ. The Detector is set Ri. The Fault Code is set to fault code based on the appropriate case number.

Fig4. The format of FA in passive misdirection attack. The Flag is set to FA_Passive , the Packet ID is set to the packet ID of misdirected packet. The Source and Destination are set to source & destination IP addresses of the misdirected packet. Detector is set the router that detects misdirected packets. Malicious router is set to the previous hop that misdirected packets.

If the timer (TR) expires before receiving RREP, Ri concludes that either RREQ or REEP packet is dropped by a malicious router, then, Ri detects that link < Ri , Ri+1 > is faulty.

If Ri receives a RREQ packet with invalid MAC, it concludes that a malicious router has modified it and then detects that link < Ri-1, Ri > is faulty.

If Ri receives a RREP packet with invalid MAC, Ri concludes that a malicious router has modified it and then detects that link < Ri , Ri+1 > is faulty.

If (Ri ≠ R[k]), then Ri concludes that a previous router has misdirected the traffic, so it detects that router Ri-1 is faulty

If (Ri = R[k]) and (Ri-1 ≠ R[k-1]), then Ri concludes that two or more previous consecutive routers collude to misdirect traffic, so it detects that the two routers Ri-1 and R[k-1] are faulty or at least one of the sub-routes from R[k-1] to Ri-1 is faulty.

If condition 4 doesn't hold, then Ri concludes that the source R1 is malicious since it attempts to authenticate invalid route, moreover, all routers<R[k-1], R[k-2]…, R[1]> colludes to misdirect traffic. So they are detected as faulty.

Note: in our protocol, if the link is detected to be faulty, we cannot exactly tell whether the upstream router, downstream router or the link is faulty so any of them may be faulty.

Otherwise, if TU is set, and then the fault is detected (based on previous cases), the route authentication process will be terminated without flooding FA.

Detecting passive misdirection attack

In this attack, the attacker aims at misdirecting data traffic without violating detection protocol. So, when the route authentication process completes successfully, each router en route can rely on its RAT to detect the malicious routers that misdirect traffic in data-plane phase. For example, in scenario shown in figure 1, assume the correct route from A to G is A-C-F-G, so after the route is authenticated using our protocol, router F updates its RAT as follows: <SA SC > are appended (in sequence) to the Source field, SG is appended to the Destination field and the valid incoming interface is set to 1. Therefore, if the malicious node E tries to misdirect traffic to invalid route (as shown in figure1), then router F checks its RAT and easily detects that the traffic is misdirected by the malicious router E. therefore, F floods FA as shown in figure 4 and sets the fields as follows:

The Source is set to: A. The Destination is set to: G. The Detector is set to: F. The Malicious Router is set to: E. The Packet ID is set to a value computed by the source to distinguish packets.

Distribution Detection

relying on a single router to announce faults is not an efficient scheme, so unlike other approaches that are limited on source to detect faults and announce them, rather, in our protocol, each router detects a fault can immediately flood FA to inform all other routers about the problem and provide them all significant details (source route, sequence number and fault code). So, the router can utilize the fault code in FA and use the diagnosis algorithm to analyze and detect the fault links or fault routers.

This approach prevents malicious router from announcing invalid reports and enables correct routers to rely on the collected information to diagnose and detect the faults, then synchronize the detected faults between them. Therefore, the efficiency of detection could be improved dramatically.


Once a router detects a router or link to be faulty then, it floods cryptography protected FA with appropriate fault code to enable other routers to detect the fault. So these FA's could be disseminated via the flooding mechanism of link state protocols. As a consequence, the malicious router/link will be removed from the routing fabric and the routing tables of valid routers will be changed to avoid using the detected malicious routers. In addition, over a time, an alarm should be raised so the network operators can respond with proper actions. in addition, we suggest applying priority-based mechanism to respond to misdirection attack in data-plane phase, whereas critical or secure applications and services may be given high priority and won't be allowed to traverse unauthenticated routes, hence the detector will forward low-priority misdirected packets and drop high-priority misdirected packets, until the malicious router is detected and the correct route is authenticated.


In this paper ,we focus on a misdirection attack launched in data-plane phase and present RAMD protocol to authenticate the route before sending data, and detect the misconfigured or malicious routers that could misdirect the traffic or incorrectly forward packets within autonomous systems (AS) that apply the link-state routing protocols (e.g. OSPF). However, RAMD doesn't require computation of fingerprints or MAC on data-plane phase as in SFMD and HSER protocols, as a consequence, we believe that RAMD has better performance in detecting misdirection attack and has little communication and computation overhead. As a future work, we will evaluate our protocol in NS2 simulation and compare our results with other related protocols (e.g. SFMD, HSER).