Secure group communications using key graphs

ABSTRACT

Many emerging applications (e.g., teleconference, real-time information services, pay per view, distributed interactive simulation, and collaborative work) are based upon a group communications model, i.e., they require packet delivery from one or more authorized senders to a very large number of authorized receivers. As a result, securing group communications (i.e., providing confidentiality, integrity, and authenticity of messages delivered between group members) will become a critical networking issue.In this paper, we present a novel solution to the scalability problem of group/multicast key management. We formalize the notion of a secure group as a triple (U,K,R) where U denotes a set of users, K a set of keys held by the users, and R a user-key relation. We then introduce key graphs to specify secure groups. For a special class of key graphs, we present three strategies for securely distributing rekey messages after a join/leave, and specify protocols for joining and leaving a secure group. The rekeying strategies and join/leave protocols are implemented in a prototype group key server we have built. We present measurement results from experiments and discuss performance comparisons. We show that our group key management service, using any of the three rekeying strategies, is scalable to large groups with frequent joins and leaves. In particular, the average measured processing time per join/leave increases linearly with the logarithm of group size.

REFERENCES

• 1: Tony Ballardie. Scalable Multicast Key Distribution, RFC 19~9, May 1996.
• 2: T. Ballardie , J. Crowcroft, Multicast-specific security threats and counter-measures, Proceedings of the 1995 Symposium on Network and Distributed System Security (SNDSS'95), p.2, February 16-17, 1995
• 3: Shimshon Berkovits. How to Broadcast a Secret. In D.W. Davies, editor, Advances in cryptology, EURO- CRYPT '91, volume 547 of Lecture Notes in Computer Science, pages 535-541. Springer Verlag, 1991.
• 4: Ray Bird , Inder Gopal , Amir Herzberg , Phil Janson , Shay Kutten , Refik Molva , Moti Yung, The KryptoKnight family of light-weight protocols for authentication and key distribution, IEEE/ACM Transactions on Networking (TON), v.3 n.1, p.31-41, Feb. 1995 [doi>10.1109/90.365435]
• 5: Guang-huei Chiou , Wen-Tsuen Chen, Secure Broadcasting Using the Secure Lock, IEEE Transactions on Software Engineering, v.15 n.8, p.929-934, August 1989 [doi>10.1109/32.31350]
• 6: S. E. Deering, Multicast routing in internetworks and extended LANs, Symposium proceedings on Communications architectures and protocols, p.55-64, August 16-18, 1988, Stanford, California, United States
• 7: Amos Fiat , Moni Naor, Broadcast encryption, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.480-491, January 1994, Santa Barbara, California, United States
• 8: Li Gong. Enclaves: Enabling Secure Collaboration over the Internet. IEEE Journal on Selected Areas in Communications, pages 567-575, April 1997.
• 9: H. Harney and C. Muckenhirn. Group Key Management Protocol {CKMP) Architecture, RFC 209J, July 1997.
• 10: H. Harney and C. Muckenhirn. Croup Key Management Protocol (GKMP) Specification, RFC 2093, July 1997.
• 11: J. B. Lacy, D. P. Mitchell, and W. M. Schell. CryptoLib: cryptography in software. In Proceedings of USENIX: .~th UNIX Security Symposium, October 1993.
• 12: Simon S. Lain and Chung Kei Wong. Keystone: A Group Key Management Service. Work in progress, Department of Computer Sciences, The University of Texas at Austin.
• 13: B. N. Levine , J. J. Garcia-Luna-Aceves, Improving Internet multicast with routing labels, Proceedings of the 1997 International Conference on Network Protocols (ICNP '97), p.241, October 28-31, 1997
• 14: Ralph C. Merkle, A certified digital signature, Proceedings on Advances in cryptology, p.218-238, July 1989, Santa Barbara, California, United States
• 15: Suvo Mittra, Iolus: a framework for scalable secure multicasting, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, September 14-18, 1997, Cannes, France
• 16: B. Clifford Neuman. Proxy-Based Authorization and Accounting for Distributed Systems. In Proceedings of 13th International Conference on Distributed Computing Systems, pages 283-291, May 1993.
• 17: Jennifer G. Steiner, Clifford Neuman, and Jeffrey I. Schiller. Kerberos: An Authentication Service for Open Network Systems. In USENIX Winter Conference, pages 191-202, February 1988.
• 18: Doug R. Stinson, On Some Methods for Unconditionally Secure Key Distributionand Broadcast Encryption, Designs, Codes and Cryptography, v.12 n.3, p.215-243, Nov. 1997 [doi>10.1023/A:1008268610932]
• 19: J.J. Tardo and K. Alagappan. SPX: Global authentication using public key certificates. In Proceedings of 12th IEEE Symposium on Research in Security and Privacy, pages 232-244, May 1991.
• 20: Debby M. Wallner, Eric J. Harder, and Ryan C. Agee. Key Management for Multicast: Issues and Architectures. Working draft, National Security Agency, July 1997.
• 21: Chung K Wong , Mohamed G. Gouda , Simon S. Lam, Secure Group Communications Using Key Graphs, University of Texas at Austin, Austin, TX, 1997
• 22: Thomas Y.C. Woo, Raghuram Bindignavle, Shaowen Su, and Simon S. Lam. SNP: An interface for secure network programming. In Proceedings of USENIX'9.~ Summer Technical Conference, June 1994.
• 23: Thomas Y.C. Woo and Simon S. Lain. Designing a Distributed Authorization Service. In Proceedings IEEE INFOCOM '98, San Francisco, March 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
  C.5 COMPUTER SYSTEM IMPLEMENTATION

General Terms:
Design, Security