Random key-assignment for secure Wireless Sensor Networks

ABSTRACT

A distributed Wireless Sensor Network (WSN) is a collection of n sensors with limited hardware resources. Sensors can exchange messages via Radio Frequency (RF), whose range usually covers only a limited number of other sensors. An interesting problem is how to implement secure pair-wise communications among any pair of sensors in a WSN. A WSN requires completely distributed solutions which are particularly challenging due to the limited resources and the size of the network. Moreover, WSNs can be subject to several security threats, including the physical compromising of a sensor. Hence, any solution for secure pairwise communications should tolerate the collusion of a set of corrupted sensors. This paper describes a probabilistic model and two protocols to establish a secure pair-wise communication channel between any pair of sensors in the WSN, by assigning a small set of random keys to each sensor. We build, based on the first Direct Protocol, a second Co-operative Protocol. The Co-operative Protocol is adaptive: its security properties can be dynamically changed during the life-time of the WSN. Both protocols also guarantee implicit and probabilistic mutual authentication without any additional overhead and without the presence of a base station. The performance of the Direct Protocol is analytically characterized while, for the Co-operative Protocol, we provide both analytical evaluations and extensive simulations. For example, the results show that, assuming each sensor stores 120 keys, in a WSN composed of 1024 sensors with 32 corrupted sensors the probability of a channel corruption is negligible in the case of the Co-operative Protocol.

REFERENCES

• 1: Giuseppe Ateniese, Michael Steiner, and Gene Tsudik. New multiparty authentication services and key agreement protocols. IEEE Journal on Selected Areas in Communications, 18(4), 2000.
• 2: Stefano Basagni, Distributed Clustering for Ad Hoc Networks, Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), p.310, June 23-25, 1999
• 3: Stefano Basagni , Kris Herrin , Danilo Bruschi , Emilia Rosti, Secure pebblenets, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501436.501438]
• 4: Mihir Bellare , Ran Canetti , Hugo Krawczyk, Keying Hash Functions for Message Authentication, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.1-15, August 18-22, 1996
• 5: D. W. Carman, P. S. Kruus, and B. J. Matt. Constraints and approaches for distributed sensor network security. Technical Report #00-010, NAI Labs, 2000.
• 6: Haowen Chan , Adrian Perrig , Dawn Song, Random Key Predistribution Schemes for Sensor Networks, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.197, May 11-14, 2003
• 7: Jyh-Cheng Chen , Krishna M. Sivalingam , Prathima Agrawal, Performance comparison of battery power consumption in wireless multiple access protocols, Wireless Networks, v.5 n.6, p.445-460, 1999 [doi>10.1023/A:1019136102972]
• 8: Roberto Di Pietro , Luigi V. Mancini , Sushil Jajodia, Secure Selective Exclusion in Ad Hoc Wireless Network, Proceedings of the IFIP TC11 17th International Conference on Information Security: Visions and Perspectives, p.423-434, May 07-09, 2002
• 9: Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):644--654, 1976.
• 10: Laurent Eschenauer , Virgil D. Gligor, A key-management scheme for distributed sensor networks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586117]
• 11: A. D. Amis et al. Max-min d-cluster formation in wireless ad hoc networks. In Proceedings of INFOCOM 2000, pages 32--41, 2000.
• 12: John Haigh. Probabilty Models. Springer, 2002. ISBN 1-85233-431-2.
• 13: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, ACM SIGPLAN Notices, v.35 n.11, p.93-104, Nov. 2000 [doi>10.1145/356989.356998]
• 14: Yih-Chun Hu , Adrian Perrig , David B. Johnson, Ariadne:: a secure on-demand routing protocol for ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570648]
• 15: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 16: Sergio Marti , T. J. Giuli , Kevin Lai , Mary Baker, Mitigating routing misbehavior in mobile ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.255-265, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345955]
• 17: NIST. Fips pub 140-1, security requirements for cryptographic modules. National Institute of Standard and Technology, January 1994.
• 18: Charles E. Perkins. Ad Hoc Networking. Addison Wesley Professional, 2001. ISBN 0-201-30976-9.
• 19: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor netowrks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 20: Lakshmi Ramachandran , Manika Kapoor , Abhinanda Sarkar , Alok Aggarwal, Clustering algorithms for wireless ad hoc networks, Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications, p.54-63, August 11-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345848.345860]
• 21: E. M. Royer and C-K Toh. A review of current routing protocols for ad hoc mobile wireless network. In IEEE Personal Communication Magazine, pages 46--55, April 1999.
• 22: Amit Sinha , Anantha Chandrakasan, Dynamic Power Management in Wireless Sensor Networks, IEEE Design & Test, v.18 n.2, p.62-74, March 2001 [doi>10.1109/54.914626]
• 23: Michael Steiner , Gene Tsudik , Michael Waidner, Key Agreement in Dynamic Peer Groups, IEEE Transactions on Parallel and Distributed Systems, v.11 n.8, p.769-780, August 2000 [doi>10.1109/71.877936]
• 24: Yongguang Zhang , Wenke Lee, Intrusion detection in wireless ad-hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.275-283, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345958]
• 25: Sencun Zhu , Shouhuai Xu , Sanjeev Setia , Sushil Jajodia, Establishing Pairwise Keys for Secure Communication in Ad Hoc Networks: A Probabilistic Approach, Proceedings of the 11th IEEE International Conference on Network Protocols, p.326, November 04-07, 2003

INDEX TERMS

Keywords:
distributed wireless sensors networks, key management protocols, secure pair-wise communications, sensor-to-sensor authentication