Modeling pairwise key establishment for random key predistribution in large-scale sensor networks

Abstract

Sensor networks are composed of a large number of low power sensor devices. For secure communication among sensors, secret keys are required to be established between them. Considering the storage limitations and the lack of post-deployment configuration information of sensors, RandomKey Predistribution schemes have been proposed. Due to limited number of keys, sensors can only share keys with a subset of the neighboring sensors. Sensors then use these neighbors to establish pairwise keys with the remaining neighbors. In order to study the communication overhead incurred due to pairwise key establishment, we derive probability models to design and analyze pairwise key establishment schemes for large-scale sensor networks. Our model applies the binomial distribution and a modified binomial distribution and analyzes the key path length in a hop-by-hop fashion. We also validate our models through a systematic validation procedure. We then show the robustness of our results and illustrate how our models can be used for addressing sensor network design problems.

References

1. {1} I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Commun. Mag., vol. 40, pp. 102-114, Aug. 2002.
2. {2} R. Blom, "An optimal class of symmetric key generation systems," in EUROCRYPT'84, ser. Lecture Notes in Computer Science. Paris, France: Springer-Verlag, 1985, vol. 209, pp. 335-338.
3. {3} C. Blundo, A. D. Santis, A. Herzberg, S. Kutten, U. Vaccaro, and M. Yung, "Perfectly-secure key distribution for dynamic conferences," Inf. Comput., vol. 146, no. 1, pp. 1-23, 1998.
4. {4} B. Bollobás, Modern Graph Theory. New York: Springer-Verlag, 1998.
5. {5} D. W. Carman, P. S. Kruus, and B. J. Matt, "Constraints and approaches for distributed sensor network security," NAI Laboratory, Tech. Rep., Sep. 2000.
6. {6} H. Chan, A. Perrig, and D. Song, "Random key predistribution schemes for sensor networks," in Proc. 2003 Symp. Security Privacy. Alamitos, CA: IEEE Computer Society, 2003, pp. 197-215.
7. {7} R. Di Pietro, L. V. Mancini, and A. Mei, "Efficient and resilient key discovery based on pseudo-random key pre-deployment," in Proc. 18th Int. Parallel Distributed Processing Symp. (IPDPS'04), Apr. 2004, p. 217.
8. {8} W. Du, J. Deng, Y. S. Han, and P. K. Varshney, "A pairwise key predistribution scheme for wireless sensor networks," in Proc. 10th ACM Conf. Computer Communications Security (CCS'03), Oct. 2003, pp. 42-51.
9. {9} W. Du, J. Deng, Y. S. Han, P.Varshney, J. Katz, and A. Khalili, "A pairwise key pre-distribution scheme for wireless sensor networks," ACM Trans. Inf. Syst. Secur., 2005, accepted for publication.
10. {10} L. Eschenauer and V. D. Gligor, "A key-management scheme for distributed sensor networks," in Proc. 9th ACM Conf. Computer Communication Security (CCS-02), Nov. 2002, pp. 41-47.
11. {11} V. D. Gligor and P. Donescu, "Fast encryption and authentication: XCBCencryption and XECBauthentication modes," in Proc. 2nd NIST Workshop AES Modes of Operation, Aug. 2001, pp. 92-108.
12. {12} J. Hill, R. Szewczyk, A.Woo, S. Hollar, D. E. Culler, and K. S. J. Pister, "System architecture directions for networked sensors," in Proc. Architectural Support for Programming Languages Operating Systems, 2000, pp. 93-104.
13. {13} D. Huang, M. Mehta, and D. Medhi, "Source routing based pairwise key establishment protocol for sensor networks," in Proc. 24th IEEE Int. Performance Computing Communications Conf., 2005, pp. 177-183.
14. {14} D. Huang, M. Mehta, D. Medhi, and H. Lein, "Location-aware key management scheme for wireless sensor networks," in Proc. ACM Workshop Security of Ad Hoc Sensor Networks (SASN'04), Oct. 2004, pp. 29-42.
15. {15} D. Liu and P. Ning, "Establishing pairwise keys in distributed sensor networks," in Proc. 10th ACM Conf. Computer Communications Security (CCS'03), Oct. 2003, pp. 52-61.
16. {16} D. Liu, P. Ning, and R. Li, "Establishing pairwise keys in distributed sensor networks," ACM Trans. Information System Security, vol. 8, no. 1, pp. 41-77, 2005.
17. {17} M. Mehta, D. Huang, and L. Harn, "RINK-RKP: A scheme for key predistribution and shared-key discovery in sensor networks," in Proc. 24th IEEE Int. Performance Computing Communications Conf., 2005, pp. 193-197.
18. {18} M. D. Penrose, "On k-connectivity for a geometric random graph," Random Struct. Algorithms, vol. 15, no. 2, pp. 145-164, Sep. 1999.
19. {19} P. E. Pfeiffer and D. A. Schum, Introduction to Applied Probability. New York: Academic, 1973.
20. {20} J. H. Spencer, The Strange Logic of Random Graphs (Algorithms and Combinatorics, ser. 22. New York: Springer-Verlag, 2001.
21. {21} F. Xue and P. R. Kumar, "The number of neighbors needed for connectivity of wireless networks," Wireless Netw., vol. 10, pp. 169-181, 2004.
22. {22} S. Zhu, S. Xu, S. Setia, and S. Jajodia, "Establishing pair-wise keys for secure communication in ad hoc networks: A probabilistic approach," in Proc. 11th IEEE Int. Conf. Network Protocols (ICNP), Nov. 2003, pp. 326-335.

Index Terms

• Hardware

  • Communication hardware, interfaces and storage

    • Signal processing systems

• Information systems

  • Data management systems

    • Data structures

      • Data layout

        • Data encryption

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks

• Security and privacy

  • Cryptography

• Social and professional topics

  • Computing / technology policy

    • Computer crime

• Theory of computation

  • Computational complexity and cryptography