Mitigating DoS attacks against broadcast authentication in wireless sensor networks

ABSTRACT

Broadcast authentication is a critical security service in wireless sensor networks. There are two general approaches for broadcast authentication in wireless sensor networks: digital signatures and μTESLA-based techniques. However, both signature-based and μTESLA-based broadcast authentication are vulnerable to Denial of Services (DoS) attacks: An attacker can inject bogus broadcast packets to force sensor nodes to perform expensive signature verifications (in case of signature-based broadcast authentication) or packet forwarding (in case of μTESLA-based broadcast authentication), thus exhausting their limited battery power. This paper presents an efficient mechanism called message-specific puzzle to mitigate such DoS attacks. In addition to signature-based or μTESLA-based broadcast authentication, this approach adds a weak authenticator in each broadcast packet, which can be efficiently verified by a regular sensor node, but takes a computationally powerful attacker a substantial amount of time to forge. Upon receiving a broadcast packet, each sensor node first verifies the weak authenticator, and performs the expensive signature verification (in signature-based broadcast authentication) or packet forwarding (in μTESLA-based broadcast authentication) only when the weak authenticator is valid. A weak authenticator cannot be precomputed without a non-reusable (or short-lived) key disclosed only in a valid packet. Even if an attacker has intensive computational resources to forge one or more weak authenticators, it is difficult to reuse these forged weak authenticators. Thus, this weak authentication mechanism substantially increases the difficulty of launching successful DoS attacks against signature-based or μTESLA-based broadcast authentication. A limitation of this approach is that it requires a powerful sender and introduces sender-side delay. This article also reports an implementation of the proposed techniques on TinyOS, as well as initial experimental evaluation in a network of MICAz motes.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: Tuomas Aura , Pekka Nikander , Jussipekka Leiwo, DOS-Resistant Authentication with Client Puzzles, Revised Papers from the 8th International Workshop on Security Protocols, p.170-177, April 03-05, 2000
• 3: Back, A. 2002. Hashcash---a denial of service counter-measure. http://www.cypherspace.org/hashcash/hashcash.pdf.
• 4: Mario Cagalj , Srdjan Capkun , Jean-Pierre Hubaux, Wormhole-Based Antijamming Techniques in Sensor Networks, IEEE Transactions on Mobile Computing, v.6 n.1, p.100-114, January 2007 [doi>10.1109/TMC.2007.18]
• 5: Certicom Research. 2000. Standards for efficient cryptography---SEC 2: Recommended elliptic curve domain parameters. http://www.secg.org/collateral/sec2_final.pdf.
• 6: ChipCon. 2.4 GHz IEEE 802.15.4/ZigBee-ready RF Transceiver. http://www.chipcon.com/files/CC2420_Data_Sheet_1_4.pdf.
• 7: CrossBow. Micaz: Wireless measurement system. http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/MICAz_Datasheet.pdf.
• 8: Crossbow Technology Inc. Wireless sensor networks. http://www.xbow.com/Products/Wireless_Sensor_Networks.htm.
• 9: Dai, W. 2004. Crypto++ 5.2.1 benchmarks. http://www.eskimo.com/~weidai/benchmarks.html.
• 10: Drew Dean , Adam Stubblefield, Using client puzzles to protect TLS, Proceedings of the 10th conference on USENIX Security Symposium, p.1-1, August 13-17, 2001, Washington, D.C.
• 11: Jing Deng , Richard Han , Shivakant Mishra, Secure code distribution in dynamically programmable wireless sensor networks, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127822]
• 12: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 13: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 14: Rosario Gennaro , Pankaj Rohatgi, How to Sign Digital Streams, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.180-197, August 17-21, 1997
• 15: Gunter, C., Khanna, S., Tan, K., and Venkatesh, S. 2004. DoS protection for reliably authenticated broadcast. In Proceedings of the 11th Network and Distributed Systems Security Symposium (NDSS'04). 17--36.
• 16: Gura, N., Patel, A., and Wander, A. 2004. Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In Proceedings of the 2004 Workshop on Cryptographic Hardware and Embedded Systems (CHES'04). 119--132.
• 17: Haller, N. M. 1994. The S/KEY one-time password system. In Proceedings of the ISOC Symposium on Network and Distributed System Security. 151--157.
• 18: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 19: Hu, Y., Jakobsson, M., and Perrig, A. 2005. Efficient constructions for one-way hash chains. In Proceedings of the 3rd International Conference on Applied Cryptography and Network Security. 423--441.
• 20: Hu, Y., Perrig, A., and Johnson, D. 2003. Packet leashes: A defense against wormhole attacks in wireless ad hoc networks. In Proceedings of INFOCOM'03.
• 21: IEEE Computer Society. 2003. IEEE 802.15.4: IEEE standard for information technology---telecommunications and information exchange between systems local and metropolitan area networks---specific requirements part 15.4: Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANs). http://standards.ieee.org/getieee802/download/802.15.4-2003.pdf.
• 22: Intel Research. Intel mote. http://www.intel.com/research/exploratory/motes.htm.
• 23: Juels, A. and Brainard, J. 1999. Client puzzles: A cryptographic countermeasure against connection depletion attacks. In Proceedings of the 6th Network and Distributed Systems Security Symposium (NDSS'99).
• 24: Karlof, C., Sastry, N., Li, Y., Perrig, A., and Tygar, J. 2004. Distillation codes and applications to dos resistant multicast authentication. In Proceedings of the 11th Network and Distributed Systems Security Symposium (NDSS'04). 37--56.
• 25: Philip Levis , Neil Patel , David Culler , Scott Shenker, Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.2-2, March 29-31, 2004, San Francisco, California
• 26: Liu, A., Kampanakis, P., and Ning, P. TinyECC: Elliptic curve cryptography for sensor networks (version 0.3). http://discovery.csc.ncsu.edu/software/TinyECC/.
• 27: Liu, D. and Ning, P. 2003. Efficient distribution of key chain commitments for broadcast authentication in distributed sensor networks. In Proceedings of the 10th Annual Network and Distributed System Security Symposium (NDSS'03). 263--276.
• 28: Donggang Liu , Peng Ning, Multilevel μTESLA: Broadcast authentication for distributed sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.4, p.800-836, November 2004 [doi>10.1145/1027794.1027800]
• 29: Donggang Liu , Peng Ning , Sencun Zhu , Sushil Jajodia, Practical Broadcast Authentication in Sensor Networks, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.118-132, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.49]
• 30: Sara Miner , Jessica Staddon, Graph-Based Authentication of Digital Streams, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.232, May 14-16, 2001
• 31: James Newsome , Dawn Song, GEM: Graph EMbedding for routing and data-centric storage in sensor networks without geographic information, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958501]
• 32: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 33: Niculescu, D. and Nath, B. 2001. Ad hoc positioning system (APS). In Proceedings of IEEE GLOBECOM '01.
• 34: Pannetrat, A. and Molva, R. 2003. Efficient multicast packet authentication. In Proceedings of the 10th Network and Distributed Systems Security Symposium (NDSS'03). 251--262.
• 35: Jung Min Park , Edwin K. P. Chong , Howard Jay Siegel, Efficient multicast stream authentication using erasure codes, ACM Transactions on Information and System Security (TISSEC), v.6 n.2, p.258-285, May 2003 [doi>10.1145/762476.762480]
• 36: Adrian Perrig, The BiBa one-time signature and broadcast authentication protocol, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.501988]
• 37: Adrian Perrig , J. D. Tygar , Dawn Song , Ran Canetti, Efficient Authentication and Signing of Multicast Streams over Lossy Channels, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.56, May 14-17, 2000
• 38: Perrig, A., Canetti, R., Song, D., and Tygar, D. 2001. Efficient and secure source authentication for multicast. In Proceedings of the Network and Distributed System Security Symposium.
• 39: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 40: Leonid Reyzin , Natan Reyzin, Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying, Proceedings of the 7th Australian Conference on Information Security and Privacy, p.144-153, July 03-05, 2002
• 41: R. Rivest, The MD4 Message-Digest Algorithm, RFC Editor, 1992
• 42: Rivest, R., Robshaw, M., Sidney, R., and Yin, Y. 1998. The RC6 block cipher. NIST Fist AES Candidate Conference.
• 43: Dawn Song , J. D. Tygar , David Zuckerman, Expander Graphs for Digital Stream Authentication and Robust Overlay Networks, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.258, May 12-15, 2002
• 44: Ivan Stojmenovic , Mahtab Seddigh , Jovisa Zunic, Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.14-25, January 2002 [doi>10.1109/71.980024]
• 45: XiaoFeng Wang , Michael K. Reiter, Mitigating bandwidth-exhaustion attacks using congestion puzzles, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030118]
• 46: Brent Waters , Ari Juels , J. Alex Halderman , Edward W. Felten, New client puzzle outsourcing techniques for DoS resistance, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030117]
• 47: Wenyuan Xu , Wade Trappe , Yanyong Zhang , Timothy Wood, The feasibility of launching and detecting jamming attacks in wireless networks, 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.1062697]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Security

Keywords:
DoS attacks, Sensor networks, broadcast authentication, security