Distributed collaborative key agreement and authentication protocols for dynamic peer groups

ABSTRACT

We consider several distributed collaborative key agreement and authentication protocols for dynamic peer groups. There are several important characteristics which make this problem different from traditional secure group communication. They are: 1) distributed nature in which there is no centralized key server; 2) collaborative nature in which the group key is contributory (i.e., each group member will collaboratively contribute its part to the global group key); and 3) dynamic nature in which existing members may leave the group while new members may join. Instead of performing individual rekeying operations, i.e., recomputing the group key after every join or leave request, we discuss an interval-based approach of rekeying. We consider three interval-based distributed rekeying algorithms, or interval-based algorithms for short, for updating the group key: 1) the Rebuild algorithm; 2) the Batch algorithm; and 3) the Queue-batch algorithm. Performance of these three interval-based algorithms under different settings, such as different join and leave probabilities, is analyzed. We show that the interval-based algorithms significantly outperform the individual rekeying approach and that the Queue-batch algorithm performs the best among the three interval-based algorithms. More importantly, the Queue-batch algorithm can substantially reduce the computation and communication workload in a highly dynamic environment. We further enhance the interval-based algorithms in two aspects: authentication and implementation. Authentication focuses on the security improvement, while implementation realizes the interval-based algorithms in real network settings. Our work provides a fundamental understanding about establishing a group key via a distributed and collaborative approach for a dynamic peer group.

REFERENCES

• 1: Yair Amir , Yongdae Kim , Cristina Nita-Rotaru , John L. Schultz , Jonathan Stanton , Gene Tsudik, Secure Group Communication Using Robust Contributory Key Agreement, IEEE Transactions on Parallel and Distributed Systems, v.15 n.5, p.468-480, May 2004 [doi>10.1109/TPDS.2004.1278104]
• 2: [2] Y. Amir and J. Stanton, The Spread Wide Area Group Communication System. Johns Hopkins Univ., Baltimore, MD, CNDS-98-4, 1998.
• 3: Giuseppe Ateniese , Michael Steiner , Gene Tsudik, Authenticated group key agreement and friends, Proceedings of the 5th ACM conference on Computer and communications security, p.17-26, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288097]
• 4: Simon Blake-Wilson , Alfred Menezes, Authenticated Diffie-Hellman Key Agreement Protocols, Proceedings of the Selected Areas in Cryptography, p.339-361, August 17-18, 1998
• 5: [5] M. Burmester and Y. Desmedt, "A secure and efficient conference key distribution system," in Proc. Advances in Cryptology-EUROCRYPT'94 , 1995, vol. LNCS 950, pp. 275-286.
• 6: [6] W. Diffie and M. Hellman, "New directions in cryptography," IEEE Trans. Inf. Theory, vol. 22, no. 6, pp. 644-654, 1976.
• 7: Alan Fekete , Nancy Lynch , Alex Shvartsman, Specifying and using a partitionable group communication service, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.53-62, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259422]
• 8: Christoph G. Günther, An identity-based key-exchange protocol, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.29-37, November 1990, Houthalen, Belgium
• 9: Mike Just , Serge Vaudenay, Authenticated Multi-Party Key Agreement, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.36-49, November 03-07, 1996
• 10: Yongdae Kim , Adrian Perrig , Gene Tsudik, Communication-Efficient Group Key Agreement, Proceedings of the IFIP TC11 Sixteenth Annual Working Conference on Information Security: Trusted Information: The New Decade Challenge, p.229-244, June 11-13, 2001
• 11: Yongdae Kim , Adrian Perrig , Gene Tsudik, Tree-based group key agreement, ACM Transactions on Information and System Security (TISSEC), v.7 n.1, p.60-96, February 2004 [doi>10.1145/984334.984337]
• 12: [12] P. P. C. Lee, "Distributed and collaborative key agreement protocols with authentication and implementation for dynamic peer groups," M.Phil. thesis, The Chinese University of Hong Kong, Jun. 2003.
• 13: [13] P. P. C. Lee, J. C. S. Lui, and D. K. Y. Yau, Distributed collaborative key agreement and authentication protocols for dynamic peer groups The Chinese University of Hong Kong, CS&E Tech. Rep., Jul. 2005.
• 14: Xiaozhou Steve Li , Yang Richard Yang , Mohamed G. Gouda , Simon S. Lam, Batch rekeying for secure group communications, Proceedings of the 10th international conference on World Wide Web, p.525-534, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372153]
• 15: [15] A. Perrig, "Efficient collaborative key management protocols for secure autonomous group communication," in Int. Workshop on Cryptographic Techniques and E-Commerce (CrypTEC '99), Jul. 1999, pp. 192-202.
• 16: Sanjeev Setia , Samir Koussih , Sushil Jajodia , Eric Harder, Kronos: A Scalable Group Re-Keying Approach for Secure Multicast, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.215, May 14-17, 2000
• 17: Alan T. Sherman , David A. McGrew, Key Establishment in Large Dynamic Groups Using One-Way Function Trees, IEEE Transactions on Software Engineering, v.29 n.5, p.444-458, May 2003 [doi>10.1109/TSE.2003.1199073]
• 18: Boyeon Song , Kwangjo Kim, Two-Pass Authenticated Key Arrangement Protocol with Key Confirmation, Proceedings of the First International Conference on Progress in Cryptology, p.237-249, December 10-13, 2000
• 19: Michael Steiner , Gene Tsudik , Michael Waidner, Key Agreement in Dynamic Peer Groups, IEEE Transactions on Parallel and Distributed Systems, v.11 n.8, p.769-780, August 2000 [doi>10.1109/71.877936]
• 20: [20] M. Waldvogel, G. Caronni, D. Sun, N. Weiler, and B. Plattner, "The versakey framework: versatile group key management," IEEE J. Sel. Areas Commun., vol. 17, no. 9, pp. 1614-1631, Sep. 1999.
• 21: D. Wallner , E. Harder , R. Agee, Key Management for Multicast: Issues and Architectures, RFC Editor, 1999
• 22: Chung Kei Wong , Mohamed Gouda , Simon S. Lam, Secure group communications using key graphs, IEEE/ACM Transactions on Networking (TON), v.8 n.1, p.16-30, Feb. 2000 [doi>10.1109/90.836475]
• 23: Yang Richard Yang , X. Steve Li , X. Brian Zhang , Simon S. Lam, Reliable group rekeying: a performance analysis, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.27-38, August 2001, San Diego, California, United States

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.2.3 Network Operations

  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

  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:
Design, Management, Security

Keywords:
authentication, dynamic peer groups, group key agreement, rekeying, secure group communication, security