High Performance, Robust and Secure Group Communication

About us
Technology Transfer
Secure Spread

Yearly Technical Report, July 2001


A practical group communication system should provide secure multicast services for peer groups over local and wide area networks. To support the environment described in the Dynamic Coalition program, such a system should scale to tens of coalition parties, with hundreds of servers, supporting thousands of users. This service is crucial for building distributed applications that work in dynamic environments and communicate over unsecured networks (e.g. the Internet). It is also important for enabling other infrastructures for these environments, such as replicated certification, highly available policy management, and high performance access control.

A common claim today is that a wide-area, secure group communication system with strict reliability semantics and strict security requirements, cannot perform well enough to be practical. Based on our past and current work, we claim that with careful protocol design, a system that is limited to the size of the above peer groups can perform well without relaxing any of the security or reliability guarantees. The objective of this project is to build it.


Our research plan calls for the concurrent development of two architectures. The layered architecture layers our security mechanisms on top of the guarantees of the group communication system. This significantly simplifies the design and allows us to experiment with different approaches quickly. This work translates to a client library we call Secure Spread.

The integrated architecture integrates the security mechanisms into the group communication system. This approach is much more scalable as it dramatically amortizes the cost of providing security so that costly operations only happen when the network connectivity changes and not as a result of client-initiated actions. The tradeoff is in an increased development complexity. This work translates to versions of the Spread toolkit that come with built-in security. The rational behind this two-tracks approach is that it allows us to experiments with many protocols before we decide what to include (for a heavy development price) inside the group communication toolkit.

Layered architecture

We started by implementing Secure Spread 0.0.3, providing a key agreement protocol based on the CLIQUES Group Diffie-Helman (GDH) algorithm. The protocol did not support cascaded failures. This first version was released at November 2000.

We then worked on providing a fault-tolerant protocol. We designed the first robust contributory key agreement protocol based on CLIQUES GDH and proved its correctness. This robust protocol formed the core of Secure Spread 1.0.0, a version we released at March 2001. A technical report presenting two robust algorithms and their corectness is available below. This work was presented at the 2001 IEEE International Conference on Distributed Computing Systems held in Phoenix, Arizona during April.

We have also finalized the design of a new robust Tree-based Group Diffie-Helman algorithm. The primitives that allow building the protocol were implemented within the CLIQUES TGDH library. A paper describing this work was presented at the 2000 ACM Conference on Computer and Communications Security (CCS-8) held in Philadelphia, Pennsylvania during November.

A new group key agreement method (STR), based on a protocol originally proposed by Steer et al. at Crypto88, was specified and implemented as part of the CLIQUES STR library. This work was presented at IFIP-SEC 2001 in June.

We created a unified framework in Secure Spread that enabled us to evaluate and compare the different key agreement algorithms side by side, namely, Centralized Key Distribution (CKD), CLIQUES Group Diffie Helman (GDH), Tree-based Group Diffie Helman (TGDH), Burmester-Desmedt (BD), and STR.

We worked on designing and integrating with Secure Spread four more key agreement protocols (in addition to GDH):

  1. CKD: we implemented the 'vanilla' cases for evaluation purposes.
  2. BD : we designed and implemented a robust protocol based on the BD algorithm.
  3. TGDH: we finished the design of a robust protocol based on TGDH and we implemented the 'vanilla' cases for performance evaluation purposes.
  4. STR: we finished the design of a robust protocol based on STR and we implemented the 'vanilla' cases for performance evaluation purposes.
Preliminary results on the performance evaluation of above five key agreement protocols were presented in the Dynamic Coalition PI Meeting at Colarado Springs USA in July. We plan to make these protocols available in our next release of Secure Spread.

Integrated architecture

We integrated a global flow control algorithm for multi-sender multi-group multicast in wide area overlay networks. This is a very important step toward practical high performance wide area group communication.

We defined the necessary services for practical secure group communication in particular and for overlay networks in general. We looked beyond the key agreement protocols into authentication and access control mechanisms.

We completed the initial design of a framework for access control in group communication systems. This framework specifies a modular architecture allowing multiple access control and authentication protocols to be used and the location of checks in the group communication system to enforce the policies.

The access control and authentication framework adds two new features to the Spread group communication system. First, it provides a modular API that allows anyone to write a custom authentication and access control policy code module which will be loaded into the Spread daemon. This module (or modules) will control how clients are authenticated when they connect to the daemon and what restrictions should be enforced on the clients' actions (such as joining groups or sending messages). Second, it inserts appropriate checks into Spread to enforce whatever access control policy the user has enabled.

We implemented the framework in the Spread Group Communication System version 3.16. A technical report describing the architecture along with some examples of authentication methods that are supported by the framework is available. This work will be presented in the Third International Workshop on Networked Group Communications at London, UK in November.

Current Plan:

Our plan for FY 2002 includes the following:
  • Explore and analyze the difficulties in dynamic control and reconfiguration of group communication systems. Begin the design of efficient and correct protocols for this environment.
  • Work with several other Dynamic Coalition groups to evaluate which software components would be suitable to integrate with Secure Spread.
  • The initial implementation of an Integrated architecture: The implementation will include fault-tolerant protocols that implement shared keys, optimized per-group keys, and use the keys to provide core security services. The focus of this work will be a prototype upon which performance and correctness evaluation can be done, including a comparison with the layered architecture.
  • The research of new group trust models and an API: Development of the algorithms that compute the overall trust of a group based on individual members' respect for other members. Design of an API that exports the individual and group trust status.
  • The release of a new Secure Spread library, the second release based on the new architecture and protocols developed in this project.


Framework for Authentication and Access Control of Client-Server Group Communication Systems
ps, ps.gz, pdf. To be published in the Proceedings of the Third International Workshop on Networked Group Communications, London, United Kingdom, November 7-9, 2001. A longer version is available as CNDS Technical Report 2001-2 ( ps, ps.gz, pdf. ).

Yair Amir, Cristina Nita-Rotaru, and Jonathan Stanton

In this paper we present a framework for integrating authentication and access control mechanisms and policies into a group communication system.

Exploring Robusteness in Group Key Agreement
ps, ps.gz, pdf. Published in Proceedings of the 21th IEEE International Conference on Distributed Computing Systems, Phoenix, Arizona, April 16-19, 2001, pp 399-408. An extended version is available as CNDS Technical Report CNDS 2000-4 ( ps, ps.gz, pdf. ).

Yair Amir, Yongdae Kim, Cristina Nita-Rotaru, John Schultz, Jonathan Stanton, and Gene Tsudik

In this paper we present two robust contributory key agreement protocols which are resilient to any sequence of events while preserving the group communication membership and ordering guarantees.

Communication-Efficient Group Key Agreement

To be published in IFIP -SEC 2001, June 2001.

Yongdae Kim, Gene Tsudik and Adrian Perrig

Most prior research in group key management focused on minimizing computational overhead stemming from expensive cryptographic operations whereas bandwidth and communication round complexity was of secondary concern. However, recent advances in computation have resulted in the network delay in wide area networks (WANs) being the primary cost factor in the performance of group key management protocols. In this paper, we reconsider a group key agreement protocol previously proposed by Steer, et al. in 1988. We extend it to handle dynamic groups and network faults such as topology partitions and merges. The resulting protocol suite is simple, provably secure, fault-tolerant, and particularly well-suited for applications in high-delay WANs.

The Cost of Adding Security Services to Group Communication Systems
ps, ps.gz, pdf. Technical Report CNDS-2000-3.

Cristina Nita-Rotaru

In this paper we present Secure Spread, a secure version of the Spread Toolkit. Secure Spread is a group communication system that utilizes contributory group key management developed by the Cliques project and Blowfish symmetric encryption algorithm.


We released Spread 3.13 in August 2000. The main new features of this version included:

  • Scalability improvements in the number of groups in the system. The lightweight group management is now using probablistic algorithms that reduce group lookups to complexity of o(log(n)) down from o(n). This allows us to support tens of thousands of groups without noticeable performance penalty. Our system is still limited to about 1000 groups due to state transfer implementation limitation.
  • Performance improvements for small messages (by a factor of 4 or so).
  • A new configuration format that allows improved run time configuration.

We released Secure Spread Beta 0 in November 2000. This is a preliminary version which includes a fairly stable API and a correct implementation of the CLIQUES GDH key agreement protocol. Secure Spread beta 0 supports simple group events and failure scenarios. No cascading failures are supported. This version is available for other researchers to use. It works with Spread 3.12, 3.13 and 3.14.

We released Secure Spread Version 1.0 in March 2001. This version included a complete robust CLIQUES GDH protocol and a stable API for establishing secure groups and sending and receiving encrypted messages. This version is available and works with Spread 3.12, 3.13, 3.14, and 3.16.0.

We have released Spread 3.14 (October 31, 2000), 3.15.0 (December 20, 2000), 3.15.1 (February 26, 2001), and 3.15.2 (March 20, 2001) during this period. These releases address stability issues discovered by the growing community of Spread users.

A release of Spread, 3.16.0 (June 25, 2001), that includes a preliminary version of an integrated authentication and access control enforcement framework.

Technology Transfer:

We know of one Dynamic Coaltions project that already uses our software: This is the Efficient and Scalable Infrastructure Support project done at Johns Hopkins and Brown, which aims to provide scalable certification service. We are exploring potential collaboration with other projects in the program.

During the period Spread was integrated into the beta version of OpenLinux. It was released in the next OpenLinux version in June.

A Spread Workshop was held over three days at Johns Hopkins University in June 2001. This meeting included people from academia and industry and involved presentations, demos, and a collaborative discussion of future features, current needs and problems, and solutions.

Questions or comments to:
webmaster (at) dsn.jhu.edu
TEL: (410) 516-5562
FAX: (410) 516-6134
Distributed Systems and Networks Lab
Computer Science Department
Johns Hopkins University
3400 N. Charles Street Baltimore, MD 21218-2686