SECURING ROUTING PROTOCOLS IN MOBILE AD HOC NETWORKS by Mohamed Ahmed Abdelshafy Abdallah Submitted for the degree of Doctor of Philosophy Department of Computer Science School of Mathematical and Computer Sciences Heriot-Watt University May 2016 The copyright in this thesis is owned by the author. Any quotation from the report or use of any of the information contained in it must acknowledge this report as the source of the quotation or information. Abstract A Mobile Ad Hoc Network (MANET) is more prone to security threats than other wired and wireless networks because of the distributed nature of the network. Conventional MANET routing protocols assume that all nodes cooperate without maliciously disrupting the operation of the protocol and do not provide defence against attackers. Blackhole and flooding attacks have a dramatic negative impact while grayhole and selfish attacks have a little negative impact on the performance of MANET routing protocols. Malicious nodes or misbehaviour actions detection in the network is an impor- tant task to maintain the proper routing protocol operation. Current solutions cannot guarantee the true classification of nodes because the cooperative nature of the MANETs which leads to false exclusions of innocent nodes and/or good classification of malicious nodes. The thesis introduces a new concept of Self- Protocol Trustiness (SPT) to discover malicious nodes with a very high trustiness ratio of a node classification. Designing and implementing new mechanisms that can resist flooding and blackhole attacks which have high negative impacts on the performance of these reactive protocols is the main objective of the thesis. The design of these mechanisms is based on SPT concept to ensure the high trustiness ratio of node classification. In addition, they neither incorporate the use of cryptographic algorithms nor depend on routing packet formats which make these solutions robust and reliable, and simplify their implementations in different MANET reactive protocols. Anti-Flooding (AF) mechanism is designed to resist flooding attacks which relies on locally applied timers and thresholds to classify nodes as malicious. Although AF mechanism succeeded in discovering malicious nodes within a small time, it has a number of thresholds that enable attacker to subvert the algorithm and cannot guarantee that the excluded nodes are genuine malicious nodes which was the motivation to develop this algorithm. On the other hand, Flooding Attack Resisting Mechanism (FARM) is designed to close the security gaps and overcome the drawbacks of AF mechanism. It succeeded in detecting and excluding more than 80% of flooding nodes within the simulation time with a very high trustiness ratio. Anti-Blackhole (AB) mechanism is designed to resist blackhole attacks and relies on a single threshold. The algorithm guarantees 100% exclusion of blackhole nodes and does not exclude any innocent node that may forward a reply packet. Although AB mechanism succeeded in discovering malicious nodes within a small time, the only suggested threshold enables an attacker to subvert the algorithm which was the motivation to develop it. On the other hand, Blackhole Resisting Mechanism (BRM) has the main advantages of AB mechanism while it is designed to close the security gaps and overcome the drawbacks of AB mechanism. It succeeded in detecting and excluding the vast majority of blackhole nodes within the simulation time. To my Mother and Father Acknowledgements All thanks and praises to the Almighty Allah, the most Gracious and the most Merciful for his favour, grace, guidance and giving me the strength to achieve my PhD. I would like to express my sincere thanks and greatest gratitude to my supervisor Dr. Peter King for his time, suggestions and continuous support during my research. You always help me to achieve my hopes and aspirations. I cannot find the words that you deserve. Many thanks Peter. I would like to thank all staff members and administrative staff of Mathematical and Computer Science Department at Heriot-Watt University for their continuous help. My sincere thanks to Prof. Nicholas Taylor for his continuous support. I am very grateful to the people I have been in contact with in Egypt, Saudi Arabia and UK. My gratitude to Heriot-Watt Muslim Society and Arab Society in Edin- burgh for the nice time I have spent with them. Special Thanks to my office mate Turkey Alsalakini for his valuable support and help. My gratitude for my friends Ali Etorban, Idris Skloul and Mustafa Aswad for their valuable help. Thanks to my old and current office mates specially Khari Armih, Majed Al Saeed, Nawaf Mirza and Atif Al Ghamdi for their help and feedback. Finally, I would like express my deepest thanks and greatest gratitude to my mother and father for their eternal favours and I would like to say to them without your prayers I did not achieve a success in my life and I would not be in this position. I would like to thank as well my wife, sons and daughter for their patience dur- ing my research. I would like to express my deepest gratitude to my brother and sisters. Thanks my family for your encouragement and support to finish my work successfully. ii Contents 1 Introduction 1 1.1 Thesis Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Research Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Organisation of the thesis . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Literature Review 7 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Mobile Ad hoc Networks (MANETs) . . . . . . . . . . . . . . . . . . 8 2.3 MANET Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3.1 Distributed Operation . . . . . . . . . . . . . . . . . . . . . . 10 2.3.2 Dynamic Topologies . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.3 Node-Constrained Resources . . . . . . . . . . . . . . . . . . . 10 2.3.4 Limited Physical Security . . . . . . . . . . . . . . . . . . . . 11 2.4 MANET Routing Protocols . . . . . . . . . . . . . . . . . . . . . . . 11 2.4.1 Proactive Routing Protocols . . . . . . . . . . . . . . . . . . . 11 2.4.1.1 Destination Sequenced Distance-Vector (DSDV) . . . 12 2.4.1.2 Wireless Routing Protocol (WRP) . . . . . . . . . . 12 2.4.1.3 Fisheye State Routing (FSR) . . . . . . . . . . . . . 13 2.4.1.4 Optimized Link State Routing (OLSR) . . . . . . . . 13 2.4.2 Reactive Routing Protocols . . . . . . . . . . . . . . . . . . . 13 2.4.2.1 Dynamic Source Routing (DSR) . . . . . . . . . . . 14 2.4.2.2 Ad hoc On Demand Distance Vector (AODV) . . . . 14 2.4.2.3 Associativity-Based Routing (ABR) . . . . . . . . . 15 iv 2.4.3 Hybrid Routing Protocols . . . . . . . . . . . . . . . . . . . . 15 2.4.3.1 Zone Routing Protocol (ZRP) . . . . . . . . . . . . . 15 2.4.3.2 Core Extraction Distributed Ad hoc Routing Proto- col (CEDAR) . . . . . . . . . . . . . . . . . . . . . . 16 2.4.4 Multipath Routing Protocols . . . . . . . . . . . . . . . . . . . 16 2.4.4.1 Ad hoc On-demand Multipath Distance Vector Routing (AOMDV) . . . . . . . . . . . . . . . . . . . 17 2.4.4.2 Scalable Multipath On-demand Routing (SMORT) . 17 2.5 MANET Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5.1 MANET Routing Attacks . . . . . . . . . . . . . . . . . . . . 20 2.5.2 Passive Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5.2.1 Traffic Analysis . . . . . . . . . . . . . . . . . . . . . 20 2.5.2.2 Traffic Monitoring . . . . . . . . . . . . . . . . . . . 21 2.5.2.3 Eavesdropping . . . . . . . . . . . . . . . . . . . . . 21 2.5.3 Active Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.5.3.1 Modification-based Attacks . . . . . . . . . . . . . . 21 2.5.3.1.1 Redirection Attack . . . . . . . . . . . . . . 21 2.5.3.1.2 Misrouting Attack . . . . . . . . . . . . . . 22 2.5.3.1.3 Detour Attack . . . . . . . . . . . . . . . . 22 2.5.3.1.4 Blackmail Attack . . . . . . . . . . . . . . . 22 2.5.3.1.5 Denial of Service (DoS) Attack . . . . . . . 22 2.5.3.2 Impersonation-based Attacks . . . . . . . . . . . . . 23 2.5.3.2.1 Man-in-the-Middle Attack . . . . . . . . . . 23 2.5.3.2.2 Sybil Attack . . . . . . . . . . . . . . . . . . 23 2.5.3.3 Fabrication-based Attacks . . . . . . . . . . . . . . . 23 2.5.3.3.1 Routing Table Poisoning Attack . . . . . . . 24 2.5.3.3.2 Flooding Attack . . . . . . . . . . . . . . . 24 2.5.3.3.3 Rushing Attack . . . . . . . . . . . . . . . . 24 2.5.3.3.4 Blackhole Attack . . . . . . . . . . . . . . . 24 2.5.3.3.5 Grayhole Attack . . . . . . . . . . . . . . . 25 v 2.5.3.3.6 Wormhole Attack . . . . . . . . . . . . . . . 25 2.5.3.3.7 Selfish Attack . . . . . . . . . . . . . . . . . 25 2.6 Securing MANET Routing Protocols . . . . . . . . . . . . . . . . . . 25 2.6.1 Cryptographic Algorithms . . . . . . . . . . . . . . . . . . . . 26 2.6.1.1 Symmetric Key Cryptography . . . . . . . . . . . . . 26 2.6.1.2 Asymmetric Key Cryptography . . . . . . . . . . . . 27 2.6.1.3 Cryptographic hash functions . . . . . . . . . . . . . 28 2.6.1.4 Digital signatures . . . . . . . . . . . . . . . . . . . . 28 2.6.2 Secured Routing Mechanisms . . . . . . . . . . . . . . . . . . 29 2.6.2.1 Prevention Mechanisms . . . . . . . . . . . . . . . . 29 2.6.2.1.1 Authenticated Routing for Ad-hoc Net- works (ARAN) . . . . . . . . . . . . . . . . 30 2.6.2.1.2 Security-Aware ad-hoc Routing (SAR) . . . 31 2.6.2.1.3 Secure Routing Protocol (SRP) . . . . . . . 31 2.6.2.1.4 Secure Efficient Ad hoc Networks (SEAD) . 32 2.6.2.1.5 ARIADNE . . . . . . . . . . . . . . . . . . 32 2.6.2.1.6 Secure Ad hoc On-demand Distance Vector Routing Protocol (SAODV) . . . . . . . . . 33 2.6.2.1.7 Secure Link State Routing Protocol (SLSP) 34 2.6.2.2 Detection and Reaction Mechanisms . . . . . . . . . 34 2.6.2.2.1 Byzantine Algorithm . . . . . . . . . . . . . 34 2.6.2.2.2 CORE . . . . . . . . . . . . . . . . . . . . . 35 2.6.2.2.3 CONFIDANT . . . . . . . . . . . . . . . . . 35 2.6.2.2.4 Watchdog and Pathrater . . . . . . . . . . . 36 2.6.2.3 Secured Routing Mechanisms Drawbacks . . . . . . . 36 2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3 Methodology 38 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2 Routing Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2.1 Selection Criteria . . . . . . . . . . . . . . . . . . . . . . . . . 39 vi 3.2.2 Dynamic Source Routing (DSR) . . . . . . . . . . . . . . . . . 40 3.2.3 Ad hoc On Demand Distance Vector (AODV) . . . . . . . . . 41 3.2.4 Ad hoc On-demand Multipath Distance Vector Routing (AOMDV) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2.5 Secure Ad hoc On-demand Distance Vector Routing Protocol (SAODV) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.3 Routing Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.3.1 Selection Criteria . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.3.2 Flooding Attack . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3.3 Blackhole Attack . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3.4 Grayhole Attack . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.3.5 Selfish Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.4 System Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.4.1 Selection Criteria . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4.2 NS-2 Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4.3 Supporting Mobility in NS-2 . . . . . . . . . . . . . . . . . . . 50 3.4.4 Randomness in Scenarios Generation . . . . . . . . . . . . . . 51 3.4.5 Adding Security to NS-2 . . . . . . . . . . . . . . . . . . . . . 53 3.4.6 SAODV Implementation . . . . . . . . . . . . . . . . . . . . . 55 3.4.7 Simulation Approaches . . . . . . . . . . . . . . . . . . . . . . 56 3.4.8 Attacker Model . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.4.9 Simulation Limitations . . . . . . . . . . . . . . . . . . . . . . 59 3.4.10 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . 61 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4 Routing Protocols under Attacks 63 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2 Simulation Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.3 AODV under Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.3.1 AODV under Flooding Attack . . . . . . . . . . . . . . . . . . 65 4.3.2 AODV under Blackhole Attack . . . . . . . . . . . . . . . . . 66 vii