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
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.
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):
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.
- CKD: we implemented the 'vanilla' cases for evaluation purposes.
- BD : we designed and implemented a robust protocol based on the
- TGDH: we finished the design of a robust protocol based on TGDH
and we implemented the 'vanilla' cases for performance
- STR: we finished the design of a robust protocol based on STR and
we implemented the 'vanilla' cases for performance evaluation
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
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 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.
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
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
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
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 (
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.
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.
We released Spread 3.13 in August 2000. The main new features of this
- 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
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