Modeling key agreement in multi-hop ad hoc networks

ABSTRACT

Securing multicast communications in ad hoc networks has become one of the most challenging research directions in the areas of wireless networking and security. This is especially true as ad hoc networks are emerging as the desired environment for an increasing number of civilian, commercial and military applications, also addressing an increasingly large number of users. In this paper we study a very basic security question for Ad Hoc Networks: Key Agreement against passive adversaries. Despite being a widely studied area in wired networks, the problem becomes significantly more challenging for ad hoc networks, and even more for sensor networks, due to lack of trusted entities, infrastructures, full connectivity, routing structures, and due to severe limitations on the resources and capabilities of network nodes. In this paper we perform a comprehensive investigation of Key Agreement over resource constrained ad hoc networks. First, we formally model the key agreement problem over multi-hop ad hop networks, and we directly extend known key agreement protocols for wired networks, and evaluate the efficiency of such approaches. We then go beyond natural extensions of such protocols, by proposing non-trivial extensions based on efficient topology-driven simulations of logical networks over an arbitrary physical network, in order to optimize the most significant metrics of interest for such networks: i.e. bandwidth, latency, processing cost. Indeed, the resulting protocols are significantly more efficient in some or all of the above metrics, as our analytical results indicate.

REFERENCES

• 1: Michael Steiner , Gene Tsudik , Michael Waidner, Diffie-Hellman key distribution extended to group communication, Proceedings of the 3rd ACM conference on Computer and communications security, p.31-37, March 14-15, 1996, New Delhi, India [doi>10.1145/238168.238182]
• 2: W.Diffie, M.Hellman, New directions in cryptography, IEEE Transactions on Information Theory, 22 (1976), 644--654.
• 3: Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, August 1994
• 4: I. Ingemarsson, D. Tang, C. Wong. A Conference Key Distribution System. IEEE Transactions on Information Theory, 28(5):714--720, Sept. 1982
• 5: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 6: Mor Harchol-Balter , Tom Leighton , Daniel Lewin, Resource discovery in distributed networks, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.229-237, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301362]
• 7: Shay Kutten , David Peleg, Deterministic distributed resource discovery (brief announcement), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.336, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.362152]
• 8: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 9: C. Cheng , I. Cimet , S. Kumar, A protocol to maintain a minimum spanning tree in a dynamic topology, Symposium proceedings on Communications architectures and protocols, p.330-337, August 16-18, 1988, Stanford, California, United States
• 10: A. Mooij, W. Wesselink. A formal analysis of a dynamic distributed spanning tree algorithm. Computer Science TR 03-16, Technische Universiteit Eindhoven, Dec. 2003
• 11: Shlomi Dolev , Amos Israeli , Shlomo Moran, Self-stabilization of dynamic systems assuming only read/write atomicity, Distributed Computing, v.7 n.1, p.3-16, November 1993 [doi>10.1007/BF02278851]
• 12: L. Blin , F. Butelle, The First Approximated Distributed Algorithm for the Minimum Degree Spanning Tree Problem on General Graphs, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.161.1, April 22-26, 2003
• 13: F. Gärtner, A Survey of Self-Stabilizing Spanning-Tree Construction Algorithms, EPFL Technical Report, 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Modeling techniques

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Trees; Network problems

General Terms:
Algorithms, Design, Performance, Security

Keywords:
approximation algorithms, efficiency, group key agreement, optimization, performance evaluation, topology driven protocols