A ROM-friendly secure code update mechanism for WSNs using a stateful-verifier τ-time signature scheme

ABSTRACT

Several mechanisms have been proposed to efficiently authenticate multicast of finite data streams as needed for code image updates in wireless sensor networks (WSNs). They involve either a public-key digital signature or loose time synchronization between the sender and the receivers. What usually does not get any attention is the program memory (ROM) occupied by these mechanisms which do not fulfill the primary task of a sensor network.

An optimized implementation of the elliptic curve digital signature scheme occupies up to 25% of the ROM of a TelosB node; the same or even more is needed for time synchronization schemes. Therefore, if sensor networks do not need public-key operations or time synchronization for their primary task, these SCU mechanism are not suitable for coexistence with the application code on the sensor nodes. This work contributes in two directions. Firstly, we propose a stateful-verifier T-time signature scheme based on Merkle's one-time signature. Secondly, we propose a protocol exploiting our signature scheme for securing existing code image update protocols for WSNs minimizing ROM overhead to 1% on TelosB motes.

REFERENCES

• 1: TinyOS: An open-source operating system designed for wireless embedded sensor networks, 2007. http://www.tinyos.net/.
• 2: Piotr Berman , Marek Karpinski , Yakov Nekrich, Optimal trade-off for Merkle tree traversal, Theoretical Computer Science, v.372 n.1, p.26-36, March, 2007 [doi>10.1016/j.tcs.2006.11.029]
• 3: Jens-Matthias Bohli , Alban Hessler , Osman Ugus , Dirk Westhoff, A secure and resilient WSN roadside architecture for intelligent transport systems, Proceedings of the first ACM conference on Wireless network security, March 31-April 02, 2008, Alexandria, VA, USA [doi>10.1145/1352533.1352562]
• 4: Ran Canetti, Juan Garay, Gene Itkis, Daniele Micciancio, Moni Naor, and Benny Pinkas. Multicast security: A taxonomy and some efficient constructions. In Proc. IEEE INFOCOM'99, volume 2, pages 708{716, New York, NY, March 1999. IEEE.
• 5: Jing Deng , Richard Han , Shivakant Mishra, Secure code distribution in dynamically programmable wireless sensor networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127822]
• 6: Benedikt Driessen , Axel Poschmann , Christof Paar, Comparison of innovative signature algorithms for WSNs, Proceedings of the first ACM conference on Wireless network security, March 31-April 02, 2008, Alexandria, VA, USA [doi>10.1145/1352533.1352539]
• 7: Prabal K. Dutta , Jonathan W. Hui , David C. Chu , David E. Culler, Securing the deluge Network programming system, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127826]
• 8: Christian Gehrmann and Mats Näslund. ECRYPT Yearly Report on Algorithms and Keysizes (2006), D.SPA.21 Rev. 1.1, January 2007.
• 9: 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
• 10: Jonathan W. Hui , David Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031506]
• 11: Sangwon Hyun , Peng Ning , An Liu , Wenliang Du, Seluge: Secure and DoS-Resistant Code Dissemination in Wireless Sensor Networks, Proceedings of the 7th international conference on Information processing in sensor networks, p.445-456, April 22-24, 2008 [doi>10.1109/IPSN.2008.12]
• 12: Markus Jakobsson, Tom Leighton, Silvio Micali, and Michael Szydlo. Fractal merkle tree representation and traversal. In Topics in Cryptology - CT-RSA 2003: The Cryptographers' Track at the RSA Conference 2003, pages 314--326. Springer, 2003.
• 13: Donnie H. Kim , Rajeev Gandhi , Priya Narasimhan, Exploring Symmetric Cryptography for Secure Network Reprogramming, Proceedings of the 27th International Conference on Distributed Computing Systems Workshops, p.17, June 22-29, 2007 [doi>10.1109/ICDCSW.2007.37]
• 14: Patrick E. Lanigan , Rajeev Gandhi , Priya Narasimhan, Sluice: Secure Dissemination of Code Updates in Sensor Networks, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.53, July 04-07, 2006 [doi>10.1109/ICDCS.2006.77]
• 15: An Liu and Peng Ning. TinyECC: Elliptic Curve Cryptography for Sensor Networks (Version 1.0), 2007 2007.
• 16: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 17: Ralph C. Merkle, A certified digital signature, Proceedings on Advances in cryptology, p.218-238, July 1989, Santa Barbara, California, United States
• 18: Adrian Perrig , Robert Szewczyk , J. D. Tygar , Victor Wen , David E. Culler, SPINS: security protocols for sensor networks, Wireless Networks, v.8 n.5, p.521-534, September 2002 [doi>10.1023/A:1016598314198]
• 19: Kun Sun , Peng Ning , Cliff Wang, TinySeRSync: secure and resilient time synchronization in wireless sensor networks, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180439]
• 20: Michael Szydlo. Merkle tree traversal in log space and time. In Advances in Cryptology - EUROCRYPT'04, pages 541--554. Springer, 2004.
• 21: Hailun Tan , Sanjay Jha , Diet Ostry , John Zic , Vijay Sivaraman, Secure multi-hop network programming with multiple one-way key chains, Proceedings of the first ACM conference on Wireless network security, March 31-April 02, 2008, Alexandria, VA, USA [doi>10.1145/1352533.1352564]
• 22: O. Ugus, D. Westhoff, R. Laue, A. Shoufan, and S.A. Huss. Optimized implementation of elliptic curve based additive homomorphic encryption for wireless sensor networks. In 2nd Workshop on Embedded Systems Security, WESS'2007, 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

General Terms:
Algorithms, Design, Security

Keywords:
data authentication, one-time signature, secure code image update, wireless sensor networks