VersaKey — Versatile Key Management for Large and Dynamic Groups

Middleware supporting secure applications in a distributed environment faces several challenges. Scalable security in the context of multicasting or broadcasting is especially hard when privacy and authenticity is to be assured to highly dynamic groups where the application allows participants to join and leave at any time.

Unicast security is well-known and has widely advanced into production state. But proposals for multicast security solutions that have been published so far are complex, often require trust in network components or are inefficient. In this paper, we propose a framework of new approaches for achieving scalable security in IP multicasting. Our solutions assure that that newly joining members are not able to understand past group traffic, and that leaving members may not follow future communication.

For versatility, our framework supports a range of closely related schemes for key management, ranging from tightly centralized to fully distributed and even allows switching between these schemes on-the-fly with low overhead. Operations have low complexity (O(log N) for joins or leaves), thus granting scalability even for very large groups. We also introduce a novel concurrency-enabling scheme, which was devised for fully distributed key management.

As part of the project, we evaluate the requirements for secure multicasting, design and implement our flexible system, and evaluate its properties, based on the existing prototype implementation.

Architecture

As part of our work on VersaKey, we co-invented the now popular use of key hierarchies for secure group communications (unlike other approaches, VersaKey does not require the broadcast of new keying material when a new member joins).

Since then, one of the main advantages of VersaKey has become its versatility. namely, that it can work both in presence of a central controller (such as used e.g. in pay-per-view applications) as well as fully collaborative environments.

VersaKey's three distinct modes each provide for their unique advantages depending on its use and context. Nevertheless, it is also possible to switch between modes at run-time. For example, if the central controller should fail or become unreachable, the remaining nodes can reorganize themselves for distributed operation, if not prohibited through system policy.

Concurrency

When using a distributed approach for managing large and dynamic groups, changes to group membership may happen quite frequently. Multiple membership changes can be initiated by different members faster than the propagation delay of the network, i.e., concurrently.

It turns out that in distributed VersaKey, concurrency can be achieved without synchronization or locking. This method, dubbed the method Continuous Consistency Protocol (CCP), is outlined in the three-part image to the right and described below in simple terms. The image shows the local viewpoint of one member, with time advancing upward.

For a start, assume a consistent state, i.e., everybody agrees on the same key (represented by a black circle filled white). This is labeled as the Root node. Further assume that two other nodes have independently generated new keys. These two keys would normally be in conflict: Which is the right one to use? In Versakey, this is not a problem, as it supports sets of keys for all operations where normally a single key would be used. This set is known as the active set and consists of all the leaf nodes in this "inheritance graph" (actually, a directed acyclic graph, or DAG) rooted at the Root node.

The key actually used for cryptographic operations is then a function of all members in the active set (e.g., a simple exclusive-or). Whenever a key is used, the unique key IDs of the members of the active set (i.e., the keys that contributed to the set) are communicated as well, to enable the other nodes to construct the appropriate key.

When our observed node needs to generate a new key to supercede the current information (middle third of the image), it uses the current active set as the base (and will enlist the IDs of the keys in the active set as parents). The right third of the image shows a potential key graph and active set when multiple concurrent operations continue to happen.

It can be shown that the size of the active set is bounded by the maximum number of operations that executed concurrently and that the active set will shrink when the group membership changes at lower concurrency rates (it does not change size when no changes take place, but this can be alleviated by introducing no-op changes). When communication is reliable and the delays satisfy the triangle inequality, no messages ever refer to keys that will only arrive in the near future. Also, nodes only need to buffer the keys seen within a round-trip time.

Publications

(Technical reports suppressed.)

Patents

• Germano Caronni and Marcel Waldvogel: Efficient, secure multicasting with minimal knowledge
  • U.S. patent 6,195,751
  • European Patent EP952718
  • German Patent DE69902414 (entitled Effiziente sichere Mehrfachübertragung mit minimaler Kenntnis)
• Germano Caronni and Marcel Waldvogel: Efficient, secure multicasting with global knowledge
  U.S. patent 6,049,878.

Participants

• Germano Caronni
• Roman Hofer
• Bernhard Plattner
• Dan Sun
• Marcel Waldvogel
• Nathalie Weiler

The VersaKey project site still has some information, even though it is no longer being maintained.