Surviving attacks on disruption-tolerant networks without authentication

ABSTRACT

Disruption-Tolerant Networks (DTNs) deliver data in network environments composed of intermittently connected nodes. Just as in traditional networks, malicious nodes within a DTN may attempt to delay or destroy data in transit to its destination. Such attacks include dropping data, flooding the network with extra messages, corrupting routing tables, and counterfeiting network acknowledgments. Many existing methods for securing routing protocols require authentication supported by mechanisms such as a public key infrastructure, which is difficult to deploy and operate in a DTN, where connectivity is sporadic. Furthermore, the complexity of such mechanisms may dissuade node participation so strongly that potential attacker impacts are dwarfed by the loss of contributing participants. In this paper, we use connectivity traces from our UMass DieselNet project and the Haggle project to quantify routing attack effectiveness on a DTN that lacks security. We introduce plausible attackers and attack modalities and provide complexity results for the strongest of attackers. We show that the same routing with packet replication used to provide robustness in the face of unpredictable mobility allows the network to gracefully survive attacks. In the case of the most effective attack, acknowledgment counterfeiting, we show a straightforward defense that uses cryptographic hashes but not a central authority. We conclude that disruption-tolerant networks are extremely robust to attack; in our trace-driven evaluations, an attacker that has compromised 30% of all nodes reduces delivery rates from 70% to 55%, and to 20% with knowledge of future events. By comparison, contemporaneously connected networks are significantly more fragile.

REFERENCES

• 1: Aruna Balasubramanian , Brian Levine , Arun Venkataramani, DTN routing as a resource allocation problem, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 2: N. Banerjee, M. D. Corner, and B. N. Levine. An Energy-Efficient Architecture for DTN Throwboxes. In Proc. IEEE Infocom, May 2007.
• 3: Dan Boneh , Matthew Franklin, Identity-Based Encryption from the Weil Pairing, SIAM Journal on Computing, v.32 n.3, p.586-615, 2003 [doi>10.1137/S0097539701398521]
• 4: S. Buchegger and J. Le Boudec. The Effect of Rumor Spreading in Reputation Systems for Mobile Ad hoc Networks. In Proc. WiOpt, pages 131--140, 2003.
• 5: J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. In Proc. IEEE INFOCOM, April 2006.
• 6: B. Burns, O. Brock, and B. N. Levine. MV routing and capacity building in disruption tolerant networks. In Proc. IEEE INFOCOM, pages 398--408, March 2005.
• 7: Srdjan Čapkun , Jean-Pierre Hubaux , Levente Buttyan, Mobility Helps Peer-to-Peer Security, IEEE Transactions on Mobile Computing, v.5 n.1, p.43-51, January 2006 [doi>10.1109/TMC.2006.12]
• 8: Alice Cheng , Eric Friedman, Sybilproof reputation mechanisms, Proceedings of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080202]
• 9: James A. Davis , Andrew H. Fagg , Brian N. Levine, Wearable Computers as Packet Transport Mechanisms in Highly-Partitioned Ad-Hoc Networks, Proceedings of the 5th IEEE International Symposium on Wearable Computers, p.141, October 08-09, 2001
• 10: Roger Dingledine , Nick Mathewson , Paul Syverson, Tor: the second-generation onion router, Proceedings of the 13th conference on USENIX Security Symposium, p.21-21, August 09-13, 2004, San Diego, CA
• 11: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: M. Grossglauser and M. Vetterli. Locating Peers With Ease: Mobility Diffusion Of Last Encounters In Ad hoc Networks. In Proc. IEEE Infocom, April 2003.
• 14: P. Holme, B. J. Kim, C. N. Yoon, and S. K. Han. Attack Vulnerability of Complex Networks. APS Physics Review E, 65(5):056109.1--056109.14, May 2002.
• 15: Yih-Chun Hu , Adrian Perrig , David B. Johnson, Ariadne: a secure on-demand routing protocol for ad hoc networks, Wireless Networks, v.11 n.1-2, p.21-38, January 2005 [doi>10.1007/s11276-004-4744-y]
• 16: Pan Hui , Augustin Chaintreau , James Scott , Richard Gass , Jon Crowcroft , Christophe Diot, Pocket switched networks and human mobility in conference environments, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.244-251, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080142]
• 17: Sushant Jain , Kevin Fall , Rabin Patra, Routing in a delay tolerant network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 18: P. Juang et al. Energy-Efficient Computing for Wildlife Tracking: design tradeoffs and early experiences with ZebraNet. SIGOPS Oper. Syst. Rev., 36(5):96--107, 2002.
• 19: Jiejun Kong , Xiaoyang Hong , Yunjung Yi , Joon-Sang Park , Jun Liu , Mario Gerla, A secure ad-hoc routing approach using localized self-healing communities, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062722]
• 20: David Kotz , Calvin Newport , Robert S. Gray , Jason Liu , Yougu Yuan , Chip Elliott, Experimental evaluation of wireless simulation assumptions, Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 04-06, 2004, Venice, Italy [doi>10.1145/1023663.1023679]
• 21: Qun Li , Daniela Rus, Sending messages to mobile users in disconnected ad-hoc wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.44-55, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345918]
• 22: A. Lindgren, A. Doria, and O. Scheln. Probabilistic Routing in Intermittently Connected Networks. In Proc. Workshop on Service Assurance with Partial and Intermittent Resources, August 2004.
• 23: A. Lindgren, A. Doria, and O. Scheln. Probabilistic Routing in Intermittently Connected Networks. In Proc. Workshop on Service Assurance with Partial and Intermittent Resources, August 2004.
• 24: P. Papadimitratos and Z. Haas. Secure Routing for Mobile Ad Hoc Networks. In Proc. SCS Communication Networks and Distributed Systems Modeling and Simulation Conference, 2002.
• 25: Alex (Sandy) Pentland , Richard Fletcher , Amir Hasson, DakNet: Rethinking Connectivity in Developing Nations, Computer, v.37 n.1, p.78-83, January 2004 [doi>10.1109/MC.2004.1260729]
• 26: C. Piro, C. Shields, and B. N. Levine. Detecting the Sybil Attack in Ad hoc Networks. In Proc. IEEE/ACM Intl. Conf. on Security and Privacy in Communication Networks (SecureComm), pages 1--11, Aug. 2006.
• 27: K. Sanzgiri, B. Dahill, D. LaFlamme, B. N. Levine, C. Shields, and E. Belding-Royer. Authenticated Routing for Ad hoc Networks. IEEE/ACM Journal of Selected Areas in Communications: Special issue on Wireless Ad hoc Networks (JSAC), 23(3):598--610, March 2005.
• 28: N. Sarafijanovic-Djukic and M. Grossglauser. Last Encounter Routing under Random Waypoint Mobility. In Proc. IFIP-TC6 NETWORKING, pages 974--988, 2004.
• 29: A. Seth and S. Keshav. Practical Security for Disconnected Nodes. In Proc. Workshop on Secure Network Protocols (NPSEC), Nov. 2005.
• 30: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.252-259, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080143]
• 31: Wizzy digital courier. http://www.wizzy.org.za.
• 32: Xiaolan Zhang , Jim Kurose , Brian Neil Levine , Don Towsley , Honggang Zhang, Study of a bus-based disruption-tolerant network: mobility modeling and impact on routing, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287876]
• 33: Wenrui Zhao , Mostafa H. Ammar, Message Ferrying: Proactive Routing in Highly-Partitioned Wireless Ad Hoc Networks, Proceedings of the The Ninth IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS'03), p.308, May 28-30, 2003
• 34: W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989483]
• 35: W. Zhao, Y. Chen, M. Ammar, M. D. Corner, B. N. Levine, and E. Zegura. Capacity Enhancement using Throwboxes in DTNs. In Proc. IEEE Intl Conf on Mobile Ad hoc and Sensor Systems (MASS), pages 31--40, Oct 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Performance, Security

Keywords:
DTN, deployment, mobility, routing, security