skip to main content
article

On the performance of group key agreement protocols

Published: 01 August 2004 Publication History

Abstract

Group key agreement is a fundamental building block for secure peer group communication systems. Several group key management techniques were proposed in the last decade, all assuming the existence of an underlying group communication infrastructure to provide reliable and ordered message delivery as well as group membership information. Despite analysis, implementation, and deployment of some of these techniques, the actual costs associated with group key management have been poorly understood so far. This resulted in an undesirable tendency: on the one hand, adopting suboptimal security for reliable group communication, while, on the other hand, constructing excessively costly group key management protocols.This paper presents a thorough performance evaluation of five notable distributed key management techniques (for collaborative peer groups) integrated with a reliable group communication system. An in-depth comparison and analysis of the five techniques is presented based on experimental results obtained in actual local- and wide-area networks. The extensive performance measurement experiments conducted for all methods offer insights into their scalability and practicality. Furthermore, our analysis of the experimental results highlights several observations that are not obvious from the theoretical analysis.

References

[1]
Amir, Y., Danilov, C., Miskin-Amir, M., Schultz, J., and Stanton, J. 2004. The Spread Toolkit: Architecture and Performance. Tech. rep., CNDS-2004-1, Johns Hopkins University.]]
[2]
Amir, Y., Dolev, D., Kramer, S., and Malki, D. 1992. Transis: A communication sub-system for high availability. In Digest of Papers, The 22nd International Symposium on Fault-Tolerant Computing Systems. 76--84.]]
[3]
Amir, Y., Kim, Y., Nita-Rotaru, C., Schultz, J., Stanton, J., and Tsudik, G. 2001. Exploring robustness in group key agreement. In The 21st IEEE International Conference on Distributed Computing Systems. IEEE Computer Society Press, 399--408.]]
[4]
Amir, Y., Kim, Y., Nita-Rotaru, C., Schultz, J., Stanton, J., and Tsudik, G. 2004. Secure group communication using robust contributory key agreement. IEEE Trans. Parallel and Distrib. Syst. 15, 5, 468--480.]]
[5]
Amir, Y., Kim, Y., Nita-Rotaru, C., and Tsudik, G. 2002. On the performance of group key agreement protocols (short paper). In The 22nd IEEE International Conference on Distributed Computing Systems. IEEE Computer Society Press.]]
[6]
Amir, Y., Moser, L. E., Melliar-Smith, P. M., Agarwal, D., and Ciarfella, P. 1995. The Totem single-ring ordering and membership protocol. ACM Trans. Comput. Syst. 13, 4 (Nov.), 311--342.]]
[7]
Amir, Y., Nita-Rotaru, C., Stanton, J., and Tsudik, G. 2003. Scaling secure group communication systems: Beyond peer-to-peer. In The 3rd DARPA Information Survivability Conference and Exposition (DISCEX III), Washington, D.C.]]
[8]
Amir, Y. and Stanton, J. 1998. The Spread wide area group communication system. Tech. rep., 98-4, Johns Hopkins University.]]
[9]
Anker, T., Chockler, G. V., Dolev, D., and Keidar, I. 1998. Scalable group membership services for novel applications. In Workshop on Networks in Distributed Computing.]]
[10]
Birman, K. P. and Joseph, T. 1987. Exploiting virtual synchrony in distributed systems. In The 11th Annual Symposium on Operating Systems Principles. 123--138.]]
[11]
Birman, K. P. and Renesse, R. V. 1994. Reliable Distributed Computing with the ISIS Toolkit. IEEE Computer Society Press.]]
[12]
Boneh, D. 1998. The decision Diffie-Hellman problem. In Third Algorithmic Number Theory Symposium. Lecture Notes in Computer Science, vol. 1423. Springer-Verlag, Berlin Germany, 48--63.]]
[13]
Boneh, D. 1999. Twenty years of attacks on the RSA cryptosystem. Not. Am. Math. Soc. (AMS) 46, 2, 203--213.]]
[14]
Bresson, E., Chevassut, O., and Pointcheval, D. 2001a. Provably authenticated group Diffie-Hellman key exchange---The dynamic case. In Asiacrypt 2001. Lecture Notes in Computer Science.]]
[15]
Bresson, E., Chevassut, O., Pointcheval, D., and Quisquater, J.-J. 2001b. Provably authenticated group Diffie-Hellman key exchange. In The 8th ACM Conference on Computer and Communications Security. ACM Press.]]
[16]
Burmester, M. and Desmedt, Y. 1994. A secure and efficient conference key distribution system. Advances in Cryptology---EUROCRYPT'94.]]
[17]
Caronni, G., Waldvogel, M., Sun, D., Weiler, N., and Plattner, B. 1999. The VersaKey framework: Versatile group key management. IEEE J. Select. Areas Commun. 17, 9 (Sep.).]]
[18]
Diffie, W. and Hellman, M. E. 1976. New directions in cryptography. IEEE Trans. Inform. Theory IT-22, 644--654.]]
[19]
Fekete, A., Lynch, N., and Shvartsman, A. 1997. Specifying and using a partitionable group communication service. In The 16th ACM Symposium on Principles of Distributed Computing, Santa Barbara, CA. 53--62.]]
[20]
Floyd, S., Jacobson, V., Liu, C., McCanne, S., and Zhang, L. 1997. A reliable multicast framework for light-weight sessions and application level framing. IEEE/ACM Trans. Netw. 5, 6 (Dec.), 784--803.]]
[21]
Gong, L. 1997. Enclaves: Enabling secure collaboration over the Internet. IEEE J. Select. Areas Commun. 15, 3 (Apr.), 567--575.]]
[22]
Harney, H., Colegrove, A., and McDaniel, P. 2001. Principles of policy in secure groups. In Network and Distributed Systems Security Symposium.]]
[23]
Hiltunen, M. A. and Schlichting, R. D. 1996. Adaptive distributed and fault-tolerant systems. Int. J. Comput. Syst. Sci. Engng. 11, 5 (Sep.), 125--133.]]
[24]
Hiltunen, M. A., Schlichting, R. D., and Ugarte, C. 2001. Enhancing survivability of security services using redundancy. In International Conference on Dependable Systems and Networks.]]
[25]
Katz, J. and Yung, M. 2003. Scalable protocols for authenticated group key exchange. Advances in Cryptology---CRYPTO'03.]]
[26]
Keidar, I., Marzullo, K., Sussman, J., and Dolev, D. 2000. A client-server oriented algorithm for virtually synchronous group membership in WANs. In The 20th International Conference on Distributed Computing Systems. 356--365.]]
[27]
Kihlstrom, K. P., Moser, L. E., and Melliar-Smith, P. M. 1998. The SecureRing protocols for securing group communication. In The 31st Hawaii International Conference on System Sciences, Vol. 3. Kona, Hawaii, 317--326.]]
[28]
Kim, Y. 2002. Group Key Agreement---Theory and Practice. Ph.D. thesis, Department of Computer Science, University of Southern California.]]
[29]
Kim, Y., Perrig, A., and Tsudik, G. 2000. Simple and fault-tolerant key agreement for dynamic collaborative groups. In The 7th ACM Conference on Computer and Communications Security. ACM Press, 235--244.]]
[30]
Kim, Y., Perrig, A., and Tsudik, G. 2001. Communication-efficient group key agreement. In IFIP SEC 2001.]]
[31]
Kim, Y., Perrig, A., and Tsudik, G. 2004a. Group key agreement efficient in communication. IEEE Trans. Comput. 33, 7.]]
[32]
Kim, Y., Perrig, A., and Tsudik, G. 2004b. Tree-based group key agreement. ACM Trans. Inf. Syst. Secur. 7, 1.]]
[33]
McDaniel, P., Prakash, A., and Honeyman, P. 1999. Antigone: A flexible framework for secure group communication. In The 8th USENIX Security Symposium. 99--114.]]
[34]
Menezes, A., van Oorschot, P., and Vanstone, S. 1996. Handbook of Applied Cryptography. CRC Press.]]
[35]
Moser, L. E., Amir, Y., Melliar-Smith, P. M., and Agarwal, D. A. 1994. Extended virtual synchrony. In The 14th International Conference on Distributed Computing Systems. IEEE Computer Society Press, Los Alamitos, CA, 56--65.]]
[36]
National Institute for Standards and Technology (NIST). 2000. Digital Signature Standard (DSS). Number FIPS 186-2. National Institute for Standards and Technology (NIST). http://csrc.nist.gov/publications/fips/fips186-2/fips186-2.pdf.]]
[37]
Nita-Rotaru, C. 2003. High Performance Secure Group Communication. Ph.D. thesis, Department of Computer Science, Johns Hopkins University.]]
[38]
OpenSSL Project team. 1999. OpenSSL. http://www.OpenSSL.org/.]]
[39]
Reiter, M. K. 1994. Secure agreement protocols: reliable and atomic group multicast in RAMPART. In The 2nd ACM Conference on Computer and Communications Security. 68--80.]]
[40]
Renesse, R. V., Birman, K., and Maffeis, S. 1996. Horus: A flexible group communication system. Commun. ACM 39, 76--83.]]
[41]
Rivest, R. L., Shamir, A., and Adleman, L. M. 1978. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 2 (Feb.), 120--126.]]
[42]
Rodeh, O., Birman, K., and Dolev, D. 2001. The architecture and performance of security protocols in the Ensemble Group Communication System. ACM Trans. Inf. Syst. Secur. 4, 3 (Aug.), 289--319.]]
[43]
Rodeh, O., Birman, K., and Dolev, D. 2002. Using AVL trees for fault tolerant group key management. Int. J. Inf. Secur. 1, 2 (Feb.).]]
[44]
Schultz, J. 2001. Partitionable Virtual Synchrony using Extended Virtual Synchrony. M.S. thesis, Department of Computer Science, Johns Hopkins University.]]
[45]
Setia, S., Koussih, S., Jajodia, S., and Harder, E. 2000. Kronos: A scalable group re-keying approach for secure multicast. In The 2000 IEEE Symposium on Security and Privacy. IEEE, 215--218. Oakland, CA.]]
[46]
Sherman, A. T. and McGrew, D. A. 2003. Key establishment in large dynamic groups using one-way function trees. IEEE Trans. Softw. Engng. 444--458.]]
[47]
Steer, D., Strawczynski, L., Diffie, W., and Wiener, M. 1990. A secure audio teleconference system. Advances in Cryptology---CRYPTO'88.]]
[48]
Steiner, M., Tsudik, G., and Waidner, M. 2000. Key agreement in dynamic peer groups. IEEE Trans. Parallel Distrib. Syst.]]
[49]
Tzeng, W.-G. and Tzeng, Z.-J. 2000. Round-efficient conference-key agreement protocols with provable security. In Advances in Cryptology---ASIACRYPT '2000. Lecture Notes in Computer Science. Springer-Verlag, Kyoto, Japan.]]
[50]
Wallner, D., Harder, E., and Agee, R. 1999. Key management for multicast: Issues and architectures. RFC 2627.]]
[51]
Whetten, B., Montgomery, T., and Kaplan, S. 1994. A high performance totally ordered multicast protocol. In Theory and Practice in Distributed Systems, International Workshop. Lecture Notes in Computer Science, vol. 938.]]
[52]
Wong, C. K., Gouda, M. G., and Lam, S. S. 2000. Secure group communications using key graphs. Trans. Netw. 8, 1, 16--30.]]

Cited By

View all
  • (2024)Scalable and Secure Key Agreement Protocols for Dynamic GroupsEssential Information Systems Service Management10.4018/979-8-3693-4227-5.ch011(279-310)Online publication date: 20-Sep-2024
  • (2024)Network impact analysis on the performance of Secure Group Communication schemes with focus on IoTDiscover Data10.1007/s44248-024-00015-12:1Online publication date: 17-Sep-2024
  • (2022)An Experience Report on the Suitability of a Distributed Group Encryption Scheme for an IoT Use Case2022 IEEE 95th Vehicular Technology Conference: (VTC2022-Spring)10.1109/VTC2022-Spring54318.2022.9860762(1-7)Online publication date: Jun-2022
  • Show More Cited By

Recommendations

Reviews

Andrew Robert Huber

"In practice, the actual costs of group key management cannot be trivially extrapolated from the theoretical analysis." This is the most important statement in this thorough performance analysis. Five group key management protocols are described, analyzed, and compared: group Diffie-Hellman (GDH), centralized key distribution (CKD), tree-based GDH (TGDH), an imbalanced tree version of TGDH called skinny tree (STR), and Burmester and Desmedt (BD). A theoretical analysis compares the computation costs (exponentiations, signatures, and verifications) and communication costs (numbers and types of messages) of four operations: a single member joining or leaving the group, and multiple member merges and partitions. The actual times of these operations for the five algorithms were measured on a local area network (LAN) for group sizes of up to 50 members. Graphs show join and leave results for 512 and 1024 bit keys, and merge and partition results for 1024 bit keys. To show how communication costs matter in practice, join and leave results are also shown for a wide area network (WAN). It would have been interesting to see results for larger key sizes. Since the protocols differ in trading off computation versus communication, no one protocol is always best. TGDH is shown to be the best single protocol overall, though the authors discuss several common application classes where other algorithms are better. They also demonstrate why, with real systems, theoretical analysis alone is insufficient. This is excellent work, reported well. Both theoretical computer scientists and practicing software developers can appreciate this work, and both should emulate it. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Information and System Security
ACM Transactions on Information and System Security  Volume 7, Issue 3
August 2004
156 pages
ISSN:1094-9224
EISSN:1557-7406
DOI:10.1145/1015040
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2004
Published in TISSEC Volume 7, Issue 3

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Group Communication
  2. Group Key Management
  3. Peer Groups
  4. Secure Communication

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)34
  • Downloads (Last 6 weeks)8
Reflects downloads up to 19 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Scalable and Secure Key Agreement Protocols for Dynamic GroupsEssential Information Systems Service Management10.4018/979-8-3693-4227-5.ch011(279-310)Online publication date: 20-Sep-2024
  • (2024)Network impact analysis on the performance of Secure Group Communication schemes with focus on IoTDiscover Data10.1007/s44248-024-00015-12:1Online publication date: 17-Sep-2024
  • (2022)An Experience Report on the Suitability of a Distributed Group Encryption Scheme for an IoT Use Case2022 IEEE 95th Vehicular Technology Conference: (VTC2022-Spring)10.1109/VTC2022-Spring54318.2022.9860762(1-7)Online publication date: Jun-2022
  • (2022)Secure lightweight multi‐party key agreement based on hyperelliptic curve Diffie–Hellman for constraint networksConcurrency and Computation: Practice and Experience10.1002/cpe.692134:13Online publication date: 12-Mar-2022
  • (2021)Towards a Group Encryption Scheme Benchmark: A View on Centralized Schemes with Focus on IoTProceedings of the ACM/SPEC International Conference on Performance Engineering10.1145/3427921.3450252(233-240)Online publication date: 9-Apr-2021
  • (2021)Multi-tier security for cloud environment by HECDSA with IBEM2021 5th International Conference on Computing Methodologies and Communication (ICCMC)10.1109/ICCMC51019.2021.9418428(10-16)Online publication date: 8-Apr-2021
  • (2020)Design of group key agreement protocol using neural key synchronizationJournal of Interdisciplinary Mathematics10.1080/09720502.2020.173195623:2(435-451)Online publication date: 12-May-2020
  • (2020)Tree and elliptic curve based efficient and secure group key agreement protocolJournal of Information Security and Applications10.1016/j.jisa.2020.10259955(102599)Online publication date: Dec-2020
  • (2020)Research on Self-Adaptive Group Key Management in Deep Space NetworksWireless Personal Communications10.1007/s11277-020-07540-7Online publication date: 7-Jun-2020
  • (2019)Analytical Models for the Scalability of Dynamic Group-key Agreement Protocols and Secure File Sharing SystemsACM Transactions on Privacy and Security10.1145/334299822:4(1-36)Online publication date: 25-Sep-2019
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media