Contents

Abstract 1. Introduction 2. Overview 3. Route Tables 4. AODV Terminology 5. Route Request (RREQ) Message Format 6. Route Reply (RREP) Message Format 7. Multicast Activation (MACT) Message Format 8. Group Hello (GRPH) Message Format 9. Security Considerations

Abstract
Ad-hoc networks are an emerging area of mobile computing. There are various challenges that are faced in the Ad-hoc environment. These are mostly due to the resource poorness of these networks. They are usually set up in situations of emergency, for temporary operations or simply if there are no resources to set up elaborate networks. Ad-hoc networks therefore throw up new requirements and problems in all areas of networking. The solutions for conventional networks are usually not sufficient to provide efficient Ad-hoc operations. The wireless nature of communication and lack of any security infrastructure raise several security problems. In this we attempt to analyze the demands of Ad-hoc environment. We focus on three areas of Ad-hoc networks, key exchange and management, Ad-hoc routing, and intrusion detection.

1. Introduction
The Ad hoc On Demand Distance Vector (AODV) routing algorithm is a routing protocol designed for ad hoc mobile networks. AODV is capable of both unicast and multicast routing. It is an on demand algorithm, meaning that it builds routes between nodes only as desired by source nodes. It maintains these routes as long as they are needed by the sources. Additionally, AODV forms trees which connect multicast group members. The trees are composed of the group members and the nodes needed to connect the members. AODV uses sequence numbers to ensure the freshness of routes. It is loop-free, self-starting, and scales to large numbers of mobile nodes. AODV builds routes using a route request / route reply query cycle. When a source node desires a route to a destination for which it does not already have a route, it broadcasts a route request (RREQ) packet across the network. Nodes receiving this packet update their information for the source node and set up backwards pointers to the source node in the route tables. In addition to the source node's IP address, current sequence number, and broadcast ID, the RREQ also contains the most recent sequence number for the destination of which the source node is aware. A node receiving the RREQ may send a route reply (RREP) if it is either the destination or if it has a route to the destination with corresponding sequence number greater than or equal to that contained in the RREQ. If this is the case, it unicasts a RREP back to the source. Otherwise, it rebroadcasts the RREQ. Nodes keep track of the RREQ's source IP address and broadcast ID. If they receive a RREQ which they have already processed, they discard the RREQ and do not forward it.As the RREP propagates back to the source, nodes set up forward pointers to the destination. Once the source node receives the RREP, it may begin to forward data packets to the destination. If the source later receives a RREP containing a greater sequence number or contains the same sequence number with a smaller hopcount, it may update its routing information for that destination and begin using the better route. As long as the route remains active, it will continue to be maintained. A route is considered active as long as there are data packets periodically travelling from the source to the destination along that path. Once the source stops sending data packets, the links will time out and eventually be deleted from the intermediate node routing tables. If a link break occurs while the route is active, the node upstream of the break propagates a route error (RERR) message to the source node to inform it of the now unreachable destination(s). After receiving the RERR, if the source node still desires the route, it can reinitiate route discovery.

The Multicast Ad hoc On-Demand Distance Vector (MAODV) protocol Multicast routes

are set up in a similar manner. The membership of these multicast groups is free to
change during the lifetime of the network. MAODV enables mobile nodes to establish a tree connecting multicast group members. Mobile nodes are able to respond quickly to link breaks in multicast trees by repairing these breaks in a timely manner. In the event of a network partition, multicast trees are established independently in each partition, and trees for the same multicast group are quickly connected if the network components merge. One distinguishing feature of MAODV is its use of sequence numbers for multicast groups. Each multicast group has its own sequence number, which is initialized by the multicast group leader and incremented periodically. Using these sequence numbers ensures that routes found to multicast groups are always the most current ones available. Given the choice between two routes to a multicast tree, a requesting node always selects the one with the greatest sequence number. MAODV is the multicast protocol associated with the Ad hoc On-Demand Distance Vector (AODV) routing protocol, and as such it shares many similarities and packet formats with AODV. The Route Request and Route Reply packet types are based on those used by AODV, as is the unicast Route Table. Similarly, many of the configuration parameters used by MAODV are defined by AODV.

2. Overview
Route Requests (RREQs), Route Replies (RREPs), Multicast Activations (MACTs), and Group Hellos (GRPHs) are the message types utilized by the multicast operation AODV. RREQs and RREPs are handled as specified in, except for certain procedures controlled by new flags. These message types are handled by UDP, and normal IP header processing applies. So, for instance, the requesting node is expected to use its IP address as the source IP address for the messages. The range of dissemination of broadcast RREQs can be indicated by the TTL in the IP header. Fragmentation is typically not required. As long as the multicast group members remain connected (with in a ``multicast tree''), MAODV does not play any role. When a node either wishes to join a multicast group or find a route to a multicast group, the node uses a broadcast RREQ to discover a route to the multicast tree associated with that group. For join requests, a route is determined when the RREQ reaches a node that is already a member of the multicast tree, and the node's record of the multicast group sequence number is at least as great as that contained in the RREQ. For non-join requests, any node with a current route to the multicast tree may respond to the RREQ. A current route is defined as an 4

unexpired multicast route table entry whose associated sequence number for the multicast group is at least as great as that contained in the RREQ. The route to the multicast tree is made available by uncasting a RREP back to the source of the RREQ. Since each node receiving the request caches a route back to the source of the request, the RREP can be unicast back to the source from any node able to satisfy the request. Once the source node has waited the discovery period to receive RREPs, it selects the best route to the multicast tree and unicasts the next hop along that route a MACT message. This message activates the route. Nodes monitor the link status of next hops on the multicast tree. When a link break on the multicast tree is detected, the tree branch should be immediately repaired through the use of the REQ/RREP/MACT messages. A multicast group leader is associated with each multicast group. The primary responsibility of this node is the initialization and maintenance of the group sequence number. A Group Hello message is periodically broadcast across the network by the multicast group leader. This message carries a multicast group and group sequence number and corresponding group leader IP address. This information is used for disseminating updated group sequence numbers throughout the multicast group and for repairing multicast trees after a previously disconnected portion of the network containing part of the multicast tree becomes reachable once again.

3. Route Tables
MAODV is a routing protocol, and it deals with route table management. Route table information must be kept even for ephemeral routes, such as are created to temporarily store reverse paths towards nodes originating RREQs. MAODV uses the following fields with each route table entry, which are based on the route table defined in the AODV - Destination IP Address - Destination Sequence Number - Hop Count (number of hops needed to reach destination) - Last Hop Count - Next Hop - Next Hop Interface - List of Precursors - Lifetime (expiration or deletion time of the route) - Routing Flags 5

The following information is stored in each entry of the multicast route table for multicast tree routes: - Multicast Group IP Address - Multicast Group Leader IP Address - Multicast Group Sequence Number - Next Hops - Hop Count to next Multicast Group Member - Hop Count to Multicast Group Leader The Next Hops field is a linked list of structures, each of which contains the following fields: -Next Hop IP Address -Next Hop Interface -Link Direction -Activated Flag The direction of the link is relative to the location of the group leader, i.e. UPSTREAM is a next hop towards the group leader, and DOWNSTREAM is a next hop away from the group leader. A node on the multicast tree must necessarily have only one UPSTREAM link. The IP Address of a Next Hop MUST NOT be used to forward multicast messages until after a MACT message has activated the route. The Next Hop Interface fields in the Route Table and Next Hop field of the Multicast Route Table are used for recording the outgoing interface on which the next hop can be reached. Nodes MAY also maintain a Group Leader Table, which is an association between multicast groups and their corresponding group leaders. The fields of the group leader table are the following: -Multicast Group IP Address -Group Leader IP Address

4. MAODV Terminology
This protocol specification uses conventional meanings for capitalized words such as MUST, SHOULD, etc., to indicate requirement levels for various protocol features. A node which is a member of the given multicast group and which is typically the first such group member in the connected portion of the network. This node is responsible for initializing and maintaining the multicast group destination sequence number.

Group leader table - The table where ad hoc nodes keep information concerning each multicast group and its corresponding group leader. There is one entry in the table for each multicast group for which the node has received a Group Hello. Multicast tree - The tree containing all nodes which are members of the multicast group and all nodes which are needed to connect the multicast group members. Multicast route table- The table where ad hoc nodes keep routing (including next hops) information for various multicast groups. Reverse route- A route set up to forward a reply (RREP) packet back to the source from the destination or from an intermediate node having a route to the destination.

5. Route Request (RREQ) Message Format

0123 01234567890123456789012345678901 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type |J|R|G| Reserved | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Other fields as specified for AODV....... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Route Request message remains as specified, except that the following flags have been added: J Join flag; set when source node wants to join a multicast group. R Repair flag; set when a node wants to initiate a repair to connect two previously disconnected portions of the multicast tree. When a node wishes to repair a multicast tree, it appends the Multicast Group Rebuild extension. When a node wishes to unicast the RREQ for a multicast group to the group leader, it includes the Multicast Group Leader extension.

6. Route Reply (RREP) Message Format

0123 01234567890123456789012345678901 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | R |Reserved| Prefix Sz | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Other fields as specified for AODV....... 7

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Route Reply message remains as specified, except that the following flag has been added: R Repair flag; set when a node is responding to a repair request to connect two previously disconnected portions of the multicast tree. When the RREP is sent for a multicast destination, the Multicast Group Information extension is appended.

7. Multicast Activation (MACT) Message Format

0123 01234567890123456789012345678901 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type |J|P|G|U|R| |Reserved| | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Multicast Group IP address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source IP address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Sequence Number| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Multicast Activation message is illustrated above, and contains the following fields: Type4 J Join flag; set when a node is joining the multicast group, as opposed to finding a route to the group for the transmission of data messages. P Prune flag; set when a node wishes to prune itself from the tree, unset when the node is activating a tree link. G Group Leader flag; set by a multicast tree member that fails to repair a multicast tree link breakage, and indicates to the group member receiving the message that it should become the new multicast group leader. U Update flag; set when a multicast tree member has repaired a broken tree link and is now a new distance from the group leader. R Reboot flag; set when a node has just rebooted. Reserved Sent as 0; ignored on reception.

Hop Count The distance of the sending node from the multicast group leader. Used only when the 'U' flag is set; otherwise sent as 0. Multicast Group IP Address: - The IP address of the Multicast Group for which a route is supplied. Source IP Address: - The IP address of the sending node. Source Sequence Number: - The current sequence number for route information generated by the source of the route request. To prune itself from the tree (i.e., inactivate its last link to the multicast tree), a multicast tree member sends a MACT with the 'P' flag = 1 to its next hop on the multicast tree. A multicast tree member that has more than one next hop to the multicast tree SHOULD NOT prune itself from the multicast tree.

8. Group Hello (GRPH) Message Format

0123 01234567890123456789012345678901 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type|U|O| Reserved| Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Group Leader IP address| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Multicast Group IP address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Group Hello message is illustrated above, and contains the following fields: Type5 U Update flag; set when there has been a change in group leader information. O Off_Mtree flag; set by a node receiving the group hello that is not on the multicast tree. Reserved Sent as 0; ignored on reception. Hop Count The number of hops the packet has traveled. Used by multicast tree nodes to update their distance from the group leader when the M flag is not set. Group Leader IP Address -The IP address of the group leader. Multicast Group IP Address -The IP address of the Multicast Group for which the sequence number is supplied. 9

Multicast Group Sequence Number- The current sequence number of the multicast group.

9. Security Considerations
Currently, MAODV does not specify any special security measures. Route protocols, however, are prime targets for impersonation attacks, and must be protected by use of authentication techniques involving generation of unforgettable and cryptographically strong message digests or digital signatures. It is expected that, in environments where security is an issue, that IPSec authentication headers will be deployed along with the necessary key management to distribute keys to the members of the ad hoc network using MAODV. Key Management Service We employ cryptographic schemes, such as digital signatures, to protect both routing information and data traffic. Use of such schemes usually requires a key management service. We adopt a public key infrastructure because of its superiority in distributing keys and in achieving integrity and non-repudiation. Efficient secret key schemes are used to secure further communication after nodes authenticate each other and establish a shared secret session key. In a public key infrastructure, each node has a public/private key pair. Public keys can be distributed to other nodes, while private keys should be kept confidential to individual nodes. There is a trusted entity called Certification Authority (CA) for key management. The CA has a public/private key pair, with its public key known to every node, and signs certificates binding public keys to nodes. The trusted CA has to stay on-line to reflect the current bindings, because the bindings could change over time: a public key should be revoked if the owner node is no longer trusted or is out of the network; a node may refresh its key pair periodically to reduce the chance of a successful brute-force attack on its private key. It is problematic to establish a key management service using a single CA in ad hoc networks. The CA, responsible for the security of the entire network, is a vulnerable point of the network: if the CA is unavailable, nodes cannot get the current public keys of other nodes or to establish secure communication with others. If the CA is compromised and leaks its private key to an adversary, the adversary can then sign any erroneous certificate using this private key to impersonate any node or to revoke any certificate. A standard approach to improve availability of a service is replication. But a naive replication of the CA makes the service more vulnerable: compromise of any single replica, which possesses the service private key, could lead to collapse of the entire system. To solve this problem, we distribute the trust to a set of nodes by letting these nodes share the key management responsibility. 10

9.1 System model Our key management service is applicable to an asynchronous ad hoc network; that is, a network with no bound on message-delivery and message-processing times. We also assume that the underlying network layer. The configuration of a key management service: the key management service consists of n servers. The service, as a whole, has a public/private key pair K/k. The public key K is known to all nodes in the network, whereas the private key k is divided into n shares s1, s2, sn, one share for each server. Each server i also have a public/private key pair K/k and knows the public keys of all nodes. Provides reliable link. The service, as a whole, has a public/private key pair. All nodes in the system know the public key of the service and trust any certificates signed using the corresponding private key. Nodes, as clients, can submit query requests to get other clients public keys or submit update requests to change their own public keys. Internally, our key management service, with an (n, t+1) configuration (n _ 3t+1), consists of n special nodes, which we call servers, present within an ad hoc network. Each server also has its own key pair and stores the public keys of all the nodes in the network. In particular, each server knows the public keys of other servers. Thus, servers can establish secure links among them. We assume that the adversary can compromise up to t servers in any period of time with certain duration. If a server is compromised, then the adversary has access to all the secret information stored on the server. A compromised server might be unavailable or exhibit Byzantine behavior (i.e., it can deviate arbitrarily from its protocols). We also assume that the adversary lacks the computational power to break the cryptographic schemes we employ. The service is correct if the following two conditions hold: (Robustness) The service is always able to process query and update requests from clients. Every query always returns the last updated public key associated with the requested client, assuming no concurrent updates on this entry. (Confidentiality) The private key of the service is never disclosed to an adversary. Thus, an adversary is never able to issue certificates, signed by the service private key, for erroneous bindings.

Cryptography

Distribution of trust in our key management service is accomplished using Blowfish cryptography [4, 3]. An (n, t + 1) threshold cryptography scheme allows n parties to share the ability to perform a cryptographic operation (e.g., creating a digital signature), so that any t +

11

1 parties can perform this operation jointly, whereas it is infeasible for at most t parties to do so, even by collusion. In our case, the n servers of the key management service share the ability to sign certificates. For the service to tolerate t compromised servers, we employ an (n, t+1) threshold cryptography scheme and divide the private key k of the service into n shares (s1, s2, . . . , sn), assigning one share to each server. We call (s1, s2, . . . , sn) an (n, t + 1) sharing of k. For the service to sign a certificate, each server generates a partial signature for the certificate using its private key share and submits the partial signature to a combiner. (i)With t + 1 correct partial signatures, Our key management service actually works under a much weaker link assumption, which is more appropriate for ad hoc networks. (ii) The duration depends on how often and how fast share refreshing is done. (iii) Any server can be a combiner. No extra information about k is disclosed to a combiner. To make sure that a compromised combiner cannot prevent a signature from being computed, we can use t + 1 servers as combiners to ensure that at least one combiner is correct and is able to compute the signature. Let K/k be the public/private key pair of the service. Using a (3, 2) Blowfish cryptography scheme, each server i gets a share si of the private key k. For a message m, server i can generate a partial signature PS (m, si) using its share si. Correct servers 1 and 3 both generate partial signatures and forward the signatures to a combiner c. Even though server 2 fails to submit a partial signature, c is able to generate the signature k of m signed by service private key k. The combiner is able to compute the signature for the certificate. However, compromised servers (there are at most t of them) cannot generate correctly signed certificates by themselves, because they can generate at most t partial signatures. When applying threshold cryptography, we must defend against compromised servers. For example, a compromised server could generate an incorrect partial signature. Use of this partial signature would yield an invalid signature. Fortunately, a combiner can verify the validity of a computed signature using the service public key. In case verification fails, the combiner tries another set of t + 1 partial signatures. This process continues until the combiner constructs the correct signature from t + 1 correct partial signatures. More efficient robust combining schemes are proposed [13, 12]. These schemes exploit the inherent redundancies in the partial signatures (note that any t+1 correct partial signatures contain all the information of the final signature) and use error correction codes to mask incorrect partial signatures.

12

References:
1) Intrusion Detection in Wireless Ad-hoc Networks, Yongguang Zhang, Wenke Lee. 2) Key Agreement in Ad-hoc Networks, N.Asokan, Philip Ginzboorg. 3) Securing Ad-hoc Networks, L. Zhou, Z.J.Haas. 4) A Secure Routing Protocol for Ad Hoc Networks, Bridget Dahill, Brian Neil, Elizabeth Royer, Clay Shields. 5) Routing Security in Ad Hoc Networks, Janne Lundberg, Helsinki University of Technology. 6) Key Agreement in Dynamic Peer Groups, Michael Steiner, Gene Tsudik, Michael Waidner, IEE Computer Society. 7) Mobile Ad Hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Consideration, S. Corson, J. Macker. 8) A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,E. M. Royer and C.K. Toh . 9) The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. J. Broch and D.B. Johnson. 10) Ad Hoc On-Demand Distance Vector Routing Protocol. C. E. Perkins and E. M. Royer.

13