A random perturbation-based scheme for pairwise key establishment in sensor networks

ABSTRACT

A prerequisite for secure communications between two sensor nodes is that these nodes exclusively share a pairwise key. Although numerous pairwise key establishment (PKE) schemes have been proposed in recent years, most of them have no guarantee for direct key establishment, no resilience to a large number of node compromises, no resilience to dynamic network topology, or high overhead. To address these limitations, we propose a novel random perturbation-based (RPB) scheme in this paper. The scheme guarantees that any two nodes can directly establish a pairwise key without exposing any secret to other nodes. Even after a large number of nodes have been compromised, the pairwise keys shared by non-compromised nodes remain highly secure. Moreover, the scheme adapts to changes in network topology and incurs low computation and communication overhead. To the best of our knowledge, the RPB scheme is the only one that provides all these salient features without relying on public key cryptography. Through prototype-based evaluation, we show that the RPB scheme is highly efficient and practical for current generation of sensor nodes. In particular, to support a sensor network with up to 2¹⁶ nodes, establishing a pairwise key of 80 bits between any two 8-bit, 7.37-MHz MICA2 motes only requires about 0.13 second of CPU time, 0.33 KB RAM space, and 15 KB ROM space per node.

REFERENCES

• 1: 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]
• 2: Sencun Zhu , Sanjeev Setia , Sushil Jajodia, LEAP: efficient security mechanisms for large-scale distributed sensor networks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948120]
• 3: Fan Ye , Haiyun Luo , Jerry Cheng , Songwu Lu , Lixia Zhang, A two-tier data dissemination model for large-scale wireless sensor networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570664]
• 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: Wenliang Du , Jing Deng , Yunghsiang S. Han , Pramod K. Varshney, A pairwise key pre-distribution scheme for wireless sensor networks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948118]
• 7: Donggang Liu , Peng Ning, Establishing pairwise keys in distributed sensor networks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948119]
• 8: 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
• 9: Ross J. Anderson , Markus G. Kuhn, Low Cost Attacks on Tamper Resistant Devices, Proceedings of the 5th International Workshop on Security Protocols, p.125-136, April 07-09, 1997
• 10: Helena Handschuh , Pascal Paillier , Jacques Stern, Probing Attacks on Tamper-Resistant Devices, Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, p.303-315, August 12-13, 1999
• 11: S. Skorobogatov, "Low temperature data remanence in static ram," in University of Cambridge, Computer Laboratory, Technical Report UCAM-CL-TR-536, June 2002.
• 12: David Samyde , Sergei Skorobogatov , Ross Anderson , Jean-Jacques Quisquater, On a New Way to Read Data from Memory, Proceedings of the First International IEEE Security in Storage Workshop, p.65, December 11-11, 2002
• 13: "Cotsbots: The mobile mote-based robots," http://www-bsac.eecs.berkeley.edu/projects/cotsbots/.
• 14: Roberto Di Pietro , Luigi V. Mancini , Alessandro Mei, Random key-assignment for secure Wireless Sensor Networks, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986868]
• 15: W. Du, J. Deng, Y. Han, and S. Chen, "A key management scheme for wireless sensor networks using deployment knowledge," IEEE INFOCOM'04, March 2004.
• 16: Donggang Liu , Peng Ning, Location-based pairwise key establishments for static sensor networks, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986869]
• 17: Haowen Chan and Adrian Perrig, "PIKE: Peer intermediaries for key establishment in sensor networks," in Proceedings of IEEE Infocom, Mar. 2005.
• 18: Arno Wacker , Mirko Knoll , Timo Heiber , Kurt Rothermel, A new approach for establishing pairwise keys for securing wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098922]
• 19: D. Malan, M. Welsh, and M. Smith, "A public-key infrastructure for key distribution in tinyos based on elliptic curve cryptography," First IEEE International Conference on Sensor and Ad Hoc Communications and Networks (SECON), October 2004.
• 20: Ronald Watro , Derrick Kong , Sue-fen Cuti , Charles Gardiner , Charles Lynn , Peter Kruus, TinyPK: securing sensor networks with public key technology, Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, October 25-25, 2004, Washington DC, USA [doi>10.1145/1029102.1029113]
• 21: Arvinderpal S. Wander , Nils Gura , Hans Eberle , Vipul Gupta , Sheueling Chang Shantz, Energy Analysis of Public-Key Cryptography for Wireless Sensor Networks, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, p.324-328, March 08-12, 2005 [doi>10.1109/PERCOM.2005.18]
• 22: Gunnar Gaubatz , Jens-Peter Kaps , Erdinc Ozturk , Berk Sunar, State of the Art in Ultra-Low Power Public Key Cryptography for Wireless Sensor Networks, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications Workshops, p.146-150, March 08-12, 2005 [doi>10.1109/PERCOMW.2005.76]
• 23: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 24: W. Zhang and G. Cao, "Group rekeying for filtering false data in sensor networks: A predistribution and local collaboration-based approach," IEEE Infocom 2005, March 2005.
• 25: "Crossbow technology inc," http://www.xbow.com 2004.
• 26: R. Rivest, "The rc5 encryption algorithm," in Proceedings of the 1st International Workshop on Fast Software Encryption, 1994, pp. 86--96.
• 27: C. Karlof, N. Sastry, U. Shankar, and D. Wagner, "Tinysec: Tinyos link layer security proposal, version 1.0," 2002.
• 28: Mihir Bellare , Roch Guérin , Phillip Rogaway, XOR MACs: New Methods for Message Authentication Using Finite Pseudorandom Functions, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.15-28, August 27-31, 1995
• 29: 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
• 30: Victor Shnayder , Mark Hempstead , Bor-rong Chen , Geoff Werner Allen , Matt Welsh, Simulating the power consumption of large-scale sensor network applications, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031518]

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:
pairwise key establishment, polynomial, random perturbation, sensor network security