Summary:

As node connectivity to the Internet has plotted a trend of exponential growth over the past decade, the group interaction among these nodes this connectivity has allowed has also increased.  One such type of interaction is that of personal communication.  As such, several applications have developed in this space including email  and instant messaging services.  A logical extension to mere connectivity is secure connectivity, and this issue has become more important as the number of users and the relationships among the users of the Internet has changed.  Specifically, the trust model upon which operation was originally based no longer holds.  Thus, measures have been implemented to guarantee secure personal communication.  Unicast security, sufficient for email, implies encrypting/sending and receiving/decrypting infomation with a symmetric secret key, established either with out-of-band communication, or using a public-key infrastructure.  However, in a group setting establishing these shared secrets becomes more complex.  In the case of a instant message chat group, which implies a potentially dynamic and arbitrarily large membership and a multicast paradigm, establishing pair-wise shared secrets among all the members is very inefficient (N*(N-1) secret keys must be established).  There have been many proposals aimed at providing a group key management (GKM) architecture that will improve upon this "brute-force" attempt at secure connectivity in the multicast setting, some of which are summarized in the following sections.  In this project I shall implement using C one such architecture, a centralized key management scheme, with the specific goal of providing GKM for an IM-style chat group.  If time allows, I shall also implement a distributed key management variant and a simple chat application with which to test the implementation.

High-Level Implementation Requirements:

It is important that the sender of each message be authenticated, rather than just being able to determine that message came from a valid member.  Although this is not a strict requirement of a chat forum in general, a chat group implies a level of association which may make the desire for anonymity unlikely.   Additionally, individual identification becomes desireable merely to facilitate understanding of the chat flow.  Also, as a 'by-product' of the authentication technique, message integrity can also be assured. 

Forward and reverse secrecy of messages must be maintained.  This means a user who joins a group at time T must not be able to read any messages he captured sent to the group at t < T.  Similarly, a user who leaves or is forced from a group at time T' must not be able to read any messages she captures at t > T'.  More simply, a user must only be able to decode those messages that were sent to the group during the time she was a member of the group.  This implies that new keys must be distributed in some fashion every time the membership of a group changes.   In addition, it is good practice to periodically distribute new keys regardless of membership change to reduce the likelihood of keys being compromised.

Due to the autonomous nature of most chat groups (non-enterprise), it is also desireable to provide effective GKM without involving a third party.  In addition to the benefit of not having to trust an extra-group entity, chat groups are, in general, relatively short-lived (minutes or hours) and yet membership can by highly dynamic during its existence. This dynamism makes the prospect of handling the rekeying of the group through an external third party unattractive, due to the central point of failure it implies.  An entity offering such a service would likely be serving serveral groups concurrently.  Therefore, congestion would likely become a problem in the network infrastructure physically close to the third-party service node.  Thus, an intra-group controller is better suited for a chat group from both a trust viewpoint and a network throughput/latency viewpoint.

A Centralized, Tree-based Scheme:

The architecture I shall implement, described in [6], is well-suited to the requirements of a chat-group.  That is, it allows for tight control over the individual participants, via an invitation mechanism, and satisfies the aforementioned high-level implementation requirements.

Briefly, the GKM architecture I shall implement uses a general binary tree approach to manage group keys, though it is intuitive that an AVL tree (a tree in which the 'depth' of any two leaves differs by no more than 1) is optimal when one considers the computations necessary to rekey the tree, on average, when a member 'join' or 'leave' operation occurs.  A public key infrastructure (PKI) is assumed.  Although this necessarily implies third party interaction, the PKI is, depending on policy, at most invoked once during join events.  This is a far lower cost than using a "trusted" third party to handle group key management itself.  Reliable IP Mulicast is assumed, but a viable alternative in small to medium groups is a soft-state approach to implement reliability and multiple unicast transmissions.  The group collaboration scenario envisioned with this architecture is shown here [6].  The basic architecture components are described here [6]. The basic group operations are described here [6].

A Distributed, Tree-based Scheme:

An interesting distributed scheme can be found in [1].  It satisfies the high-level implementation requirements described above, but has the additional property that no group member has a special role, unlike the centralized scheme, which makes use of a Group Manager.  Although this distributed approach makes the implementation more complex, it is still efficient, with O(log N) complexity, where N is the number of group members.  This sheme is also uses a binary tree for key management and provides Diffie-Hellman authentication, using Gunther's idea of implicity-certified public keys as a more efficient alternative to the normal approach using verified CA (Certificate Authority) signatures.  Follow the links for imformation on notation [1] and rigorous descriptions of the Gunther's authentication scheme [1], key establishment [1], join [1] and leave [1] procedures.

Related Work [1,6]¹:

Previous work in secure group key communication protocols mainly focused on server-based systems [2, 10, 16, 17, 3, 8]. Early work on server-based schemes uses a central server, which shares a secret key with each member and uses unicast and encryption to communicate new keys securely with each member individually [7, 10]. To achieve scalability Mittra proposes a server hierarchy [10]. Wallner et. al. propose a key tree hierarchy [16], which is built by the central server and which makes key updates efficient by broadcasting a message of size$O(logN)$ where $N$ is the number of members. My approach uses a similar key tree hierarchy, but the key tree is generated by the members and no central server is necessary. Wong et al. extends the centrally managed key tree hierarchy to provide secure multicast service [17]. Chang et al. propose another method for efficient key update [3], which reduces the total number of keys in the group from $N$ (in key tree schemes) to $2log(N)$. Unfortunately this scheme is not robust against collusion attacks -- members can remain in the group (even after they were expelled) by exchanging their keys. A careful inspection of the protocol reveals that the keys of a leaving member are still used for subsequent group operation, which violates forward secrecy.

Protocols for smaller groups have not received as much attention as those for large groups. Since many chat groups can be expected to be small or medium-sized groups in practice (10s - 100s), efficient protocols for such groups are important. For such groups, it is possible to remove the requirement for a central server and construct collaborative group key authentication protocols.

In collaborative group key agreement protocols, Burmester and Desmedt describe star-based, tree-based, broadcast, and cyclic protocols for contributory group key agreement [2]. All protocols are variations on the Diffie-Hellman key exchange. They do not address the problems of dynamic groups, namely no ``join'' and ``leave'' operations are presented. In addition, the tree-based scheme uses a group ``chair'' which is at the root of the key hierarchy and is responsible to establish the common group key. In a fully distributed key management scheme the need for a trusted group chair can be eliminated, adding dynamic membership, and resolving practical implementation issues.

Ateniese et al. address dynamic membership issues [1]. Their system is also based on a variant of the Diffie-Hellman key agreement. The scheme, however, uses a group controller and needs $N$ protocol rounds to establish a common key in a group of $N$ members. The total bandwidth used is $O(N2)$. More efficient schemes have improved these bounds to $log(N)$ number of rounds and$O(N)$bandwidth requirements.

For dealing with the group key distribution in a large group with frequent membership changes, some good explorations have been done:

Spanning Trees
 [BD96] proposes the distribution of the key along a spanning tree generated between the members. It relies on trust in all members to forward the data without modification and does not handle group membership changes securely and efficiently.

Cliques
The approach proposed in [STW97] is to improve the capability of a system to distribute session keys in dynamic groups, but the solution does not scale well to large groups, since the group manager has to perfrom O(n) exponentiations for each group membership change and messages get prohibitively large.

Iolus
In Iolus[Mit97], a large group is decomposed into a number of subgroups, thus reducing the number of members affected by a key change due to membership changes. It relies on  relay nodes  performing admission control and packet rekeying. This not only requires full trust into these relays, but also increases the transmission delay, and does not handle relay failures gracefully.

Multicast Trees
Very recently we came across two schemes for multicast key distribution that are remarkably similar to our own tree-based approach. One is by D. Wallner, E. Harder, and R. Agee, from the National Security Agency, currently only available as an expired Internet draft. The other scheme, by C. Wong, M. Gouda, and S. Lam, from the University of Texas, is scheduled to appear in SIGCOMM 98.

[Personal Reference Notes]²

References:

[1] A. Perrig, "Efficient Collaborative Key Management Protocols for Secure Autonomous Group Communication", 1999.
[2] T. Dunigan and C. Cao, "Group Key Management", 1998.
[3] A. Ballardie, "Scalable Multicast Key Distribution", 1996.
[4] R. Canetti and B. Pinkas, "A Taxonomy of Multicast Security Issues", 1998.
[5] M. Waldvogel, G. Caronni, D. Sun, N. Weiler and B. Plattner, "The VersaKey Framework: Versatile Group Key Management", 1999.
[6] G. Caronni, M. Waldvogel, D. Sun and B. Plattner, "Efficient Security for Large and Dynamic Multicast Groups", 1998.
[7] I. Chang, R. Engel, D. Kandlur, D. Pendarakis and D. Saha, "Key Management for Secure Internet Multicast using Boolean Function Minimization Techniques", 1999.
[8] T. Hardjono, M. Baugher and H. Harney, "Group Security Association (GSA) Management in IP Multicast", 2000.
[9] O. Rodeh, K. Birman and D. Dolev, "Using AVL Trees for Fault Tolerant Group Key Management", 2000.
[10] B. Bhargava, S. B. Kamisetty and S. K. Madria, "Fault-tolerant Authentication and Group Key Management in Mobile Computing", 2000.
[11] SCIM, 2002.
[12] P-C Cheng, J. A. Garay, A. Herzberg and H. Krawczyk, "Design and Implementation of Modular Key Management Protocol and IP Secure Tunnel on AIX", 1995.