Share PDF

Search documents:
  Report this document  
    Download as PDF   
      Share on Facebook

Dynamic Source Routing using MD5 Hash Function in MANET

Abhinav Paliwal

Ashish Patnaik

Nabila Hyder

M.Tech (Research Scholar)

M.Tech(Research Scholar)

M.Tech (Research Scholar)

Dept of Computer Science &

Dept of Computer Science &

Dept of Computer Science &




JSS Academy of Technical

Galgotia College of Engineering &

Galgotia College of Engineering &

Education, Noida UP-201306

Technology, Greater Noida

Technology, Greater Noida










The Dynamic Source Routing protocol (DSR) is a simple and efficient routing protocol designed specifically for use in multi-hop wireless ad hoc networks of mobile nodes. DSR allows the network to be completely self-organizing and self-configuring, without the need for any existing network infrastructure or administration. The protocol is composed of the two mechanisms of Route Discovery and Route Maintenance, which work together to allow nodes to discover and maintain source routes to arbitrary destinations in the ad hoc network. When using source routing, each packet to be routed carries in its header the complete, ordered list of nodes through which the packet must pass. A key advantage of source routing is that intermediate hops do not need to maintain routing information in order to route the packets they receive, since the packets themselves already contain all of the necessary routing information. This, coupled with the dynamic, on-demand nature of Route Discovery, completely eliminates the need for periodic router advertisements and link status packets, reducing the overhead of DSR, especially during periods when the network topology is stable and these packets serve only as keep- alive.

General Terms

Mobile Ad hoc Network , DSR. protocol


Topology Creation and Route Discovery ; Cached Route , Route Reply, Route Request


An Ad hoc network has a certain characteristic, which imposes new demands on the routing protocol .The most important characteristics are the dynamic topology, which is a consequence of node mobility. A mobile ad-hoc network (MANET) is a network formed without any central administration which consists of mobile nodes that use a wireless interface to send packet data. The principle behind mobile ad hoc networking is multi-hop relaying, which means

messages sent by source to destination are forwarded by the other nodes if destination node is not directly reachable. In other words, an ad hoc node in MANET operates as not only end terminal but also as an intermediate router. Data packets sent by a source node may be reached to destination node via a number of intermediate nodes. Thus, multi-hop scenario occurs. In the absence of a security mechanism, it is easy for an attacker to insert, intercept or modify the messages. In ad hoc networks, the routing protocols are divided into three categories: Proactive, Reactive and Hybrid to avoid different attacks. Mobile ad hoc routing protocols can be classified in many ways depending upon their route construction and maintenance mechanisms, route selection strategy, topology formation, update mechanism, utilization of specific resources, type of cast, etc.

II.Literature Survey

Many of the security solutions to secure the routing in MANETs have been proposed. Some research papers which, focus on secure routing in mobile ad hoc networks are discussed below:

P. Papadimitratos and Z. Haas [3] proposed a secure routing protocol (SRP). SRP is based on a pre-share key between source and destination nodes. In SRP, a source node generates RREQ message and broadcasts it to its neighbors. When destination node receives RREQ message it verifies the source node and establish the route. Drawback of SRP is that it does not authenticate intermediate nodes. Author of [6] have shown the attack against the SRP protocol. In SRP protocol, an attacker can disrupts the normal functioning of this routing protocol in between source and destination nodes. Y.C. Hu, A. Perrig, and D. B. Johnson [4] proposed a secure routing protocol Ariadne. Ariadne protocol uses message authentication code (MAC) to maintain the message integrity and digital signature for authentication. In Ariadne protocol, the source node generates the route request (RREQ) message and appends a hash value to RREQ message. Each

intermediate node appends its identifier, digital signature and per hops value. When destination node receives RREQ packet it verifies source node and intermediate nodes, then sends back RREP message. Drawback of Ariadne is that it vulnerable to an active 1- 1 attack [4], where an attacker could delete the node’s signature to forge a nonexistent route. L. Buttyan and I. Vajda [6] proposed a new protocol EndairA. They enhanced the security of Ariadne protocol proposed in

[4]against active 1-1 attack [4] by providing security by appending the signature of source, destination and intermediate nodes. But EndairA protocol is vulnerable to active 0-1 attack [4] which is called Man in the Middle (MITM) attack. J. Liu, F. Fu, J. Xiao and Y. Lu

[5]proposed EndairALoc protocol. The authors of [5] have shown that the. EndairA [6] protocol is vulnerable to Man in the Middle (MITM) attack. EndairALoc protocol uses the pair wise pre-shared symmetric keys to construct the message authentication code (MAC) rather than public keys, randomly generated request identifier.

III.Dynamic Source Routing

Unlike AODV and DYMO, DSR is a source routing protocol. This means that the source node adds the whole route up to the destination node to the packets header . As this is the case with most reactive ad hoc routing protocols, DSR is based on the two basic mechanisms namely route discovery and route maintenance. During the route discovery a route is set up on-demand. The route maintenance monitors an established connection during a communication between nodes [2]. DSR is able to operate on networks containing unidirectional links but it works optimal in a network with bidirectional links

Option Type

Option Data









Target Address






Address [1]






Address[ 2]












Address[ n]





Figure 1: DSR data header packet format

A. DSR Basic Functions

If a source node originates a new data packet to some destination node, it adds the whole path “source route”

in the packet header. The source node searches for a route to that destination in its own route cache table . If it does not find an entry, it initiates a route discovery process to dynamically find a route to the destination node. Route discovery is similar to that in AODV. However, there are some differences. First, the RREQ packet broadcasted by a source nodes include a new field, the route record, which saves the nodes the RREQ packet traverses on it travels towards the destination node. Second, intermediate nodes receiving the RREQ check if their address is included in the route record. Third, if the RREQ packet arrives at the destination node, it checks its route cache for another route to the source node. If it finds one, the destination node generates a RREP packet adds the route record (from RREQ packet) and sends the RREP back to the source node over its own route. Therefore DSR can work in a unidirectional link field where the revise route is not available and using other routes for replying to the RREQs Otherwise, the destination node sends the RREP packet over the reverse route back to the source node. The route maintenance is processed as mentioned in AODV. If an intermediate node could not forward a data packet, it generates a RERR packet and sends it back to the source node. Whenever a node receives a RERR message, it deletes all its routes containing the broken link.





Source Route Record









































Figure 2: DSR cache route packet Format












Option Type


Option Data


























Target Address

Address [1]

Address[ 2]


Address[ n]

Figure 3: DSR RREQ packet format

Option Type

Option Data












Target Address








Address [1]








Address[ 2]
















Address[ n]







Figure 4: DSR RREP packet Header


Option Error Type

Reserved Slavage





Error Source Address

Error Destination Address

Type Specific Information

Figure 5:DSR RERR Packet format

B. Additional Features

In addition to the two basic mechanisms mentioned above, DSR protocol provides further features.

B.1 Route Discovery Features

n Caching Overheard Routing Information

If a node is forwarding or overhearing any routing packet it updates its own route cache.

n Replying to Route Requests Using Cached Route

If an intermediate node receives a RREQ packet to the destination and has a valid route to the requested destination, the intermediate node uncast a RREP packet back to the source node.

n Route Request Hop Limits

Each RREQ packet contains a "hop limit" or time-to- live “TTL” field in its IP header. The TTL is used to limit the propagation of the RREQ packet with the aim to reduce the routing control packets overhead on the network.

B.2 Route Maintenance Features n Packet Salvaging

Packet salvaging occurs if an intermediate node forwarding a data packet detects that the link to the next node is broken and it has another valid route to the destination in its route cache. Otherwise, the node drops

the data packet. In all cases, the ode sends back a RERR packet toward the source node.

n Automatic Route Shortening

If a node is able to overhear a packet carrying a source route, which will come to it later, the node should send back a RREP with the shorter path to the source node

n Increased spreading of Route Error Messages

If a source node receives a RERR, it propagates this RERR to its neighbors by including it in its next RREQ. In this way, the source node does not respond with a

new RREP contain the same invalid link.

IV. MD5 Hash

The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128- bit (16-byte) hash value.MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity. MD5 was designed by Ron Rivest in 1991 to replace an earlier hash function, MD4. An MD5 hash is typically expressed as a 32digit hexadecimal number. The MD5 hash also known as checksum for a file is a 128- bit value, something like a fingerprint of the file. There is a very small possibility of getting two identical hashes of two different files. This feature can be useful both for comparing the files and their integrity control.

A. MD5 Hash Properties

The MD5 hash consists of a small amount of binary data, typically no more than 128 bits. All hash values share the following properties:

Hash length

The length of the hash value is determined by the type of the used algorithm, and its length does not depend on the size of the file. The most common hash value lengths are either 128 or 160 bits.


Every pair of non identical files will translate into a completely different hash value, even if the two files differ only by a single bit. Using today's technology, it is not possible to discover a pair of files that translate to the same hash value.


Each time a particular file is hashed using the same algorithm; the exact same hash value will be produced.


All hashing algorithms are one-way. Given a checksum value, it is infeasible to discover the password. In fact, none of the properties of the original message can be determined given the checksum value alone.




In our protocol, when a node wants to communicates, it initiates route discovery process by generating a RREQ message. Source appends its digital signature (DS) to the message. Neighbors of source first verify the signature of source and make the decision accordingly. We added a one way hash function to the RREQ message to maintain the integrity of message. Therefore, deletion of a node from or any kind of modification in route list of RREQ message can be detected. Destination sequence number [12]in the protocol is added to make the loop free routing and to check the freshness of route control packet. Assume that S is the source node trying to discover a route to destination D and route from S to D exist via intermediate node M and N.

A. Assumptions are

1)The nodes which are within range of each other are neighbors.

2)All the nodes in network have their own public and private key pair generated by any key management system for mobile ad hoc networks.

3)Public key of nodes are known to others nodes in network.

B.Notations are

1)LI Life time (maximum number of hop) of a packet


2)Seq Destination sequence number.

3)DSA Digital signature of node A.

4)hA Hash value appended by node A to the message.

5)A *, node A broadcast a message.

6)B, node A sends a message to node B.

C.Operation of proposed protocol and format of RREQ and RREP messages

1.) S-> * RREQ <Seq, S, D, LREQ, < >, DSs, hS>

2.) M-> * RREQ <Seq, S, D, LREQ-1, <M>, DSs, DSM, hM>

3.) N-> * RREQ <Seq, S, D, LREQ-2, <M, N>, DSs, DSM,DSN, hN>

4.) D-> N: RREP <Seq, S, D, <M, N>, DSs, DSM, DSN,DSD, hD>

5.) N-> M: RREP <Seq, S, D, <M, N>, DSs, DSM, DSN,DSD, hD>

6.) M-> S : RREP <Seq, S, D, <M ,N>, DSs, DSM, DSN,DSD, hD>


The operations of protocol are shown above. A source S initiates route discovery by generating route request (RREQ) message. RREQ contains the address of source and destination, Seq, LREQ, route list of intermediate node which makes the route from source to destination

(initially empty), digital signature of source DSS, and a hash value hS. Life time of a packet refers to maximum number of hop which a packet can travel. On each broadcast, life time would be reduced by one automatically. If life time is reached to zero, packet would be discarded. Source produced the hS using one way hash function.

hS = H(S, D, Seq, LREQ) ………………...(1)

When a neighbor of S, M receives the RREQ message, it verifies the signature of source node. If source node is genuine node, M checks Seq and compare with Seq stored in its cache. If Seq is less M discards the packet. Otherwise, it appends its identifier to route list and digital signature DSM to the message and replaces the hS by hM and then rebroadcasts

hM = H(hS, M, LREQ-1)…………………(2)

Similarly, node N verifies signature of source and node M and checks Seq, and then appends its identifier to route list and digital signature DSN to the message, replaces the hM by hN and finally rebroadcasts.

hN = H(hM, N, LREQ-2)...……….………(3)

Finally, when destination node D receives the RREQ message, it verifies all the signatures contained in RREQ packet, compares Seq with previously stored Seq in its cache. If source and all the nodes in route list are genuine and packet is not outdated, the destination node, it computes:

hD = H(N, LREQ-2, H(M, LREQ-1, H(S, D, Seq,

LREQ) ))…(4)

and compares the value of hD with hN. If both values are same, the message integrity is verified. Otherwise message is discarded. If all the verifications are successful, the destination D creates a route reply (RREP) message and sends back to the source S via the path obtained by reversing the route list in RREQ packet. Route Reply (RREP) message contains Seq, addresses of source and destination, route list, hD, and signature of all the nodes from source to destination.

Each intermediate node verifies the signature of destination D and Seq to check the freshness of message. On receiving RREP message at source, S verifies signature of all the nodes in route list and Seq. Source S computes:

h = H (N, LREQ-2, H (M, LREQ-1, H (S, D, Seq, LREQ)))….. (5)

and compares with hD to check the integrity of route list. If both values are same, S accepts RREP

.Otherwise discards. S calculates the values of LREQ-1 and LREQ-2 on the basis of route list. After successful completion of all verifications, a route from S to D is established.


The Dynamic Source Routing protocol (DSR) provides excellent performance for routing in multi-hop wireless ad hoc networks. In this paper, I have proposed a protocol to secure on demand source routing in MANETs that fulfills the security requirements. Our protocol uses one way hash function to maintain the integrity of message. Therefore, deletion of a node from or any kind of modification in route control packet can be detected. Using Public Key Cryptography (PKC), nodes can negotiate the session key for secure communication that fulfills the requirement of confidentiality. Source, destination and intermediate nodes in route list authenticate others nodes by verifying signature. Our protocol is based on Public Key Cryptography. Therefore, it consumes much battery power than protocols based on symmetric algorithms. DSR has very low routing overhead and is able to correctly deliver almost all originated data packets, even with continuous, rapid motion of all nodes in the network. DSR operates entirely on demand [12], with no periodic activity of any kind required at any level within the network This entirely on-demand behavior and lack of periodic activity allows the number of routing overhead packets caused by DSR to scale all the way down to zero. As nodes begin to move more or as communication patterns change, the routing packet overhead of DSR automatically scales to only that needed to track the routes currently in use.


[1]W. Huang, Y. Xiong, and D. Chen, “DAAODV: A Secure Ad hoc Routing Protocol based on Direct Anonymous Attestation”, Proceeding of International Conference on Computational Science and Engineering,August, vol-2, pp: 809-816, 2009.

[2]D. Cerri and A. Ghioni, “Securing AODV: The A- SAODV Securing Routing Prototype”, IEEE Communication Magazine: Security in Mobile Ad hoc and Sensor Networks, vol-46, pp: 120-125,

February, 2008.

[3]P. Papadimitratos, and Z. Haas, “Secure Routing for Mobile Ad hoc Networks”, Proceeding of SCS Communication Networks and Distributed Systems Modeling and Simulation, January, 2002.

[4]Y.C. Hu, A. Perrig, and D. B. Johnson, “Ariadne: A

Secure Ondemand Routing Protocol for Ad hoc Networks”, Proceeding of 8th Annual International Conference on Mobile Computing and Networking, (MobiCom 02), September 2002, pp: 12-23,.

[5]J. Liu, F. Fu, J. Xiao and Y. Lu, “Secure Routing for Mobile Ad Hoc Networks”, Proceeding of 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Distributed Computing, vol-3, 2007, pp: 314-318


[6]L. Buttyan, and I. Vajda, “Towards Provable Security for Ad hoc Routing Protocols”, Proceeding of 2nd ACM Workshop on Security of Ad hoc and Sensor Networks, October 2005, pp: 94- 105.