An efficient scheme for authenticating public keys in sensor networks

ABSTRACT

With the advance of technology, Public Key Cryptography (PKC) will sooner or later be widely used in wireless sensor networks. Recently, it has been shown that the performance of some public-key algorithms, such as Elliptic Curve Cryptography (ECC), is already close to being practical on sensor nodes. However, the energy consumption of PKC is still expensive, especially compared to symmetric-key algorithms. To maximize the lifetime of batteries, we should minimize the use of PKC whenever possible in sensor networks.This paper investigates how to replace one of the important PKC operations--the public key authentication--with symmetric key operations that are much more efficient. Public key authentication is to verify the authenticity of another party's public key to make sure that the public key is really owned by the person it is claimed to belong to. In PKC, this operation involves an expensive signature verification on a certificate. We propose an efficient alternative that uses one-way hash function only. Our scheme uses all sensor's public keys to construct a forest of Merkle trees of different heights. By optimally selecting the height of each tree, we can minimize the computation and communication costs. The performance of our scheme is evaluated in the paper.

REFERENCES

• 1: Ansi x9.62, elliptic curve key agreement and key transport protocols. American Bankers Association, 1999.
• 2: NIST, special publication 800-57: Recommendation for key management. part 1: General guideline. Draft, January, 2003.
• 3: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 4: S.A. Camtepe and B. Yener. Combinatorial design of key distribution mechanisms for wireless sensor networks. In Proceedings of 9th European Symposium On Research in Computer Security (ESORICS '04), 2004.
• 5: D.W. Carman, P.S. Kruus, and B.J.Matt. Constrains and approaches for distributed sensor network security. Technical report, 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: Crossbow Technology Inc. Wireless sensor networks. http://www.xbow.com/. 2004.
• 8: 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]
• 9: W. Du, J. Deng, Y. S. Han, S. Chen, and P. K. Varshney. A key management scheme for wireless sensor networks using deployment knowledge. In Proceedings of the IEEE Infocom 04, pages 586--597, Hongkong, China, March 27-31 2004.
• 10: 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]
• 11: D. Eastlake and P. Jones. Us secure hash algorithm 1 (SHA1). IETF RFC 3174, September 2001.
• 12: 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]
• 13: Prasanth Ganesan , Ramnath Venugopalan , Pushkin Peddabachagari , Alexander Dean , Frank Mueller , Mihail Sichitiu, Analyzing and modeling encryption overhead for sensor network nodes, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941372]
• 14: G. Gaubatz, J. Kaps, and B. Sunar. Public keys cryptography in sensor networks -- revisited. In The Proceedings of the 1st European Workshop on Security in Ad-Hoc and Sensor Networks (ESAS), 2004.
• 15: N. Gura, A. Patel, A. Wander, H. Eberle, and S. C. Shantz. Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs. August 11-13 2004.
• 16: C. Karlof, N. Sastry, and D. Wagner. TinySec: Link layer encryption for tiny devices. In ACM SenSys, Baltimore, Maryland, USA, November 3-5 2004.
• 17: A. Leon-Garcia. Probability and Random Processes for Electrical Engineering. Reading, MA: Addison-Wesley Publishing Company, Inc., second edition, 1994.
• 18: D. Liu and P. Ning. Efficient distribution of key chain commitments for broadcast authentication in distributed sensor networks. In Proceedings of the 10th Annual Network and Distributed System Security Symposium, pages 263--276, February 2003.
• 19: 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]
• 20: D. J. Malan, M. Welsh, and M. D. Smith. A public-key infrastructure for key distribution in TinyOS based on elliptic curve cryptography. In The First IEEE International Conference on Sensor and Ad Hoc Communications and Networks, Santa Clara, California, October 2004.
• 21: R. Merkle. Protocols for public key cryptosystems. In Proceedings of the IEEE Symposium on Research in Security and Privacy, Apr 1980.
• 22: 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]
• 23: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 24: R. Rivest. The MD5 message-digest algorithm. In Internet Request for Comment RFC 1321, April 1992.
• 25: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 26: 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]
• 27: 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]

INDEX TERMS

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

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, Performance, Security

Keywords:
deployment knowledge, merkle tree, public key, wireless sensor networks