WIXLIB

alter, discard, forge, inject and replay control and datatraffic, generate floods of spurious messages, and, ingeneral, avoid complying with the employed protocols. Theimpact of such malicious behavior can be severe, especiallybecause the cooperation of all network nodes provides forthe functionality of the absent fixed infrastructure. Inparticular, as part of the normal operation of the network,nodes are transiently associated with a dynamicallychanging, over time, subset of their peers; that is, the nodeswithin the range of their transceiver, or the ones thatprovide routing information and implicitly agree to relaytheir data packets. Due to this transient association, it ismore difficult to identify malicious nodes and detect theirmisbehavior. As a result, a malicious node can obstruct thecommunications of potentially any node in the network,exactly because it is entitled, or, even, expected toparticipate in assisting the network operation.In addition, freely roaming nodes join and leave MANETsub-domains independently, possibly frequently, andwithout notice, making it difficult in most cases to have aclear picture of the ad hoc network membership. In otherwords, there may be no ground for an a priori classificationof a subset of nodes as trusted to support the networkfunctionality. Trust may only be developed over time, whiletrust relationships among nodes may also change, when, forexample, nodes in an ad hoc network dynamically becomeaffiliated with administrative domains. This is in contrast toother mobile networking paradigms, such as Mobile IP orcellular telephony, where nodes continue to belong to theiradministrative domain, in spite of mobility. Consequently,security solutions with static configuration would notsuffice, and the assumption that all nodes can bebootstrapped with the credentials of all, or substantialfraction of, other nodes would be unrealistic for a widerange of MANET instances.From a slightly different point of view, it becomesapparent that nodes cannot be easily classified as ‘internal’or ‘external,’ that is, nodes that belong to the network ornot, or nodes expected to participate and be dedicated tosupporting a certain network operation and those that arenot. In other words, the absence of an infrastructureimpedes the usual practice of establishing a line of defense,separating nodes into trusted and non-trusted. As a result,attacks cannot be classified as internal or external either,especially at the network layer. Of course, such a distinctioncould be made at the application layer, where access to aservice, or participation to its collaborative support, may beallowed only to authorized nodes. In the latter example, anattack from a compromised node within the group, that is, agroup node under the control of an adversary would beconsidered as an internal one.The absence of a central entity makes the detection ofattacks a very difficult problem, since highly dynamic largenetworks cannot be easily monitored. Benign failures, suchas transmission impairments, path breakages, and droppedpackets, are naturally a fairly common occurrence in mobilead hoc networks, and, consequently, malicious failures willbe more difficult to distinguish. This will be especially truefor adversaries that vary their attack pattern and misbehaveintermittently against a set of their peers that also changesover time. As a result, short-lived observations will notallow detection of the adversaries. Moreover, abnormalsituations may occur frequently, because nodes behave in aselfish manner and do not always assist the networkfunctionality. It is noteworthy that such behavior may not bemalicious, but only necessary when, for example, the nodeshuts its transceiver down in order to preserve its battery.Most of the currently considered MANET protocols werenot originally designed to deal with malicious behavior orother security threats. Thus they are easy to abuse.Compromised routes, i.e., routes that are not free ofmalicious nodes, may be repeatedly chosen with the“encouragement” provided by the malicious nodesthemselves. 1 The result being that the pair of thecommunicating end-nodes will experience DoS, and theymay have to rely on cycles of time-out and new routediscovery to find operational routes, with successive querybroadcasts imposing additional overhead. Or, even worse,the end nodes may be easily deceived for some period oftime that the data flow is undisrupted, while no actualcommunication takes place. For example, the adversarymay drop a route error message, “hiding” a route breakage,or it can corrupt both the data and their checksum, or forgenetwork and transport layer acknowledgments.Finally, mobile or nomadic hosts have limitedcomputational capabilities, due to constraints stemmingfrom the nature of the envisioned MANET applications.Expensive cryptographic operations, especially if they haveto be performed for each packet and over each link of thetraversed path, make such schemes implausible for the vastmajority of mobile devices. Cryptographic algorithms mayrequire computation delays ranging from one to severalseconds [5, 11]. These delays, imposed, for example, by thegeneration or verification of a single digital signature, affectthe data rate of secure communication. But, moreimportantly, mobile devices become ideal targets of DoSattacks due to their limited computational resources. Anadversary would generate bogus packets, forcing the deviceto consume substantial portion of its resources. Worse even,a malicious node with valid credentials would generatecontrol traffic, such as route queries, at a high rate not onlyto consume bandwidth, but also to impose cumbersomecryptographic operations on sizable portion of the networknodes.4. Trust managementThe use of cryptographic techniques is necessary for theprovision of any type of security services, and mobile adhoc networks are not an exception to this rule. Thedefinition and the mechanisms for security policies,credentials, and trust relationships, i.e., the components ofwhat is collectively identified as trust management, are aprerequisite for any security scheme. A large number ofsolutions have been presented in the literature for1For instance, by the malicious nodes claiming that theypossess an inexpensive (short) route to the destination3

distributed systems, but they cannot be readily transplantedinto the MANET context, since they rely on the existence ofnetwork hierarchy and on the existence of a central entity.In fact, MANET lacks exactly these two features.Envisioned applications for the ad hoc networkingenvironment may require a completely different notion ofestablishing a trust relationship, while the network operationmay impose additional obstacles to the effectiveimplementation of such solutions.For small-scale networks, of the size of a personal orhome network, trust can be established in a truly ad hocmanner, with relationships being static and sporadicallyreconfigured manually. In such an environment, the ownerof a number of devices or appliances can imprint them, thatis, distribute their credentials and a set of rules thatdetermine the allowed interaction with and between devices[24]. The proposed security policy follows a master-slavemodel, with the master device being responsible forreconfiguring slave devices, issuing commands or retrievingdata. The return to the initial state can be done only by themaster device, or by some trusted key escrow service.This model naturally lends itself to represent personalarea networking, in particular network instances such asBluetooth [4], in the sense that within a Piconet theinteractions between nodes can be determined by thesecurity policy. The model can be extended by allowingpartial control or access rights to be delegated, so that thesecure interaction of devices becomes more flexible [25].However, if the control over a device can be delegated, thenew master should be prevented from eradicating priorassociations and assuming full control of the node.A more flexible configuration, independent of initialbindings, can be useful when a group of people wish toform a collaborative computing environment [9]. In such ascenario, the problem of establishing a trust relationship canbe solved by a secure key agreement, so that any two ormore devices are able to communicate securely. The mutualtrust among users allows them to share or establish apassword using an offline secure channel, and then executea password-based authenticated key exchange over theinsecure wireless medium. Schemes that derive a sharedsymmetric key can use a multi-party version of thepassword authenticated Diffie-Hellman key-exchangealgorithm [3]. For instance, after an initial ordering of thenodes and a leader election, in each round, nodes choose apartner and do a two-party exchange, being able to proceedindependently in an asynchronous manner, under theassumption that the adversary cannot remove or modifymessages [1].The human judgment and intervention can greatlyfacilitate the establishment of spontaneous connectivityamong devices. Users can select a shared password ormanually configure the security bindings between devices,as seen above. Furthermore, they could assess subjectivelythe ‘security’ of their physical and networking environmentand then proceed accordingly. However, human assistancemay be impossible for the envisioned MANET environmentwith nodes acting as mobile routers, although the distinctionbetween an end device and a router may be only logical,with nodes assuming both roles. Frequently, the solerequirement for two transiently associated devices will be tomutually assist each other in the provision of basicnetworking services, such as route discovery and dataforwarding. This could be so since mobile nodes will notnecessarily pursue collectively a common goal. As a result,the users of the devices may have no means to establish atrust relationship in the absence of a prior context.However, there is no reason to believe that a moregeneral trust model would not be required in the MANETcontext. For instance, a node joining a domain may have topresent its credentials in order to access an availableservice, and at the same time authenticate the service itself.Similarly, two network nodes may wish to employ a securemode of multihop communication and verify each other’sidentity. Clearly, support for such types of secureinteraction, either at the network or at the application layer,will be needed.A public key cryptosystem can be a solution, with eachnode bound to a pair of keys, one publicly known and oneprivate. However, the deployment of a public keyinfrastructure (PKI) requires the existence of a certificationauthority (CA), a trusted third party responsible forcertifying the binding between nodes and public keys. Theuse of a single point of service for key management can be aproblem in the MANET context, especially because such aservice should always remain available. It is possible thatnetwork partitions or congested links close to the CA server,although they may be transient, cause significant delays ingetting a response. Moreover, in the presence ofadversaries, access to the CA may be obstructed, or theresources of the CA node may be exhausted by a DoSattack. One approach is not to rely on a CA and thus abolishall the advantages of such a facility. Another approach is toinstantiate the CA in a way that answers the particularchallenges of the MANET environment.The former approach can be based on the bootstrappingof all network nodes with the credentials of every othernode. However, such an assumption will dramaticallynarrow the scope of ad hoc networking, since it can beapplied only to short-lived mission-oriented and thus closednetworks. An additional limitation may stem from the needto ensure a sufficient level of security, which implies thatcertificates should be refreshed from time to time, requiring,again, the presence of a CA.Alternatively, it has been suggested that users certify thepublic keys of other users. One such scheme proposes thatany group of K nodes may provide a certificate to arequesting node. Such a node broadcasts the request to itsone-hop neighborhood, each neighbor provides a partialcertificate, and if sufficient, that is, K such certificates arecollected, the node acquires the complete certificate [14].Another scheme proposes that each node selects a numberof certificates to store, so that, when a node wants the publickey of one of its peers, the two certificate repositories aremerged, and if a chain of certificates is discovered, thepublic key is obtained [13].An approach that can be applicable in a general settingand can effectively instantiate a key management facility4

has been proposed in [29]. The solution of a public keyinfrastructure is adapted to meet the requirements of theMANET environment, by providing increased availabilityand fault-tolerance. The certification authority (CA) isequipped with a private/public key pair. All network nodesknow the public key of the CA, and trust all certificatessigned by the CA’s private key. Nodes that wish to establishsecure communication with a destination, query the CA andretrieve the required certificate, thus being able toauthenticate the other end, and establish a secret shared keyfor improved efficiency. Similarly, nodes can request anupdate from the CA, that is, change their own public keyand acquire a certificate for the new key.‘contributed’ by rogue servers, will be detected. Moreover,the service provides the assurance that the adversary willnot be able to compromise enough servers over a longperiod of time. This is done with the help of sharerefreshing, a technique that allows the servers to calculatenew shares from the old ones without disclosing the privatekey of the service. The new shares are independent from theold ones and cannot be combined in an attempt to recoverthe private key of the CA. As a result, to compromise thesystem, all t 1 shares have to be compromised within onerefresh period, which can be chosen appropriately short inorder to decrease vulnerability. The vulnerability can bedecreased even further, when a quorum of correct serversdetects compromised or unavailable servers and reconfigures the service, that is, generates and distributes anew set of n’ shares, t’ 1 of which need be combined nowto calculate a valid signature. It is noteworthy that thepublic/private key pair of the service is not affected by sharerefreshing and re-configuration operations, which aretransparent to all clients.Figure 1. The configuration of a key management service:the key management service consists of n servers. Theservice, as a whole, has a public/private key pair K/k. Thepublic key K is known to all nodes in the network, whereasthe private key k is divided into n shares s1, s2, . . . , sn, oneshare for each server. Each server i also has a public/privatekey pair Ki/ki and knows the public keys of all nodes.The CA is instantiated by a set of nodes (servers), asshown in Figure 1, for enhanced availability. However, thisis not done through naïve replication, which would increasethe vulnerability of the system, since the compromise of asingle replica would be sufficient for the adversary tocontrol the CA. Instead, the trust is distributed among a setof nodes, which share the key management responsibility.In particular, each of the n servers has its own pair ofpublic/private key, and they collectively share the ability tosign certificates. This is achieved with the use of thresholdcryptography, which allows any t 1 out of n parties toperform a cryptographic operation, while t parties cannot doso. To accomplish this, the private key of the service, as awhole, is divided into n shares, with each of the serversholding one share. When a signature has to be computed,each server uses its share and generates a partial signature.All partial signatures are submitted to a combiner, a serverwith the special role to generate the certificate signature outof the collected partial signatures, as shown in the exampleof Figure 2. This is possible only with at least t 1 validpartial signatures.The application of threshold cryptography providesprotection from compromised servers, since more than tservers have to be compromised before it assumes controlof the service. If less than t 1 servers are under the controlof an adversary, the operation of the CA can continueefficiently, since purposefully invalid partial signatures,Figure 2. Threshold signature: given a service consisting of3 servers. Let K/k be the public/private key pair of theservice. Using a (3, 2) threshold cryptography scheme, eachserver 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 itsshare si. Correct servers 1 and 3 both generate partialsignatures and forward the signatures to a combiner c. Eventhough server 2 fails to submit a partial signature, c is ableto generate the signature m k of m signed by serviceprivate key k.The threshold cryptography key management schemecan be adapted further by selecting different configurationsof the key management service for different networkinstances. For example, the numbers of servers can beselected according to the size or the rate of changes of thenetwork; for a large number of nodes within a largecoverage area, the number of servers should also be large,so that the responsiveness of the service can be high. Nodeswill tend to interact with the closest server, which can beonly a few hops away, or with the server that responds withthe least delay. Another possibility is to alternate among the5

servers within easy reach of the client, something that canhappen naturally in a dynamically changing topology. Thisway, the load from queries and updates will be balancedamong different servers, and the chances of congestion nearone of the servers will be reduced. At the same time, thestorage requirements can be traded off for inter-servercommunication, by storing at each server a fraction of theentire database.Additionally, the efficient operation of the CA can beenhanced, when it is combined with secure route discoveryand data forwarding protocols, which, in fact, can emulatethe assumption of reliable links between servers in [29]even in the presence of adversaries. In particular, two of theprotocols that will be discussed below, SRP and SMT, lendthemselves naturally to this model. Any two servers2 candiscover and maintain routes to each other, and forwardservice-related traffic, regardless of whether intermediatenodes are trusted or not.5. Secure RoutingThe secure operation of the MANET routing protocol isof central importance, because of the absence of a fixedinfrastructure. Instead, nodes are transiently associated andcooperate with virtually any node that could potentiallydisrupt the route discovery and data forwarding operations.In particular, the disrupti

mobile ad hoc network. 3. Threats and Challenges Mobile ad hoc networks are vulnerable to a wide range of active and passive attacks that can be launched relatively easily, since all communications take place over the wireless medium. In particular, wireless communication facilitates eavesdropping, especially because continuous