An efficient symmetric polynomial-based key establishment protocol for wireless sensor networks

Document Type: ORIGINAL RESEARCH PAPER

Authors

Abstract

An essential requirement for providing secure services in wireless sensor networks is the ability to establish pairwise keys among sensors. Due to resource constraints on the sensors, the key establishment scheme should not create significant overhead. To date, several key establishment schemes have been proposed. Some of these have appropriate connectivity and resistance against key exposure, but the resources needed in the sensors are substantial. Others are appropriate from the resource consumption perspective, but have weak performance. This paper proposes a key establishment protocol based on symmetric polynomials. To improve performance, the protocol uses a new model to distribute polynomial shares to the sensors. A key feature of the proposed protocol is the trade-off between performance, security and resource consumption. Analysis shows that our solution has good performance compared to other approaches.

Keywords


[1] Gregory J. Pottie and William J. Kaiser. Wireless Integrated Network Sensors. Communications of the ACM, 43(5):51-58, 2000.

[2] Joseph M. Kahn, Randy H. Katz, and Kristofer S. J. Pister. Next Century Challenges: Mobile Networking for "Smart Dust". In Proceeding of the 5th ACM International Conference on Mobile Computing and Networking (MobiCom), pages 271-278, Seattle, Washington, USA, August 1999.

[3] Lan F. Akyildiz, Welljan Su, Yogesh Sankara subramaniam, and Erdal Cayirci. A Survey on Sensor Networks. IEEE Communication Magazine, 40(8):102-114, August 2002.

[4] Adrian Perrig, Robert Szewczyk, J. D. Tygar, Victor Wen, and David E. Culler. SPINS: Security Protocols for Sensor Networks. Wireless Networks, 8(5):521-534, September 2002.

[5] Anthony D. Wood and John A. Stankovic. Denial of Service in Sensor Networks. IEEE Computer Magazine, 35(10):54-62, October 2002.

[6] H.T. Kung and Dario Vlah. Efficient Location Tracking Using Sensor Networks. In Proceeding of IEEE Wireless Communications and Networking Conference (WCNC), pages 1954-1961, New Orleans, LA, USA, March 2003.

[7] Richard R. Brooks, Parameswaran Ramanathan, and Akbar M. Sayeed. Distributed Target Classification and Tracking in Sensor Networks. Proceedings of the IEEE, 91(8): 1163-1171, August 2003.

[8] Chris Karlof and David Wagner. Secure Routing in Wireless Sensor Networks: Attacks and Countermeasures. In Proceedings of the 1st IEEE Workshop on Sensor Network Protocols and Applications (SNPA), pages 113-127, May 2003.

[9] Ronald Watro, Derrick Kong, Sue-fen Cuti, Charles Gardiner, Charles Lynn, and Peter Kruus. TinyPK: Securing Sensor Networks with Public Key Technology. In Proceedings of the 2nd ACM Workshop on Security of Ad hoc and Sensor Networks (SASN), pages 59-64, Washington DC, USA, October 2004. ACM.

[10] David J. Malan, Matt Welsh, and Michael D. Smith. A Public-Key Infrastructure for Key Distribution in TinyOS Based on Elliptic Curve Cryptography. In Proceeding of the 1st IEEE International Conference on Sensor and Ad hoc Communication and Networks (SECON), pages 71-80, Santa Clara, California, USA, October 2004. IEEE.

[11] Nils Gura, Arun Patel, Arvinderpal Wander, Hans Eberle, and Sheueling C. Shantz. Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs. In Proceeding of the International Workshop Cryptographic Hardware and Embedded System (CHES), pages 119-132, Boston, Cambridge, USA, August 2004. Springer.

[12] Haodong Wang and Qun Li. Efficient Implementation of Public Key Cryptosystems on Mote Sensors (Short Paper). In Proceeding of the 8th International Conference on Information and Communication Security (ICICS), volume 4307 of Lecture Notes in Computer Science (LNCS), pages 519-528. Springer, December 2006.

[13] Zhen Yu and Yong Guan. A Key Management Scheme Using Deployment Knowledge for Wireless Sensor Networks. IEEE Transaction on Parallel and Distributed Systems, 19(10):14111425, 2008.

[14] Haowen Chan, Adrian Perrig, and Dawn Song. Random Key Predistribution Schemes for Sensor Networks. In Proceeding of the IEEE Symposium on Security and Privacy, pages 197-213, Berkeley, California, USA, May 2003. IEEE.

[15] Laurent Eschenauer and Virgil D. Gligor. A Key-Management Scheme for Distributed Sensor Networks. In Proceedings of the 9th ACM Conference on Computer and Communications Security (CCS), pages 41-47, Washington, DC, USA, November 2002. ACM.

[16] Donggang Liu and Peng Ning. Establishing Pairwise Keys in Distributed Sensor Networks. In Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS), pages 52-61, Washington D.C., USA, October 2003. ACM.

[17] Reizhong Wei and Jiang Wu. Product Construction of Key Distribution Schemes for Sensor Networks. In Proceeding of the International Workshop on Selected Areas in Cryptography (SAC), volume 3897 of Lecture Notes in Computer Science (LNCS), pages 280-293,Waterloo, Ontario, Canada, August 2005. Springer.

[18] Donggang Liu and Peng Ning. Location-Based Pairwise Key Establishments for Relatively Static Sensor Networks. In Proceeding of the 1st ACM Workshop on Security of Ad hoc and Sensor Networks (SASN), pages 72-82, Fairfax, Virginia, USA, October 2003. ACM.

[19] Joengmin Hwang and Yongdae Kim. Revisiting Random Key Predistibution Schemes for Wireless Sensor Networks. In Proceeding of the 2nd ACM Workshop on Security of Ad hoc and Sensor Networks (SASN), pages 43-52, Washington DC, USA, October 2004. ACM.

[20] Wenliang Du, Jing Deng, Yunghsiang S. Han, and Pramod K. Varshney. A Pairwise Key Predistribution Scheme for Wireless Sensor Networks. In Proceedings of the 10th ACM conference on Computer and communications security (CCS), pages 42-51, Washington D.C., USA, October 2003. ACM.

[21] Roberto Di Pietro, Luigi V. Mancini, and Alessandro Mei. Random key-assignment for secure wireless sensor networks. In Proceedings of the 1st ACM Workshop on Security of Ad hoc and Sensor Networks (CCS), pages 62-71, Fair fax, Virginia, October 2003. ACM.

[22] Wenliang Du, Jing Deng, Yunghsiang S. Han, Shigang Chen, and Pramod Varshney. A Key Management Scheme for Wireless Sensor Networks Using Deployment Knowledge. In Proceeding of the 23th IEEE Conference on Computer Communications (INFOCOM), pages 586-597, Hong Kong, March 2004. IEEE.

[23] Mahalingam Ramkumar and Nasir D. Memon. An E_cient Random Key PreDistribution Scheme. In Proceeding of IEEE Global Telecommunication Conference (GLOBECOM), pages 2218-2223. IEEE, December 2004.

[24] Donggang Liu, Peng Ning, and Rongfang Li. Establishing Pairwise Keys in Distributed Sensor Networks. ACM Transaction Information and System Security, 8(1):41-77, February 2005.

[25] Haowen Chan and Adrian Perrig. Pike: Peer Intermediaries for Key Establishment in Sensor Networks. In Proceeding of the 24th IEEE Computer and Communications Societies (IN- FOCOM), pages 524-535, Miami, Florida, USA, March 2005. IEEE.

[26] Yun Zhou, Yanchao Zhang, and Yuguang Fang. Key Establishment in Sensor Networks Based on Triangle Grid Deployment Model. In Proceeding of the IEEE Military Communication Conference (MILCOM), pages 1450-1455, Atlantic City, New Jersey, USA, October 2005. IEEE.

[27] Dijiang Huang, Manish Mehta, Deep Medhi, and Lein Harn. Location-Aware Key Management Scheme for Wireless Sensor Networks. In Proceedings of the 2nd ACM Workshop on Security of Ad hoc and Sensor Networks (SASN), pages 29-42, Washington DC, USA, October 2004.

[28] Yun Zhou, Yanchao Zhang, and Yuguang Fang. LLK: A Link-Layer Key Establishment Scheme in Wireless Sensor Networks. In Proceeding of the IEEE Wireless Communication and Networking Conference (WCNC), pages 1921-1926, Mario Gerla, UCLA, USA, March 2005.

[29] Duncan S. Wong and Agnes Hui Chan. Efficient and Mutually Authenticated Key Exchange for Low Power Computing Devices. In Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), volume 2248 of Lecture Notes in Computer Science (LNCS), pages 272-289, Gold Coast, Australia, December 2001. Springer.

[30] Donggang Liu and Peng Ning. Efficient Distribution of Key Chain Commitments for Broadcast Authentication in Distributed Sensor Networks. In Proceeding of the 10th Annual Network and Distributed System Security Symposium (NDSS), pages 263-276, San Diego, California, USA, February 2003. The Internet Society.

[31] Chenyang Lu, Brian M. Blum, Tarek F. Abdelzaher, John A. Stankovic, and Tian He. Rap: A Real-time Communication Architecture for Large-scale Wireless Sensor Networks. In Proceeding of the 8th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 55-66, San Jose, California, USA, September 2002. IEEE.

[32] Yun Zhou and Yuguang Fang. A Two-Layer Key Establishment Scheme for Wireless Sensor Networks. IEEE Transaction Mobile Computing, 6(9):1009-1020, September 2007.

[33] Wenliang Du, Jing Deng, Yunghsiang S. Han, and Pramod K. Varshney. A key pre-distribution scheme for sensor networks using deployment knowledge. IEEE Transaction Dependable and Secure Computing, 3(1):62-77, March 2006.

[34] Stefano Basagni, Kris Herrin, Danilo Bruschi, and Emilia Rosti. Secure Pebblenets. In Proceedings of the 2nd ACM international symposium on Mobile Ad hoc Networking & Computing (MobiHoc), pages 156-163, Long Beach, California, USA, October 2001. ACM.

[35] Yun Zhou and Yuguang Fang. A Scalable Key Agreement Scheme for Large Scale Networks. In Proceeding of the IEEE International Conference on Networking, Sensing and Control (ICNSC), pages 631-636, Lauderdale, Florida, USA, April 2006. IEEE.

[36] Carlo Blundo, Alfredo De Santis, Amir Herzberg, Shay Kutten, Ugo Vaccaro, and Moti Yung. Perfectly-Secure Key Distribution for Dynamic Conferences. In Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO '92), pages 471-486, Santa Barbara, California, USA, August 1993. Springer.

[37] Rolf Blom. An Optimal Class of Symmetric Key Generation Systems. In Proceedings EURO-CRYPT 84, pages 335-338, Paris, France, April 1985. Springer.

[38] Peter Borwein and Tàmas Erdèlyi. Polynomials and Polynomial Inequalities, volume 161 of Graduate Texts in Mathematics. Springer, 1995.

[39] Yun Zhou and Yuguang Fang. Scalable LinkLayer Key Agreement in Sensor Networks. In Proceeding of the IEEE Military Communication Conference (MILCOM), pages 1-6, Washington D.C., USA, October 2006. IEEE.

[40] Vijay Bhuse and Ajay Gupta. Anomaly Intrusion Detection in Wireless Sensor Networks. Journal of High Speed Networks, 15(1):33-51, January 2006.

[41] Yun Wang, Xiaodong Wang, Bin Xie, Demin Wang, and Dharma P. Agrawal. Intrusion Detection in Homogeneous and Heterogeneous Wireless Sensor Networks. IEEE Transactions on Mobile Computing, 7(6):698-711, June 2008.

[42] Crossbow Technology. http://www.xbow.com/.

[43] TinyOS: An Open-Source OS for the Networked Sensor Regime. http://www.tinyos.net/.