INTRODUCTIONProblem definition and modelNetwork ModelSecurity ModelSecurity AssumptionsConsidered AttacksClasses of AdversariesMalignancy of the attacksCollusion power of adversaryAdaptivity/Intelligence of the adversaryProblem DefinitionSecure routing protocolInitial setupTransforming the topological graph of the network into an acStarting probability distributionSource route generationGeneration of a discrete random variablePath generation algorithmSecuring Routing OperationForwarding phaseForwarding at sourceForwarding on an intermediate nodeReception at destinationAcknowledgment phaseAcknowledgment at destinationAcknowledgment on an intermediate nodeAcknowledgment at sourceLink weight managementComputation of the Link Weight UpdatesUpdate of the Probability DistributionPerformance Analysis and Implementation AssessmentConclusions and Future work1Study of a Secure Probabilistic Routing Algorithm for Ad Hoc Networks Stefan Velica * Abstract—The object of this work is to provide an extended analysis of the secure routing algorithm proposed in “Baruch Awerbuch et al. – Provably Secure Competitive Routing against Proactive Byzantine Adversaries via Reinforcement Learning” - Technical Report, Computer Science Department – Johns Hopkins University, May 3003. The study is intended to constitute itself in a technical specification for a subsequent software implementation in ns-2 network simulator. The authors propose a new approach for the challenging problem of secure routing in ad hoc networks. Inspired by other uses of “Swarm intelligence” and “Distributed Reinforcement Learning” paradigms in developing routing algorithms for fixed networks the authors develop a scheme intended to operate in dynamic setting and even more, under extremely strong adversarial environment. A Byzantine adversary is defined as an authenticated intermediate node acting alone or in collusion with other nodes in order to generate disruption or degradation of the routing service. The basic idea of the routing protocol is to combine a probabilistic source routing scheme with a feedback mechanism implemented by probing the behavior of intermediate nodes and links using authenticated acknowledgment of forwarded data packets. Probability distributions per outgoing edges, used by source node when computing the source route, are adjusted periodically, penalizing the observed failure of intermediate links to forward the packets. Therefore well performing links are selected with higher probabilities to route source initiated traffic. Each node maintains its own view of the network as a graph with routes toward all the other nodes. A source routes is extracted for each data packet from the originator’s graph and the packet is sent along that route. Authentication of the intermediate nodes is performed by an “onion encryption” scheme. Key material may be provided by classical methods using a PKI and shared keys established on-demand or some other methods. Index Terms—MANET, Byzantine adversary, onion encryption, randomized source routing. I. INTRODUCTION mobile ad hoc wireless network (MANET) is a collection of mobile computers or devices that communicate with each other by wireless links in a cooperative manner without using any infrastructure like base stations or access points. Any node may act as a router to forward messages between other nodes that are not within direct wireless communication range. The author is Master’s Student in Electrical and Computer Engineering Department, George Mason University, Fairfax, Virginia. This work is a Project Report for class ECE646-Cryptography and Computer Network Security, Fall 2003. Dynamically changing topology and variability of the wireless link quality plus the shared access to the limited bandwidth wireless channel raises additional constraints for designing efficient routing protocols compared with the static network environment. The security issues are even more acute because of the cooperative nature assumed for communication and because of the ease of access to the communication medium for the adversaries. Classical routing protocols are vulnerable to simple forms of attack like advertisement of false routing information, modification of various fields in control packets with effects like redirection of traffic routes or routing packets in a loop. Authentication of control packets is the solution for annihilating these tentative actions of disturbing the routing performance. Another complementary line of defense is monitoring the correct behavior of the routing agents by deployment of a distributed intrusion detection system of trusted servers. But there are more sophisticated attacks not addressed by these approaches. A first example of more sophisticated attack is a form of denial of service mounted by a compromised node that behaves well from the standpoint of the routing protocol and becomes part of a preferred route. When the data packets reach the compromised node it drops them all or partially, affecting the forwarding stage of the routing process. This kind of opponent node is called “black hole” or “gray hole”. Even secure extensions of typical routing protocols, like Ariadne for DSR or SEAD for DSDV are vulnerable to this kind of attack (Ariadne and SEAD are described in [5] and [6]). A method to alleviate this situation for source routing case is the introduction of a random mechanism at source node to choose among more paths toward the same destination that makes the route with the intrusive node less probable to be selected. A refinement of this idea is, in fact, used by the protocol analyzed in the current project. But even more sophisticated forms of attack can be imagined if we consider a smart adversary which may adapt his disrupting behavior by monitoring the visible traffic for him. Such a node, which acts as an authenticated one, but can any time generate disruption or degradation of the routing service is called Byzantine adversary. As a superior form of attack we can mention colluding Byzantine adversaries or a completely arbitrary strong adversarial environment. We can even formulate a routing problem in the following A2extreme situation. If there is connectivity between two nodes in our network and we need data to be exchanged by them then we would like to develop a scheme that in an effective manner, with some controllable costs, eventually larger delay, is able to identify that good path
View Full Document
Unlocking...