INTERNET-DRAFT D. Balenson, D. McGrew, A. Sherman
TIS Labs at Network Associates
February 26, 1999
Key Management for Large Dynamic Groups:
One-Way Function Trees and Amortized Initialization
<draft-balenson-groupkeymgmt-oft-00.txt>
Status of this Memo
This document is an Internet-Draft and is in full conformance
with all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-Drafts
as reference material or to cite them other than as "work in
progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Copyright Notice
Copyright (C) The Internet Society (1999). All Rights Reserved.
Abstract
We present a scalable method for establishing group session keys
for secure large, dynamic groups such as multicast sessions.
Our method is based on a novel application of One-Way Function
Trees (OFTs). The number of keys stored by group members, the
number of keys broadcast to the group when new members are added
or evicted, and the computational efforts of group members, are
logarithmic in the number of group members. The method provides
perfect forward and backward security: evicted members cannot
read future messages, even with collusion by arbitrarily many
evicted members, and newly admitted group members cannot read
previous messages.
Balenson, McGrew, Sherman expires August 26, 1999 [Page 01]
INTERNET-DRAFT February 26, 1999
Contents
1. Introduction ................................................. 2
2. Previous Work ................................................ 3
2.1 Key Establishment Algorithms for Large Groups ................ 3
2.2 Managing Large Groups ........................................ 4
2.3 Authentication in Large Groups ............................... 4
2.4 Multicast Security ........................................... 5
3. Group Operations and Their Security Requirements ............. 5
3.1 Operations ................................................... 5
3.2 Security Requirements ........................................ 6
4. One-Way Function Trees ....................................... 7
4.1 Structure of an OFT .......................................... 7
4.2 Algorithms ................................................... 8
4.3 Properties .................................................. 10
4.4 Implementation Notes and Example ............................ 11
4.5 Comparisons with Other Leading Key-Establishment Methods .... 12
5. Amortized Group Induction ................................... 15
5.1 Induction Model ............................................. 15
5.2 Induction Algorithm ......................................... 16
5.3 An Example of Induction ..................................... 16
6. Conclusion and Open Problems ................................ 17
7. Security Considerations ..................................... 18
8. References .................................................. 18
9. Acronyms and Abbreviations .................................. 23
10. Authors' Addresses .......................................... 24
11. Acknowledgments ............................................. 24
1. Introduction
Efficiently managing cryptographic keys for large, dynamically
changing groups is a difficult problem. Every time a member is
evicted from a group, the group key must change; it may also be
required to change when new members are added. The members of
the group must be able to compute a new key efficiently, while
arbitrary coalitions of evicted members must not be able to obtain
it. Communication costs must also be considered.
Real-time applications, such as secure audio and visual broadcasts,
pay TV, secure conferencing, and military command and control,
need very fast re-keying so that changes in group membership are
not disruptive. To deal with large group sizes (e.g. 100,000
members), we seek solutions whose re- keying operations "scale"
well in the sense that time, space, and broadcast requirements
of the method grow at most logarithmically in the group size.
Key management for these applications should be able to take
advantage of efficient broadcast channels, such as radio broadcast
and Internet multicast.
We present a new practical algorithm for establishing shared,
secret group communications keys in large, dynamic groups. Our
Balenson, McGrew, Sherman expires August 26, 1999 [Page 02]
INTERNET-DRAFT February 26, 1999
algorithm [McG98, Hard97, Bal98], which is based on a novel
application of one-way function trees, scales logarithmically in
group size. In comparison with previously published methods,
our algorithm achieves a new low in the required broadcast size.
2. Previous Work
The broad and challenging problem of establishing keys for large
dynamic groups touches upon a large body of previous work,
including algorithms for key establishment, group management,
authentication in large groups, and multicast security. As for
key management, unfortunately very little work has been done on
this critical problem in the open literature (e.g. see Schneier
[Sch96, pp. 169-187]).
2.1 Key Establishment Algorithms for Large Groups
Prior methods for establishing keys in groups fall roughly into
five categories: simple methods that scale linearly in group
size, information- theoretic approaches, algorithms based on
group Diffie-Hellman key exchange, hybrid methods that trade off
information-theoretic security for reduced storage requirements,
scalable methods based on hierarchies, and other techniques.
Sherman [Bal98, Section 7], Kruus [Kru98], Menezes [Men97], and
Just [Jus94] survey some of these methods.
Unfortunately, the information-theoretic approaches [Blu92, Sti96,
Chi89] require exponential space to achieve forward secrecy
against arbitrarily many colluding evicted members. Although
the group Diffie-Hellman methods [Ste96-7, Bur97, Bur94] offer
attractive distributed functionality, they suffer from a linear
number of expensive public-key operations. Similarly, the hybrid
approaches [Fia93, Ber91] scale linearly or worse. As for other
techniques (e.g. [Blo90, Gon89]) that do not fall nicely into
any of the above categories, we have not found any that provide
adequate security.
Therefore, for large groups, the leading candidates are the
hierarchical methods, which scale logarithmically in group size.
There are two hierarchical methods that do not require trusted
internal nodes: the Logical Key Hierarchy (LHK) of Wallner,
Harder, and Agee [Wal97, Won97], and the One-Way Function Tree
(OFT) method of McGrew and Sherman [McG98]. OFT was developed
at TIS Labs at Networks Associates, Inc., as part of the DARPA-funded
Dynamic Cryptographic Context Management (DCCM) Project [Bal98];
it is the subject of this document.
The hierarchical methods of Ballardie [Bal96, Bal97] and Harkins
[Hark98a] are scalable but require trusted routers.
In addition, the linear Single Key Distribution Center (SKDC)
Balenson, McGrew, Sherman expires August 26, 1999 [Page 03]
INTERNET-DRAFT February 26, 1999
approach is attractive for its simplicity -- at least for relatively
small groups (e.g. see [Harn97a-b, Harn98]).
2.2 Managing Large Groups
Managing large groups is important for group communications and
for a variety of other applications, including distributed
fault-tolerant computing and virtual private networks. Researchers
have addressed important group-management issues including defining
group membership, supporting distributed fault-tolerant applications,
and effecting decentralized dynamic group management.
An important problem in group management is the problem of defining
group membership. To support the design of secure, asynchronous,
distributed, fault-tolerant systems, Michael Reiter [Rei94]
devised a group-membership protocol that tolerates malicious
corruption of up to one third of the participants. This protocol
is useful in building systems that are robust against limited
failures (e.g. hardware failure of some nodes), and that through
threshold techniques distribute trust among two or more parties.
By contrast, a single group controller is a single point of
failure and hence not fault tolerant.
Although group keying is often used to secure group communications,
another application of group keying arises in security architectures
for distributed fault-tolerant computing. For example, Kenneth
Birman [Rei93] and his research group at Cornell have studied
how the notion of a secure process group can be used to effect
secure, distributed, fault-tolerant computing. Their efforts
include the ISIS, Horus [Hor], and Ensemble [Hay98] Systems,
which provide a framework and toolkit for developing distributed
applications.
Birman [Rod97] and his group have also applied similar ideas to
design a virtual private network that can handle network faults,
decentralized management, and dynamic membership. Unfortunately,
their "solution currently scales [only] to approximately 100
machines" [Rod97, p. 14]. Also, they claim, that for data
confidentiality, "[their] keys are so dynamic and short-lived
[changed once a minute] that the approach could be used with a
fairly weak cryptographic scheme" [Rod97, p. 1].
Li Gong [Gon96, Keu96] designed and implemented a toolkit called
Enclaves for building secure user-level group applications.
Enclaves enable users to form virtual private networks on the
Internet dynamically. His methods, however, do not scale to
large groups. Other recent work in group management includes
research by Fenner [Fen97].
2.3 Authentication in Large Groups
There are several ongoing projects to develop infrastructures to
Balenson, McGrew, Sherman expires August 26, 1999 [Page 04]
INTERNET-DRAFT February 26, 1999
support authentication. Among these are the following. The
X.509 [Ken93] approach is based on a hierarchical global name
space. By contrast, the SDSI/SPKI approaches of Rivest and
Lampson [Riv96], and Ellison [Ell97] are based on linked local
name spaces. The Secure DNS approach of Eastlake [Eas96] builds
on the existing DNS (Domain Name System).
In addition, there is work on batch authentication [Nac94], which
provides a way to verify many certificates simultaneously for
certificates signed by the same authority under the same signature
key.
2.4 Multicast Security
Securing multicast is an active area of research. Some examples
of this research are works by Kent [Ken81], Gong and Shachan
[Gon94], Ballardie and Crowcroft [Bal95], Deering [Dee98, Dee89],
Bagnall [Bag97], Mittra [Mit97], Caronni, et., al. [Car98], and
Canetti and Pinkas [Can98], which address issues, requirements,
architectures, protocols, and techniques. In addition, the works
by Ballardie [Bal96] and Harkins [Hark98a] on key establishment
discuss a variety of security problems and solutions for multicast.
Securing Mbone [Kum95] broadcasts is one driving application.
3. Group Operations and Their Security Requirements
We envision that the management of group communications keys will
take place in a setting in which there will be a communications
system, a set of possibly overlapping groups of individuals with
common purposes, and individual group members. A systems manager
will manage the communications system, and a group manager will
manage each group. We envision that groups will comprise a
hierarchy of subgroups, with subgroup and organizational managers
negotiating on behalf of subgroup members.
3.1 Operations
Associated with each role (system manager, group manager,
individual) is a set of operations, minimally including the
following operations.
Operations processed by the system manager:
- induct individual into system,
- evict individual from system,
- create group, and
- dissolve group.
Section 5 explains the concept of group induction. In short,
the most important results of system (or group) induction are
for an individual to establish a base system key known only to
the individual and the system (or group) manager, and for the
Balenson, McGrew, Sherman expires August 26, 1999 [Page 05]
INTERNET-DRAFT February 26, 1999
system (or group) manager to check the credentials of the
individual.
Operations processed by a group manager:
- add member(s) to group,
- remove member(s) from group,
- evict member(s) from group,
- initiate communications session, and
- terminate communications session.
This document focuses on the crucial operations of adding and
deleting members from a group. Note that our OFT method offers
some economy of scale when adding or deleting two or more
individuals simultaneously. There are two types of membership
deletions: a temporary removal (when the individual has not lost
his security privileges), and a permanent eviction as the result
of loss of security privileges.
Operations requested by individuals:
- request to join group,
- request to leave group,
- request to join session,
- request to leave session, and
- request to return to session.
It is possible that an individual might temporarily lose contact
with his group manager --for example, as might happen if an
airplane flies out of radio range of his group. Therefore, there
must be a way for such a member to re-synchronize key establishment
with the group.
3.2 Security Requirements
The primary security requirements for the group operations of
adding and deleting members are forward and backward security,
as quantified by the degree of forward or backward security
[Men97, pp. 528-529]. We say that a method has t-forward
security if and only if (iff) no t colluding evictees can read
any future communications traffic of the group. Similarly, a
method has t-backward security iff no group of t colluding new
members can read any previous group traffic. A method has perfect
forward (backward) security iff the method has t-forward (t-backward)
security for all t.
Backward security is optional. When a new member is added, the
group manager may choose to create a new group key, thus denying
the new member access to the old key and hence previous traffic.
We seek methods, such as OFT, that provide perfect forward
security, with the option of perfect backward security.
Balenson, McGrew, Sherman expires August 26, 1999 [Page 06]
INTERNET-DRAFT February 26, 1999
Carefully note our definitions of the phrases "perfect forward
security" and "perfect backward security." Our use of these
convenient phrases should not be confused with the different
requirement, as explained by Menezes et al. [Men97, p. 496], that
compromise of long-term keys does not reveal past session keys.
Similarly, our use of these phrases does not necessarily imply
information-theoretic "perfectly-secure key distribution" in the
sense used by Blundo et al. [Blu92].
Two additional valuable security measures are degree of traceability
and degree of disclosure amplification. A method is t-traceable
iff more than t colluding members are required to leak plaintext
or session keys without being identified if leaked material is
discovered. Disclosure amplification refers to the extent of
unauthorized disclosure of internal state information (e.g.
subgroup keys) caused by the unauthorized disclosure of certain
other internal state information.
In addition, when specifying security requirements for particular
applications, it is important to understand the security needs
and assumptions with regard to any underlying cryptographic
primitives (e.g. one-way functions) and with regard to fundamental
types of cryptographic strength (e.g. information theoretic,
computational, quantum uncertainty).
4. One-Way Function Trees
A One-Way Function Tree (OFT) is a binary tree, each node x of
which is associated with two cryptographic keys: a node key k_x
and a blinded node key k'_x = g(k_x). The blinded node key is
computed from the node key using a one-way function g; it is
blinded in the sense that a computationally limited adversary
cannot find k_x from k'_x.
Although the concept of a one-way function tree is not new (e.g.
in 1979, Merkle [Mer79] proposed an authentication system based
on a similar idea), our application of this concept is novel.
4.1 Structure of an OFT
A group manager maintains a one-way function tree. Each leaf is
associated with a member of the group. The manager uses a
symmetric encryption function E to communicate securely with
subsets of group members, using unblinded keys as encryption keys
as explained below.
Each internal node of the tree has exactly two children. The
manager assigns a randomly chosen key to each member, securely
communicates this key to the member (using an external secure
channel), and sets the node key of the member's leaf to the
member's key. The interior node keys are defined by the rule:
Balenson, McGrew, Sherman expires August 26, 1999 [Page 07]
INTERNET-DRAFT February 26, 1999
k_x = f( g(k_left(x)), g(k_right(x)) ), (1)
where left(x) and right(x) denotes the left and right child of
the node x, respectively. The function g is one-way, and the
function f is a "mixing" function (e.g. XOR). McGrew and Sherman
[McG98] discuss the properties of f and g in detail. The node
key associated with the root of the tree is the group key, which
the group can use to communicate with privacy among group members
and/or authentication of group membership.
The security of the system depends on the fact that each member's
knowledge about the current state of the key tree is limited by
the following invariant:
OFT Security Invariant - each member knows the unblinded node
keys on the path from its node to the root, and the blinded
node keys that are siblings to its path to the root, and no
other blinded or unblinded keys.
This invariant is maintained by all operations that add members
to the group, and by all operations that delete members from the
group.
4.2 Algorithms
The operations of adding and evicting members rely on the
communication of new blinded key values, from the manager to all
members, after the node key associated with a leaf has changed.
To maintain security, each blinded node key must be communicated
only to the appropriate subset of members. If the blinded key
k'_x changes, then its new value must be communicated to all of
the members who store it. These members are associated with the
descendants of the sibling of x, and they know the unblinded node
key k_s, where s is the sibling of x. To provide the new value
of the blinded key to the appropriate set of members, and keeping
it from other members, the manager encrypts k'_x with k_s before
broadcasting k_x to the group. (Here and throughout, we shall
use the verb "broadcast" in the sense of "group broadcast" --
sending a message from the group manager to all members of the
group.)
4.2.1 Adding a member
When a new member joins the group, an existing leaf node x is
split, creating new nodes left(x) and right(x). The member
associated with x becomes associated with left(x), and the new
member is associated with right(x). Both members are given new
keys. The old member gets a new key because their former sibling
knows the old blinded node key and could use this information in
collusion with another group member to find an unblinded key that
is not on his path to the root. The new values of the blinded
Balenson, McGrew, Sherman expires August 26, 1999 [Page 08]
INTERNET-DRAFT February 26, 1999
node keys that have changed are broadcast securely to the
appropriate subgroups, as described in the previous paragraph.
The number of blinded keys that must be broadcast to the group
is equal to the distance from x to the root plus two. In addition,
in a unicast transmission, the new member is given their set of
blinded node keys, using the external secure channel. In order
to keep the height h of the tree as low as possible, when a new
member is added, the leaf closest to the root is split.
4.2.2 Evicting a member
When the member associated with a leaf y is evicted from the
group, the member assigned to the sibling of y is reassigned to
the parent p of y and given a new leaf key value. If the sibling
s of y is the root of a subtree, then p becomes s, moving the
subtree closer to the root. In this case, one of the leaves of
this subtree is given a new key (so that the evictee no longer
knows the blinded key associated with the root of the subtree).
The new values of the blinded node keys that have changed are
broadcast securely to the appropriate subgroups. The number of
keys that must be broadcast is equal to the distance from y to
the root.
4.2.3 Initialization
Group initialization is the process through which the group
establishes an initial group communications key. For our OFT
method, this process involves two steps. First, the group manager
broadcasts some information to the group members needed to apply
the OFT key-updating procedures. Second, the members compute a
shared group communications key, which is needed to begin secure
group communications.
Group initialization is separate from group induction, which is
explained in Section 5. During group induction, each member
establishes an individual group base key known only by the member
and the group manager. Group initialization assumes that each
member has already established an individual group base key.
In the first step of OFT group initialization, the manager
broadcasts every blinded node key in the OFT to all group members.
In this broadcast, each blinded node key is encrypted by the
unblinded key of the sibling node, so that only members in the
sibling subtree can learn the blinded node key. All members
receive the entire broadcast, which consists of a sequence of
encrypted blinded node keys. The order in which the keys are
broadcast is determined by a postorder traversal of the OFT.
This procedure enables the members to associate the keys that
they need with the encrypted message parts they receive.
Balenson, McGrew, Sherman expires August 26, 1999 [Page 09]
INTERNET-DRAFT February 26, 1999
4.3 Properties
In this section we comment briefly on the security, resource
usage, and salient characteristic features of The OFT method.
For more details, see the paper by McGrew and Sherman [McG98].
The security properties of OFT stem from the system invariant
stated in Section 4.1, from the strength of the component one-way
function, and from the random selection of leaf keys. In short,
OFT provides perfect forward secrecy and optional perfect backward
secrecy. Thus, arbitrary coalitions of evicted members cannot
directly compute the group communications key nor any unblinded
node key.
Evicted members have some information about the key tree but not
enough to compute directly any unblinded node key. After a member
is evicted, the keys along the path from the member's node to
the root change. After this change, the evictee knows only the
blinded keys of the siblings of the nodes along the path from
the evictee to the root. These blinded nodes are insufficient
to compute directly any unblinded key.
Interestingly, OFT is a centralized, member-contributory method.
OFT is centralized in the sense that the group manager plays a
special trusted role. OFT is member contributory in the sense
that each leaf can contribute entropy to the group communication
key.
The hierarchical nature of OFT distributes the computational
costs of re- keying among the entire group, so that the managers
computational burden is comparable to that of a group member.
Table 1 below summarizes the salient resource usage of adding or
deleting a member with OFT in terms of time, memory, number of
bits broadcast, and number of random bits needed.
Resource Measure Group Member Cost Group Manager Cost
Time h h
Memory hK 2nK
Bits broadcast 0 hK + h
Random bits generated 0 K
Table 1: Summary of resource usage of adding or deleting
a member with OFT. Here, n is the group size, K is the
size of a key in bits, and h is the height of the OFT (h
= lg n when the tree is balanced). Either the member or
the manager could generate the random bits needed at the
leaves.
Balenson, McGrew, Sherman expires August 26, 1999 [Page 10]
INTERNET-DRAFT February 26, 1999
4.4 Implementation Notes and Example
Several important engineering decisions must be made in the
implementation of the OFT algorithm: the choice of f and g, the
format of broadcasts by the manager, the representation of the
tree, and time-space tradeoffs by each member involving how many
unblinded ancestor keys to store.
The function g can be based on a cryptographic hash function such
as MD5 [Riv92] or SHA-1 [Sha-1]. It is possible that the node
keys do not need to be as large as the output size of the underlying
function. For example, MD5 has a sixteen-byte output, while DES
keys are only seven bytes long. The function g can be constructed
from MD5 by discarding some of the output, as is done by S/KEY,
so that the node keys (and thus the broadcasts) are smaller.
The function f does not need to be one-way; it needs only to mix
its inputs. This fact suggests that f(x,y) = x XOR y is a fast,
simple, and effective choice (XOR denotes the bitwise exclusive-or
function).
+----------@----------+
| |
+-----@-----+ +-----#-----+
| | | |
+--#--+ +--@--+ * *
| | | |
* * # @
M
Figure 1: An example of an OFT key tree. The member at the
leaf labeled M knows the keys of the nodes labeled @ (including
the root key, which is used as the group key), and the blinded
keys of the nodes labeled #.
Balenson, McGrew, Sherman expires August 26, 1999 [Page 11]
INTERNET-DRAFT February 26, 1999
The representation of the tree and the formats of the messages
from the group manager are important but routine engineering
decisions. For example, the tree could be represented as a record
and pointer structure, or as a linear array. Message formats
for messages broadcast from the manager could explicitly include
node number information to identify which parts of a message
correspond to which subtrees, or such topological information
could be implicit in the ordering of the message parts.
4.5 Comparisons with Other Leading Key-Establishment Methods
In this section we briefly compare our OFT algorithm against the
two leading competing algorithms for establishing keys in large
dynamic groups: the Logical Key Hierarchy (LKH) of Wallner,
Harder, and Agee [Wal97], and the Single Key Distribution Center
(SKDC). As reviewed in Section 2, these two algorithms and OFT
are the main choices available to system engineers who do not
wish to trust network routers in large group applications. OFT
and LKH are appealing because their computation, broadcast, and
memory requirements scale logarithmically with group size.
Despite its linear complexity, SKDC is appealing for its simplicity.
As suggested in an observation attributed to Radia Perlman, the
add-member operation in LKH can be significantly improved by
computing the new group communications key as the result of
applying a one-way function to the current group communications
key. We shall refer to this refinement of LKH, which maintains
perfect backward security, as LKH+. Unfortunately, this refinement
applies neither to the delete-member operation nor to the OFT
algorithm -- in OFT, this refinement would violate the main system
invariant. Fortunately, in many applications, add-member is
performed much more frequently than is evict-member. Independently
of Perlman, V. Viswanathan [Vis96, pp. 25-26] also suggested a
similar constant-time member-parallel idea.
4.5.1 Comparison Criteria
The choice of which key-establishment algorithm should be used
can be answered meaningfully only in the context of the requirements
of particular applications. To assist engineers in making their
choices, we shall summarize some of the major properties of SDKC,
LHK, LKH+, and OFT in terms of selected quantitative comparison
criteria. These criteria include total delay, number of bits
broadcast, number of bits unicast, manager computation, maximum
member computation, number of random bits generated, and manager
and member memory requirements. Each of these methods provides
perfect forward security with the option of perfect backward
security.
The four leading candidate methods differ also in terms of required
primitives, security semantics, central versus contributory
flavor, and resynchronization capabilities (for dealing with
group members who temporarily are unable to receive manager
Balenson, McGrew, Sherman expires August 26, 1999 [Page 12]
INTERNET-DRAFT February 26, 1999
broadcasts). For example, SDKC and LKH require encryption
functions; LKH+ and OFT require encryption functions and one-way
functions. Although none of the authors of any of these methods
has provided a formal proof of security, some engineers may have
greater confidence in the security of methods with simpler security
semantics. Listed in increasing complexity of security semantics,
the methods are: SDKC, LKH, LKH+, OFT. With regard to the source
of entropy of random bits in common group communication keys,
SDKC, LKH, and LKH+ may be viewed as member non-contributory
methods because the group manager provides all of the entropy.
By contrast, OFT can be used in either a member non-contributory
or member-contributory fashion. Most applications have a need
to provide a resynchronization capability; some methods may
provide some degree of passive member-synchronization.
When asked why she based her LKH method on a keyed encryption
function rather than on a faster keyless one-way function (as
used in OFT), Wallner [private communication (11/19/97)] explained
that her motivating application was a radio communication system.
In this application, the available hardware supported a keyed
encryption function but not a keyless one-way function. Wallner
also remarked (without connection to the choice of encryption
function versus one-way function), that in her application, it
was very important to conserve battery power. Although these
considerations were important to her application, other applications
might have different requirements or available primitives; thus
the rationale for Wallner's choices do not necessarily apply to
other applications.
4.5.2 Quantitative Comparison of SKDC, LKH, LKH+, and OFT
Tables 2 and 3 summarize the time, broadcast, and space requirements
of each of the four leading candidate algorithms (SKDC, LKH,
LKH+, and OFT). Specifically, for each algorithm and for each
of the initialize, add- member, evict-member operations, Table
2 summarizes the total delay, number of bits broadcast, number
of bits unicast, manager time, maximum member time, and number
of random bits generated. Table 3 summarizes the manager and
member memory requirements. For more details, see McGrew and
Sherman [McG98].
4.5.3 Summary
For moderate size groups, the simple SKDC may often be appealing.
For very large groups, however, many applications will likely
demand a method that scales logarithmically in total delay and
member memory usage. For such applications, especially if the
add-member is more frequent than the evict-member operation, the
LKH+ method looks very attractive for its constant-time add-member
and relatively simple security semantics. If for the application
it is critical to minimize the number of bits broadcast or the
number of random bits generated, or if a member-contributory
method is needed, then OFT may be the method of choice.
Balenson, McGrew, Sherman expires August 26, 1999 [Page 13]
INTERNET-DRAFT February 26, 1999
Initialization
RESOURCE MEASURE SKDC LKH LKH+ OFT
Total delay n 2n 2n 3n
Number of bits broadcast nK 2nK+h 2nK+h 2nK+h
Number of bits unicast 0 0 0 0
Manager computation n 2n 2n 3n
Max member computation 1 h h 2h
No. of random bits generated K 2nK 2nK nK
Add member
RESOURCE MEASURE SKDC LKH LKH+ OFT
Total delay n 2h 1 3h
Number of bits broadcast nK 2hK+h h hK+h
Number of bits unicast 0 0 K hK
Manager computation n 2h 1 3h
Max member computation 1 h 1 2h
No. of random bits generated K hK 0 K
Evict member
RESOURCE MEASURE SKDC LKH LKH+ OFT
Total delay n 2h 2h 3h
Number of bits broadcast nK+lg n 2hK+h 2hK+h hK+h
Number of bits unicast 0 0 0 0
Manager computation n 2h 2h 3h
Max member computation 1 h h 2h
No. of random bits generated K hK hK K
Table 2: Summary of time and communication usage of
initialization, add-member, and evict-member with the SKDC,
LKH, LKH+, and OFT key-establishment methods. Here, n is
the group size, K is the size of a key in bits, and h is the
height of the key tree (h = lg n when the tree is balanced).
Note that while LKH and LKH+ hve lower magnitudes of total
delay, the units of time for OFT are typically much smaller
because keyless one-way functions are much faster than are
keyed-encryption functions.
Memory Usage
RESOURCE MEASURE SKDC LKH LKH+ OFT
Manager storage nK 2nK 2nK 2nK
Max member storage 2K hK hK hK
Table 3: Summary of manager and member memory usage in the
SKDC, LKH, LKH+, and OFT Key-establishment methods. Here,
n is the group size, K is the size of a key in bits, and h
is the height of the key tree (h = lg n when the tree is
balanced).
Balenson, McGrew, Sherman expires August 26, 1999 [Page 14]
INTERNET-DRAFT February 26, 1999
5. Amortized Group Induction
Before a group can establish an initial group communications key,
the members must be inducted (enrolled) into the group. For
centralized key establishment methods including OFT, an important
objective of this induction step is for each member to establish
an individual base key known only to the member and the group
manager. The induction process also ensures that each member has
the necessary certificates to take advantage of the supporting
authentication infrastructure. The main computational goal of
induction is to minimize its total delay.
For each group member to establish a separate base key with the
Group Manager, the simplest approach is for the manager to engage
each member in a separate pairwise authenticated key exchange
protocol, such as the Internet Key Exchange (IKE) protocol [Har98,
Mau98, Orm]. Unfortunately, this simple approach scales linearly
in group size.
In this section we describe a new approach to group induction
due to Sherman [She98] that amortizes the relatively high cost
of a pairwise key exchange over multiple entries into groups.
This amortization saves time when many users become members of
two or more groups. We call this new approach "amortized
induction." An IBM team [Blu97] independently discovered a
similar idea in a network context.
5.1 Induction Model
Assume there is a universe of N individuals from which G groups
are formed, each group having at most n members. Assume further
that N is much smaller than Gn; that is, many individuals belong
to several groups. It is for this reasonable assumption that
amortized induction offers significant savings.
We assume that there is a system that administers multiple groups,
each of whose group communications key is established by a
key-establishment algorithm such as OFT. Each participant may
join one or more group. Each group has a group manager, and
there is a system manager who controls induction into the system.
For simplicity we shall describe the induction process in terms
of a single system manager, though the concept of system manager
can be extended to a more general system management function
which might be distributed. For each group, each member must
establish an individual base key known only to the member and
the group manager.
Amortized induction reduces the number of expensive pairwise key
exchanges from Gn to N, which can be a significant savings.
Amortized induction comes at the cost of Gn one-way function
applications by the system manager, but these function evaluations
are much faster than pairwise key exchanges. For example, a single
Balenson, McGrew, Sherman expires August 26, 1999 [Page 15]
INTERNET-DRAFT February 26, 1999
application of the MD5 hash function is approximately 1000 times
faster than a single ISAKMP/OAKLEY key exchange.
5.2 Induction Algorithm
Whenever an individual first enters the system, the member
establishes an individual system base key known only to the
individual and the system manager. For example, this step could
be carried out using the ISAKMP/OAKLEY Key-Exchange Protocol.
Thereafter, whenever the individual joins a group, the individual
can establish an individual group base key with the group manager
as a one-way function of the individual's system base key, the
individual's name, and the group name.
More specifically, let A be the group name. For each member M,
the group base key KA_M for M is computed as a one-way function
F of M's system base key K_M, the name of M, and the group name.
For example,
KA_M = F( K_M, M, A ), (2)
where F is a publicly known one-way function such as the hash
function MD5. The total member delay in this computation is
constant.
The function F must satisfy the following properties: it must be
easy to compute given its three inputs, and it must be infeasible
for anyone to compute the output given only the last two inputs
(even under an adaptive chosen plaintext/ciphertext attack).
Whenever a group manager is appointed, the group manager establishes
a manager key k_A known only to the group manager and the system
manager. For added security this key establishment could be
carried out using the same pairwise key-exchange protocol used
in the induction process; alternatively, it would be possible to
compute manager keys along the lines of Equation 2.
Whenever members of a group need to be inducted, the system
manager computes the group base keys and unicasts them to the
group manager, encrypted under the manager key k_A. The length
of this unicast is linear in the group size. Note that, unlike
the SKDC method, no group broadcast is required. Members of
different groups can be inducted in parallel.
5.3 An Example of Induction
To illustrate the amortized induction process, consider a toy
example in which there are three individuals Q, R, S and two
groups A = {Q, R} and B = {S}.
Balenson, McGrew, Sherman expires August 26, 1999 [Page 16]
INTERNET-DRAFT February 26, 1999
When Member Q is inducted into the system, he establishes a base
system key K_Q known only to Q and the system manager. Similarly,
Members R and S establish base system keys K_R and K_S, respectively.
At the appointment of Group Manager A, Manger A establishes a
manager key k_A known only to Manager A and to the system manager.
Similarly, Group Manager B shares a manager key k_B with the
system manager.
To induct members of Group A, the system manager computes the
group base keys KA_Q, and KA_R for Members Q and R, respectively,
and sends them to Manager A encrypted under manager key k_A.
For example, KA_Q = f(K_Q, Q, A) and KA_R = f(K_R,R,A). In
parallel, Members Q and R each computes his own group base key.
Members of Group B are similarly inducted.
6. Conclusion and Open Problems
We have presented and analyzed a new practical hierarchical
algorithm for establishing shared cryptographic keys for large,
dynamically-changing groups. Our algorithm is based on a novel
application of One-way Function Trees (OFTs).
Unlike all previously proposed solutions based on information
theory, public-key cryptography, hybrid approaches, or a single
key distribution center, our OFT algorithm has communication,
computation, and storage requirements, which scale logarithmically
with group size, for the add or evict operation. Each of the
aforementioned methods scale linearly or worse.
In comparison with the only other proposed hierarchical method
that does not depend on trusted routers - the Logical Key Hierarchy
(LKH) [Wal97] - - our OFT algorithm reduces by half the number
of bits broadcast by the manager per add or evict operation.
The user time and space requirements of OFT and LKH are roughly
comparable. For many applications, including multicasts, minimizing
broadcast size is especially important.
An improvement to the LKH method which we call LKH+ (see Section
4.5), however, offers a significant improvement to the add
operation in LKH, reducing the cost of the add-member operation
to one one-way function application, a unicast of one key, and
no broadcast. This improvement to LKH, together with LKH's
relatively simple security semantics, makes LKH+ an attractive
choice for many applications.
The OFT method is a centralized algorithm with the option of
member contributions to the entropy of the common communications
key. Its main advantages are that, in comparison with LKH+, it
reduces by a factor of two the number of bits required to be
broadcast for each evict-member operation. Our preliminary
security analysis of OFT [McG98] raises some interesting questions
Balenson, McGrew, Sherman expires August 26, 1999 [Page 17]
INTERNET-DRAFT February 26, 1999
about the security of function iterates, and that of bottom-up
one-way function trees.
It is important to realize that there are significant fundamental
limitations to achieving security in large groups -- one might
even say that a secure large group is an oxymoron. In most large
groups, it is very likely that at least one member is unreliable,
untrustworthy, malicious, or careless. Each member knows the
common communications key and the plaintext, which is the main
commodity being protected. Using multiple communications keys
for different subgroups would not enhance security since each
member would still have the plaintext. Any member could disclose
the plaintext. Consequently, in large groups, it becomes especially
important to detect traitors (e.g. through fingerprints and
watermarks [Kur98, Sta97, Cho94]) and to limit the loss caused
by disclosures (e.g. by rapid evictions and re-keying).
Special-purpose, physically secure hardware may play a role in
these objectives, by restricting access to communication keys,
complicating effective use of compromised keys, and providing
unique fingerprints.
Our OFT algorithm offers a practical approach with low broadcast
size to manage the demanding key establishment requirements of
secure applications for large, dynamic groups.
7. Security Considerations
This document proposes a new algorithm for securely establishing
a shared, secret group communications key in a large, dynamic
group. Section 4.4 describes the security properties of this
algorithm.
8. References
[Bag97] Bagnall, P., R. Briscoe, and A. Poppitt, "Taxonomy of
communication requirements for large-scale multicast applications,"
Internet Draft (work in progress), draft-ietf-lsma-requirements-01.txt,
Internet Engineering Task Force (November 21, 1997).
[Bal95] Ballardie, Tony, and Jon Crowcroft, "Multicast-specific
threats and counter-measures," Proceedings of the Internet Society
1995 Symposium on Network and Distributed System Security, February
16-17, 1995, San Diego, California, IEEE Computer Society (1995),
2-14.
[Bal96] Ballardie, A., "Scalable multicast key distribution,"
Request for Comments (RFC) 1949, Internet Engineering Task Force
(May 1996), 18 pages.
[Bal97] Ballardie, A. "Core based tree (CBT) multicast routing
architecture," Request for Comments (RFC) 2201, Internet Engineering
Task Force (September 1997), 14 pages.
Balenson, McGrew, Sherman expires August 26, 1999 [Page 18]
INTERNET-DRAFT February 26, 1999
[Bal98] Balenson, David M., Dennis K. Branstad, David A. McGrew,
and Alan T. Sherman, "Dynamic cryptographic context management
(DCCM): Report #1: Architecture and system design," TIS Report
No. 0709, TIS Labs at Network Associates, Inc., Glenwood, MD
(June 2, 1998). 121 pages.
[Ber91] Berkovitz, S., "How to broadcast a secret," Advances in
Cryptology: Proceedings of Crypto 91, Feigenbaum, ed,. LNCS 576,
Springer-Verlag (1991), 535-541.
[Blo90] Bloom, Joel, ed., X9.24-1990, "Financial services retail
key management," ANSI X9A3 (March 1990). 84 pages.
[Blu92] Blundo, Carlo, Alfred de Santis, Amir Herzberg, Shay
Kutten, Ugo Vaccaro, and Moti Yung, "Perfectly-secure key
distribution for dynamic conferences," Advances in Cryptology:
Proceedings of Crypto92, E. F. Brickell, ed., LNCS 740,
Springer-Verlag (1992), 471-486.
[Blu97] Blumenthal, Uri, Nguyen C. Hien, and Bert Wijnen, "Key
derivation for network management applications," IEEE Network
(May/June 1997), 26-29.
[Bur94] Burmester, Mike, and Yvo Desmedt, "A secure and efficient
conference key distribution system," Advances in Cryptology:
Proceedings of Eurocrypt 94, A. De Santis, ed., LNCS 950,
Springer-Verlag (1994), 275-286.
[Bur97] Burmester, Mike, and Yvo G. Desmedt, "Efficient and
secure conference key distribution," Secure Protocols, M. Lomas,
Ed., LNCS 1189, Springer-Verlag (1997), 119-130. [Revised and
expanded version of the corresponding Eurocrypt 94 paper by the
same authors.]
[Can98] Canetti, R. and B. Pinkas, "A taxonomy of multicast
security issues," Internet Draft (work in progress),
draft-canetti-secure- multicast-taxonomy-00.txt, Internet
Engineering Task Force (May 1998).
[Chi89] Chiou, Guang-Huei, and Wen-Tsuen Chen, "Secure broadcasting
using the secure lock," IEEE Transactions on Software Engineering,
15:8 (August 1989), 929-934.
[Cho94] Chor, B., A. Fiat, and M. Naor, "Tracing traitors,"
Advances in Cryptology: Proceedings of Crypto 94, Y. G. Desmedt,
Ed., LNCS 839, Springer Verlag (1994), 257-270.
[Dee89] Deering, S., "Host Extensions for IP Multicasting,"
Request for Comments (RFC) 1112, Internet Engineering Task Force
(August 1989). 17 pages.
Balenson, McGrew, Sherman expires August 26, 1999 [Page 19]
INTERNET-DRAFT February 26, 1999
[Dee98] Deering, S., D. Estrin, D. Farinacci, M. Handley, A,
Helmy, V. Jacobson, C. Liu, P. Sharma, D. Thaler, and L. Wei,
"Protocol independent multicast-sparse mode (PIM-SM): Motivation
and architecture," Internet Draft (work in progress), draft-ietf-
idmr-pim-arch-05.txt, Internet Engineering Task Force (August 4,
1998). 26 pages.
[Ell97] Ellison, C. M., "SPKI Requirements" (February 1997).
[For latest version, see http://www.clark.net/pub/cme/html/spki.html]
[Fen97] Fenner, W., "Internet group management protocol, version
2," Request for Comments (RFC) 2236, Internet Engineering Task
Force (November 1997). 24 pages.
[Fia93] Fiat, Amos, and Moni Naor, "Broadcast encryption,"
Advances in Cryptology: Proceedings of Crypto93, D. R. Stinson,
ed., LNCS 773, Springer-Verlag (1993), 481-491.
[Gon89] Gong, Li, and David J. Wheeler F. R. S., "A matrix key
distribution scheme," Journal of Cryptology, 2:1 (1990), 51-59.
[Gon94] Gong, Li, and N. Shacham, "Elements of trusted multicasting,"
Proceedings of the IEEE International Conference on Network
Protocols, Boston, Massachusetts (October 1994).
[Gon96] Gong, Li, "Enclaves: Enabling secure collaboration over
the internet," Proceedings of the Sixth USENIX Unix and Network
Security Symposium, San Jose, California (July 1996), 149-159.
[Hard97] Harding, Michael, David A. McGrew, and Alan T. Sherman,
"A new key-management algorithm for large dynamic groups,"
transparencies from talk given by Alan Sherman at NSA (November
19, 1997). 8 pages.
[Hark98a] Harkins, Dan, and Naganand Doraswamy, "A secure, scalable
multicast key management protocol (MKMP)," Draft (work in progress),
cisco Systems and Bay Networks (March 1998). 20 pages.
[Hark98b] Karkins, D. and D. Carrel, "The Internet key exchange
(IKE)," Internet Draft (work in progress), draft-ietf-ipsec-isakmp-
oakley-08.txt, Internet Engineering Task Force (June 1998).
[Harn97a] Harney, Hugh, Carl Muckenhirn, and Thomas Rivers, "Group
key management protocol (GKMP) architecture," Request for Comments
(RFC) 2094, Internet Engineering Task Force (July 1997).
[Harn97b] Harney, Hugh, Carl Muckenhirn, and Thomas Rivers, "Group
key management protocol (GKMP) specification," Request for Comments
(RFC) 2093, Internet Engineering Task Force (July 1997).
Balenson, McGrew, Sherman expires August 26, 1999 [Page 20]
INTERNET-DRAFT February 26, 1999
[Harn98] Harney, Hugh, and Eric Harder, "Multicast security
management protocol (MSMP): Requirements and policy," Draft (work
in progress), SPARTA, Inc. (February 23, 1998). 25 pages.
[Hay98] Hayden, Mark Garland, "The Ensemble system," Ph.D.
Dissertation, Department of Computer Science, Cornell University
(January 1998). 106 pages.
[Hor] The Horus Project,
http://simon.cs.cornell.edu/Info/Projects/HORUS/.
[Jus94] Just, Michael K., "Methods of multi-party cryptographic
key establishment," MS Thesis, School of Computer Science, Carleton
University (August 9, 1994). 77 pages.
[Ken81] Kent, Stephen T., "Security requirements and protocols
for a broadcast scenario," IEEE Transactions on Communications
(June 1981).
[Keu96] Keung, S., and L. Gong, "Enclaves in Java: APIs and
implementations," Technical Report SRI-CSL-96-07, SRI International,
Menlo Park, California (July 1996).
[Kru98] Kruus, Peter, "A survey of multicast security issues
and architectures," Proceedings 21st National Information Systems
Security Conference, October 5-8, 1998, Arlington, VA, 408-420.
[Kum95] Kumar, Vinay, Mbone Interactive Multimedia on the
Internet, New Riders Publishing (Indianapolis, IN, 1995).
[Kur98] Kurosawa, Kaoru, and Yvo Desmedt, "Optimum traitor
tracing and asymmetric schemes with arbiter," Draft (work in
progress), Spring 98). 13 pages.
[Mau98] Maughan, Douglas, Mark Schertler, Mark Schneider, and
Jeff Turner, "Internet security association and key management
protocol (ISAKMP)," Internet Draft (work in progress), draft-
ietf-ipsec-isakmp-10.txt, Internet Engineering Task Force (July
3, 1998). 86 pages.
[Men97] Menezes, Alfred J., Paul C. van Oorschot, and Scott A.
Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton,
Florida (1997).
[McG98] McGrew, David A., and Alan T. Sherman, "Key establishment
in large dynamic groups using one-way function trees," TIS Report
No. 0755, TIS Labs at Network Associates, Inc., Glenwood, MD (May
1998). 13 pages.
[Mer79] Merkle, Raph C., "Secrecy, authentication, and public-key
cryptosystems," Technical Report No. 1979-1, Information Systems
Laboratory, Stanford University, Palo Alto, CA (1979).
Balenson, McGrew, Sherman expires August 26, 1999 [Page 21]
INTERNET-DRAFT February 26, 1999
[Mit97] Mittra, Suvo, "Iolus: A framework for scalable secure
multicasting," Proceedings of the ACM SIGCOMM '97, September 14-
18, 1997, Cannes, France. 11 pages.
[Nac94] Naccache, David, David M'Raithi, Serge Vaudenay, and
Dan Raphaeli, "Can D.S.A. be improved? Complexity trade-offs with
the digital signature standard," Advances in Cryptology: Eurocrypt
'94, Alfredo De Santis, Ed., LNCS 950, Springer-Verlag (1994),
77-85.
[Orm] Orman, Hilarie K., "The OAKLEY key determination protocol,"
Internet Draft (work in progress), draft-ietf-ipsec-oakley-
02.txt, Internet Engineering Task Force. 48 pages.
[Rei93] Reiter, Michael, Kenneth Birman, and Robert van Renesse,
"A security architecture for fault-tolerant systems," Technical
Report TR93-1354, Department of Computer Science, Cornell University
(June 1993). 29 pages.
[Rei94] Reiter, Michael K, "A secure group membership protocol,"
Proceedings of the IEEE Computer Society Symposium on Research
in Security and Privacy, Oakland, California, May 14-16, 1994,
IEEE Press (1994).
[Riv92] Rivest, Ronald L., The MD5 Message-Digest Algorithm,
Request for Comments (RFC) 1321, Internet Engineering Task Force
(1992).
[Riv96] Rivest, Ronald L., and Butler Lampson, "SDSI: A simple
distributed security infrastructure," Version 1.1 (October 2,
1996).
[Rod97] Rodeh, Ohad, Ken Birman, and Mark Hayden, "Dynamic
virtual private networks," Technical Report TR97-1654, Department
of Computer Science, Cornell University (November 26, 1997). 16
pages.
[Sch96] Schneier, Bruce, Applied Cryptography: Protocols,
Algorithms, and Source Code in C, John Wiley & Sons (New York,
1996).
[Sha-1] FIPS Publication 180-1, Secure hash standard, NIST,
U.S. Department of Commerce, Washington, D.C. (April 1995).
[She98] Sherman, Alan T., "A new amortized approach to group
initialization: Refinements and analysis," TIS Report No. 0754,
Trusted Information Systems, Inc. Glenwood, MD (March 26, 1998).
12 pages.
[Sta97] Staddon, Jessica Nicola, "A combinatorial study of
communication, storage and traceability in broadcast encryption
Balenson, McGrew, Sherman expires August 26, 1999 [Page 22]
INTERNET-DRAFT February 26, 1999
systems," PhD Dissertation, Dept. of Mathematics, Univ. of
California, Berkeley, CA (September 1997). 43 pages.
[Ste96] Steiner, Michael, Gene Tsudik, and Michael Waidner,
"Diffie- Hellman key distribution extended to group communication,"
Proceedings of the 3rd ACM Conference on Computer and Communications
Security, March 14-16, 1996. 7 pages.
[Ste97] Steiner, M., G. Tsudik, and M. Waidner, "CLIQUES: A new
approach to group key agreement," IBM Research Report RZ 2984 (#
93030) (December 12, 1997). 17 pages.
[Sti96] Stinson, D. R., "On some methods for unconditionally
secure distribution and broadcast encryption," unpublished document
(November 21, 1996). 35 pages.
[Vis96] Viswanathan, Vaidhyanathan, "Unconditionally secure
dynamic conference key distribution," MS Thesis, University of
Wisconsin- Milwaukee (December 1996). 28 pages.
[Wal97] Wallner, Debby M., Eric J. Harder, and Ryan C. Agee,
"Key management for multicast: Issues and architectures," Internet
Draft (work in progress), draft-wallner-key-arch-01.txt, Internet
Engineering Task Force (September 15, 1998). 18 pages.
[Won97] Wong, Chung Kei, Mohamed G. Gouda, and Simon S. Lam
"Secure group communications using key graphs," Technical Report
TR-97-23, Dept. of Computer Science, Univ. of Texas at Austin
(July 28, 1997). 24 pages.
9. Acronyms and Abbreviations
DCCM Dynamic Cryptographic Context Management (a DARPA project [Bal98])
DNS Domain Name System
GDH Group Diffie-Hellman (a Group key exchange protocol)
LKH Logical Key Hierarchy
LKH+ Logical Key Hierarchy, with improved constant-time add-member
operation
MSMP Multicast Security Management Protocol (an NSA/Sparta effort
[Harn98])
NAI Network Associates, Inc.
OFT One-Way Function Tree
SKDC Single Key Distribution Center
SMG Secure Multicast Group
TIS Trusted Information Systems, Inc.
XOR Bit-wise exclusive-or
Balenson, McGrew, Sherman expires August 26, 1999 [Page 23]
INTERNET-DRAFT February 26, 1999
10. Authors' Addresses
Note: All correspondence relating to this document should be
sent to David Balenson.
David Balenson
TIS Labs at Network Associates, Inc.
3060 Washington Road (Rt. 97)
Glenwood, MD 21738
USA
Phone: +1 443 259 2358
Fax: +1 301 854 4731
Email: balenson@tislabs.com
URL: www.nai.com/products/security/tis_research/
crypto/crypt_dccm.asp
Dr. David A. McGrew
Cisco Systems, Inc.
170 West Tasman Drive
San Jose, CA 95134-1706
USA
Phone: +1 408 525 8651
Fax: +1 408 526 4952
Email: mcgrew@cisco.com
URL: www.cisco.com
Dr. Alan T. Sherman
Department of Computer Science and Electrical Engineering
University of Maryland, Baltimore County (UMBC)
1000 Hilltop Circle
Baltimore, MD 21250
USA
Phone: +1 410 455 2666
Fax: +1 410 455 3969
Email: sherman@umbc.edu
URL: www.csee.umbc.edu/~sherman
11. Acknowledgments
This work was done as part of the Dynamic Cryptographic Context
Management (DCCM) project at TIS Labs at Network Associates, Inc.
(formerly the Advanced Research & Engineering (AR&E) Division of
Trusted Information Systems (TIS)). Support for the DCCM project
was provided by the Defense Advanced Research Project Agency
(DARPA) through Rome Laboratory under Contract No. F30602-97-C-0277.
At the time of the work, David McGrew was a cryptography researcher
Balenson, McGrew, Sherman expires August 26, 1999 [Page 24]
INTERNET-DRAFT February 26, 1999
and Alan Sherman was a contractor on sabbatical leave from The
University of Maryland, Baltimore County (UMBC). McGrew and
Sherman designed and analyzed the OFT algorithm; Sherman devised
the amortized induction procedure; and Balenson assisted with
project management and final document preparation. In October
1998, McGrew became the head of the Cryptographic Software
Development Group at cisco Systems.
We would like to acknowledge contributions by several colleagues
at TIS Labs. We are very grateful to Michael V. Harding for
significant contributions to the original algorithm and for
discussing implementation strategies with us. Dennis K. Branstad,
Principal Investigator (former) of the DCCM Project, suggested
the problem and provided constructive recommendations and technical
guidance. Thanks also to Jay Turner for helpful comments, and
to Sharon Osuna and Caroline Scace for editorial suggestions.
Balenson, McGrew, Sherman expires August 26, 1999 [Page 25]