Establishing pairwise keys in distributed sensor networks

ABSTRACT

Pairwise key establishment is a fundamental security service in sensor networks; it enables sensor nodes to communicate securely with each other using cryptographic techniques. However, due to the resource constraints on sensors, it is infeasible to use traditional key management techniques such as public key cryptography and key distribution center (KDC). To facilitate the study of novel pairwise key predistribution techniques, this paper presents a general framework for establishing pairwise keys between sensors on the basis of a polynomial-based key predistribution protocol [2]. This paper then presents two efficient instantiations of the general framework: a random subset assignment key predistribution scheme and a grid-based key predistribution scheme. The analysis in this paper indicates that these two schemes have a number of nice properties, including high probability (or guarantee) to establish pairwise keys, tolerance of node captures, and low communication overhead. Finally, this paper presents a technique to reduce the computation at sensors required by these schemes.

REFERENCES

• 1: 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]
• 2: Carlo Blundo , Alfredo De Santis , Amir Herzberg , Shay Kutten , Ugo Vaccaro , Moti Yung, Perfectly-Secure Key Distribution for Dynamic Conferences, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.471-486, August 16-20, 1992
• 3: D.W. Carman, P.S. Kruus, and B.J.Matt. Constrains and approaches for distributed sensor network security. Technical report, NAI Labs, 2000.
• 4: 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
• 5: 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]
• 6: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 7: C. Karlof and D. Wagner. Secure routing in wireless sensor networks: Attacks and countermeasures. In First IEEE Int'l Workshop on Sensor Network Protocols and Applications, May 2003.
• 8: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 9: D. Liu and P. Ning. Efficient distribution of key chain commitments for broadcast authentication in distributed sensor networks. In Proc. of the 10th Annual Network and Distributed System Security Symposium, pages 263--276, February 2003.
• 10: 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
• 11: A. Perrig, R. Canetti, D. Song, and D. Tygar. Efficient and secure source authentication for multicast. In Proc. of Network and Distributed System Security Symposium, February 2001.
• 12: 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]
• 13: Frank Stajano , Ross J. Anderson, The Resurrecting Duckling: Security Issues for Ad-hoc Wireless Networks, Proceedings of the 7th International Workshop on Security Protocols, p.172-194, April 19-21, 1999
• 14: William Stallings, Cryptography and network security (2nd ed.): principles and practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 15: Duncan S. Wong , Agnes Hui Chan, Efficient and Mutually Authenticated Key Exchange for Low Power Computing Devices, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.272-289, December 09-13, 2001
• 16: Anthony D. Wood , John A. Stankovic, Denial of Service in Sensor Networks, Computer, v.35 n.10, p.54-62, October 2002 [doi>10.1109/MC.2002.1039518]

INDEX TERMS

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

General Terms:
Design, Security

Keywords:
key management, probabilistic key sharing, sensor networks