BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR92-1269
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Integrating Security in a Group Oriented Distributed System
AUTHOR:: Reiter, Michael K.
AUTHOR:: Birman, Kenneth P.
AUTHOR:: Gong, Li   
DATE:: February 1992
PAGES:: 15
NOTES:: replaces 91-1239
ABSTRACT::
A distributed security architecture is proposed for incorporation into group 
oriented distributed systems, and in particular, into the Isis distributed 
programming toolkit. The primary goal of the architecture is to make common 
group oriented abstractions robust in hostile settings, in order to 
facilitate the construction of high performance distributed applications that 
can tolerate both component failures and malicious attacks. These 
abstractions include process groups and causal group multicast. Moreover, a 
delegation and access control scheme is proposed for use in group oriented 
systems. The focus of the paper is the security architecture; particular 
cryptosystems and key exchange protocols are not emphasized.
END:: CORNELLCS//TR92-1269
BODY::
Integrating Security in a Group
Oriented Distributed System
Michael Reiter
Kenneth Birman
Li Gong
TR 92-1269
(replaces TR 91-1239)
February1 992
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
rhis work was supported by the Defense Advanced Research Projects Agency
(DoD) under DARPNNASA subcontract NAG 2-593, administered by the NASA Ames
Research Center by grants from GTE, IBM and Siemens, Inc. and by a National
Science Foundation Graduate Fellowship. Any opinions, conclusions or
recommendations expressed in this document are those of the authors and do not
necessarily reflect the views, policies or decisions of the National Science
Foundation or the Department of Defense.
Integrating Security in a Group Oriented Distributed System*
Michael R,eiter			Kenneth Birman			Li Gong
Dept. of Computer Science			Dept. of Computer Science
Cornell University			Cornell University
Ithaca, NY 14853			Ithaca, NY 14853
reiter?cs. cornell.edu			ken ?cs. cornell.edu
Abstract
A distributed security architecture is proposed for
incorporation into group oriented distributed systems,
and in particular, into the Tsis distributed program-
ming toolkit. The primary goal of the architecture is
to make common group oriented abstractions robust
in hostile settings, in order to facilitate the construc-
tion of high performance distributed applications that
can tolerate both component failures and malicious at-
tacks. These abstractions include process groups and
causal group multicast. Moreover, a delegation and
access control scheme is proposed for use in group
oriented systems. The focus of the paper is the s&
curity architecture; particular cryptosystems and key
exchange protocols are not emphasized.
1 Introduction
Systems that address security issues in distributed
environments have traditionally been constructed
upon the remote procedure call (RPC) paradigm of
communication (e.g., [4, 24, 28,17]). Many systems,
however, utilize more general types of communication
which have not enjoyed the same amount of atten-
tion from the security community. One such alterna-
tive is group oriented communication, based on the
process group abstraction [1]. Process groups have
been incorporated into many distributed systems (e.g.,
This work was supported by the Defense Advanced Re-
search Projects Agency (DoD) under DARPA/NASA subcon-
tract NAG2-593 administered by the NASA Ames Research
Center, by grants from GTE, IBM, and Siemens, Inc., and by
a National Science Foundation Graduate Fellowship. Any opin-
ions, conclusions or recommendations expressed in this docu-
ment are those of the authors and do not necessarily reflect the
views, policies or decisions of the National Science Foundation
or the Department of Defense.
ORA Corporation
675 Massachusetts Ave.
Cambridge, MA 02139
li?carnbridge. oracorp. corn
[18, 5, 2,19, 23,14,13]) and have been shown to sim-
plify the implementation of fault tolerant applications
[5, 2,14]. The benefit in preserving process group ab-
stractions in hostile environments could therefore be
great. In particular, it would facilitate the construc-
tion of applications that can tolerate both component
failures and malicious attacks.
To illustrate this need, consider a stock broker-
age that plans to establish a trading service to trade
stocks for a certain industry on the over-the-counter
market (OTC). The trading service will reside in a
large distributed system shared by other brokerages
and traders. Because the brokerage is a market maker
for that industry, other brokerages and traders buy
and sell stocks in that industry through that broker-
age, and so the service will be utilized by other trader's
applications. The availability and performance of this
service is crucial, and thus it must be replicated. Ac-
cordingly, the firm's programmers might like to im-
plement this service as a fault tolerant process group
using their favorite group oriented programming envi-
ronment.
At the same time, however, the brokerage is con-
cerned about the security of its service. The brokerage
plans to execute this service on a potentially dynamic
set of sites; e.g., the brokerage may rent additional
machines during times of heavy load in order to run
additional servers. And, while the brokerage is con-
fident that it can protect these sites from corruption
while servers are executing on them, it cannot trust
that other sites, or the network by which the sites
communicate, will behave as expected. For instance,
corrupt traders may attempt to infiltrate the group,
alter or forge group communication, or tamper with
the group abstractions on which the consistency and
correctness of the service would rely. So, if the abstrac-
tions provided by the group oriented programming en-
vironment are not robust against malicious attack, it
To appear in Proceedings of the 1992 lEEF Symposium on Research in Security and Privacy.
is doubtful whether it should be used at all. More-
over, the brokerage is not willing to entirely trust all
of its own brokers, and thus needs some way to enforce
security policies even within the set of protected sites.
Generalizing from this example, we are concerned
with facilitating the construction of high performance,
fault tolerant applications on a secured and potentially
dynamic "island" of sites. We approach this task by
making common group oriented abstractions robust
on this island, despite malicious attacks against them.
A second goal is to provide support for group oriented
security policies within such an island. Third, since
applications may need to interact with less trusted
parties outside of this island, we feel it is important to
provide guarantees regarding the results of such com-
munication.
Another impetus to preserve process group abstrac-
tions in hostile environments is that the cryptographic
community has identified several practical security
needs in settings where groups occur naturally [7].
Proposed solutions (e.g., [10, 15, 8]), however, presup-
pose a group oriented infrastructure which cannot be
effectively provided in a hostile environment by cur-
rent systems. Secure group oriented foundations will
enable applications to more easily realize the benefits
of this research.
This paper presents a distributed security archi-
tecture to be integrated with group oriented systems
and, in particular, with the Isis toolkit [2].' Isis is a
toolkit for distributed programming that provides pr?
cess group and reliable group multicast abstractions.
With respect to Isis, the aims of this work are twofold.
The first is to weaken the execution model assumed by
Isis so that malicious behaviors are admitted, while
still preserving the abstractions provided by Isis. The
second is to enhance the Isis abstractions to be more
suitable for use in a hostile environment. And, of
course, we wish to accomplish these without unrea-
sonably degrading the performance of the toolkit.
The goal of this paper is to describe the ma-
jor features of our security architecture. More pre-
cisely, we discuss how our architecture addresses three
needs, namely for group oriented authentication, se-
cure methods for joining groups, and causal multi-
cast protocols that are appropriate in hostile envi-
ronments. We also propose a delegation and access
control scheme for use in group oriented systems. We
do not discuss key exchange protocols or specific cryp-
tosystems in detail. We instead focus on the mecha-
1This architecture is tailored to a reimplementation of the
Isis toolkit called Horns, named after the son of Isis in Egyptian
mythology. In this paper, we will use Horns terminology, which
may be unfamiliar to users of e&lier versions of Isis.
nisms we use to protect the abstractions that are fun-
damental in Isis and, we believe, in a group oriented
setting.
The rest of this paper is structured as follows. We
begin in section 2 with an informal description of the
abstractions provided by Isis. In section 3 we discuss
the system model for which Isis was designed and then
weaken this model to allow malicious behaviors. Sec-
tion 4 clarifies our goals and presents the three basic
aspects of our security architecture previously men-
tioned. Section 5 describes our group oriented delega-
tion and access control scheme. We end with a discus-
sion of the status of the system and future directions
of research.
2 The Isis abstractions
The basic abstraction provided by Isis is the process
gronp, which is simply a collection of processes with
an associated group address. Groups may overlap and
be nested arbitrarily, and processes may create and
join groups at any time. And, a process may be re-
moved from a group, either because it was perceived
to fail (i.e., crash) or because it requested to leave. A
group G can thus be seen as progressing through a se-
quence viewo(G), viewi(G),... of views satisfying the
following conditions.
o+ For all i, view?(G) c P, where P is the set of all
processes in the system.
o+ viewo(G) =
o+ For all i, view?(G) and view?+,(G) differ by the
addition or subtraction of exactly one process.
Members of a group learn about the membership of
the group through certain events. More precisely, exe-
cution of a process p is modeled as a sequence
of events, each corresponding to the execution of an
indivisible action. One such event is the delivery of
the i-th group view view?(G) of a process group G.
Views are delivered to processes in sequential order,
with the constraint that the i-th view of G is deliv-
ered to p only if p E view?(G). If the i-th group view
of G is delivered to p, then we say that p is in the i-th
group view until the (i + 1)-th view is delivered or p
is removed from the group.
The primary means of communication in Isis is
group multicast. (Point-to-point communication is
treated essentially as multicast in a static group of
size two, where any membership change destroys the
2
group.) A process in (some view of) a group can mul-
ticast to the group by specifying the group address as
the destination. Isis guarantees to processes certain
delivery properties regarding group multicasts. For in-
stance, all operational destinations eventually deliver
the message or, and only if the sender fails, none do.
And, all destination processes are in the same group
view when the message is delivered, and the set of
destination processes is precisely the members of that
view.
One guarantee of particular interest in this paper is
that messages are delivered in an order consistent with
potential causality. Informally, one message is said to
be cansally before another if the former was sent before
and could have affected the latter [16]. Causal deliv-
ery ordering has been shown to be crucial in systems
such as Isis that exploit asynchronous operations to
achieve high performance [1], because when messages
are asynchronously pipelined to destinations, a mes-
sage could be received at the destination site before
another causally before it. The danger is that, e.g.,
an update to a data structure could be delivered to
an application before tlie message initializing the data
structure. A delivery ordering that respects causality
avoids such problems.
To define the causal delivery ordering in our set-
ting, we introduce two more types of events that can
be executed by a process p in a group G: the multi-
cast of a message m to G, denoted mcast?(m, 6'), and
the delivery of a message m multicast to 6', denoted
deliverp(m, 6'). The potential causality relation is
defined as the transitive closure of the smallest rela-
tion satisfying the following conditions.
o+ For all i and p, e??
o+ For all m, p, q, and 6',
mcastp(m, 6') deliverq(m, 6').
Isis' causal delivery ordering property guaran-
tees that if mcastp(m, 6') mcastq(m', 6"), then
at any common destination r, deliverr(m, 6')
deliverr(m', 6"). In words, if the multicast of message
m causally precedes the multicast of message m',then
m is delivered before m' at any common destination.
The multicast primitive that provides this property is
called CBCAST and is a fundamental building block
on which other Isis abstractions are implemented [3].
To summarize, Isis provides process group and
group multicast abstractions. Notification of group
membership changes are coordinated with respect to
the delivery of group multicasts. And, multicast de-
liveries to a process are ordered causally to allow Isis
to safely exploit asynchronous communication.
3 The system model
The basic system model for which Isis was origi-
nally implemented is very benign. Informally, that
system consists of a set of sites that execute the set
P of processes. (Unless otherwise stated, throughout
this paper the term "process" refers to an application
process, and the term "site" refers to a workstation
running an operating system and, once added, Isis.)
Sites and processes may fail, but only by crashing,
and if a site fails then so do the processes residing
upon it. The sites communicate via an asynchronous
network: no bounds on message transmission delays
are assumed.
The system model considered in this paper is ob-
tained by weakening aspects of this model in various
ways, namely by allowing the network or sites to be
corrupted by an intruder. The intruder can engage in
any active network attack (including denial of message
service) and can view all network traffic. However, we
assume that the intruder is limited in these attacks by
the (conjectured) properties of the cryptosystems and
signatures schemes we employ. We also assume that
the intruder does not engage in traffic analysis attacks;
i.e., we do not consider sud? attacks here and assume
that encryption is sufficient to hide the contents of a
message from a network intruder. The reader should
see [30] for a survey of network attacks.
We also assume that sites may be corrupted by an
intruder during system execution. Once corrupted, a
site may exhibit arbitrarily malicious behaviors, again
limited by the cryptosystems and signature schemes
we employ. For simplicity, we assume in this paper
that once a site is corrupted, it remains so forever.
Intuitively, a corrupt site is one on which the operating
system or Isis code or data has been maliciously or
accidentally altered or replaced.
We make two assumptions about the operating sys-
tem running at an uncorrupt site. First, we assume
that it authenticates in a secure fashion the user iden-
tifiers of local processes.2 Second, we assume that it
provides protected, private address spaces for, and pri-
vate, authentic message passing between, all local sys-
tem and user processes. This includes the protection
This is a rather strong requirement, but the mechanisms
described in this paper facilitate its implementation. For exam-
pie, if smart-card technology is available, then each user and site
can be treated as an Isis group and the delegation mechanisms
of section 5 can be used to authenticate the user identifiers of
processes executed from remote sites in a fashion similar to that
of DSSA [ill. Even without such technology, the authentica-
tion mechanisms of section 4.1 provide a secure communication
channel between any two sites that facilitates the authentication
of user identifiers.
3
of virtual address spaces stored on external media.
In this paper we also assume that each uncorrupt
site maintains a local clock that is synchronized with
the clocks on all other uncorrupt sites. A clock syn-
chronization algorithm is currently being implemented
as part of a real-time extension of the Isis toolkit.
While a detailed discussion of this algorithm is out-
side the scope of this paper, we note that it is based
upon a time service which, with the authentication
mechanisms described in this paper and physical safe-
guards to ensure its integrity, can be adapted for use
in our system model.
Finally, we assume that the Isis failure detector and
name service behave according to specification (i.e.,
are not corrupt). These are services provided by Isis
and will be discussed briefly in sections 4.1 and 4.2,
respectively. The security of these services is a topic of
ongoing research; one possible approach is described
in [20].
4 Protecting the Isis abstractions
Informally, we would like to make the Isis abstrac-
tions described in section 2 robust in the system model
of section 3. In particular, we would like to ensure that
all processes in a group observe correct deliveries of
group views and messages. This is clearly impossible,
however, if a site hosting a group member is corrupt,
because that site could cause arbitrary events to be
observed in any order by any process it hosts. We
are thus faced with two reasonable options: we can
either attempt to guarantee the Isis abstractions in all
groups, but to only those processes that reside on un-
corrupt sites, or we can attempt to guarantee the Isis
abstractions only in groups that have no members on
an uncorrupt site.
We have opted for the latter for several reasons.
First, the latter approach is more consistent with our
original motivation, namely to enable a programmer to
construct a fault tolerant application on trusted sites,
despite the fact that the network or other sites can-
not be trusted. Second, the former could be achieved
only through great cost to the performance of the sys-
tem; e.g., all correct sites would be required to reach
consensus on the contents of each group multicast be-
fore delivering it to the application. Such an overhead
would be unacceptable to the type of applications for
which Isis is intended. Third, very few of the Isis ap-
plications we have seen could tolerate the corruption
of some group members, even if the Isis abstractions
were provided to the correct members. And, we ex-
pect that very few developers would be willing to pay
the performance penalty of making their applications
tolerant of such corruptions.
A consequence of this design decision is that pr?-
cesses residing on untrusted sites should not be al-
lowed to join a "trusted" group. In section 5, we
present a method by which access to groups can be
controlled. In those applications that require commu-
nication with processes on less trusted sites (e.g., the
trading service of section 1), we suggest that such com-
munication be performed in a point-t?point fashion
between the untrusted process and a single member of
the group. Then, for instance, the untrusted process
could multicast to the group by sending the message
to the member, which would multicast the message on
behalf of the process. This approach has the disadvan-
tage that a multicast from the untrusted site will be
somewhat slower. However, it is beneficial in that it
virtually eliminates any threat that the corrupt site
could pose to the consistency of the group members
(from the point of view of Isis); the one exception to
this is discussed in section 4.3.
Continuing, then, we restrict our efforts to process
groups that reside on uncorrupt sites. That is, let
sitesi(G) be the set of sites hosting the members of
view?(G), and let an uncorrupt group G be one such
that at any time during execution, if site 5 is cor-
rupt and viewi(G) is the current group view, then
5 ? sitesj(G). Then, in this work we enhance Isis
to ensure that if & is uncorrupt, then processes in
Ui view?(G) observe correct sequences of events ass?
ciated with group G, and "external" operations that
involve G, such as group joins and communication
with sites outside of G, can be performed with cer-
tain security guarantees. Henceforth, when we speak
about a process group, we assume that it is uncorrupt,
unless otherwise stated.
As mentioned in section 1, in this paper we focus
on three issues that are fundamental to our goals. To
avoid an indepth discussion of how the Isis abstrac-
tions are presented to processes, we will not describe
how the mechanisms we present here are applied to
implement specific abstractions (e.g., the delivery of
group views). Instead, we concentrate on more basic
problems that could undermine these abstractions and
that must be addressed in any system offering similar
functionality.
First, a necessary step is to develop a subsystem
that provides efficient authentication of group multi-
casts. This subsystem should allow a site in a group
(i.e., a site hosting a member of a group) to detect at-
tempts by an intruder to insert, alter or replay group
messages or to impersonate another site in the group.
4
With such a subsystem, a site in the group could rely
upon the authenticity of messages apparently from
other sites in the group. In addition, since altered
messages would be detected (and ignored), attacks on
the integrity of messages would become indistinguish-
able from lengthy message delivery times, as are denial
of message service attacks already. And, since Isis is
constructed for an asynchronous network, Isis would
behave safely under such attacks. (Intuitively, here we
are reducing these active network attacks to commu-
nication failures.) In section 4.1 we propose such an
authentication subsystem.
Second, the protocol by which a process joins a
group is crucial to the process group abstraction, be-
cause the joining site's perception of the group mem-
bership is directly dependent upon the security of the
join protocol. In Isis, when a process requests to join
a group, it specifies the group address. This address
is used by the process' site to send the appropriate re-
quest to the group, and it is necessary that the process'
site be able to authenticate the apparent response of
the group. A related issue that must be addressed is
how a process can obtain an authentic group address
for a group it wishes to join. In section 4.2 we discuss
these issues and extend our architecture to address
them.
Third, in section 4.3 we discuss the task of pre-
serving causality among multicasts in a hostile envi-
ronment. We argue that simply preserving causality
among messages in one or several uncorrupt groups
may not suffice for groups that must communicate
with less trusted principals. We then formulate the
specific causal guarantees we provide, and describe
protocols to implement them.
4.1 Multicast authentication
We introduce authentication mechanisms at the
lowest layer of the Isis toolkit, namely the Multicast
Transport Service (MUTS) [29]. A copy of MUTS re-
sides on each site, logically at the transport layer of
the ISO 051 Reference Model, and provides to the lay-
ers above it at-most-once, sequenced multicast com-
munication to other sites. MUTS provides these ab-
stractions while insulating the higher layers from the
particular transport protocol used, which may exploit
hardware multicast capability.
For our purposes, authentication must be intro
duced at the MUTS layer. Since MUTS is the lowest
layer of the Isis toolkit, we cannot introduce authenti-
cation mechanisms closer to the network, and because
Isis is designed to run on many different platforms,
we cannot rely upon authentication mechanisms be-
ing available at lower layers. It would be fruitless to
authenticate messages only at higher layers of the Isis
system, as then they could not rely upon the abstrac-
tions provided by MUTS. For example, a network in-
truder could then undetectably tamper with the infor-
mation MUTS uses to sequence messages.
Before presenting our authentication mechanisms,
we briefly consider how MUTS works. Each MUTS
layer maintains a current member list of sites for each
group it (or rather, its site) is in. A copy of MUTS
learns about changes to the site membership of a group
from the layer above it, which communicates with
other sites in the group and with the Isis failure detec-
tor [2, 21] to make this determination. When MUTS
receives a message from a higher layer to be multi-
cast to a group, it opens a connection to the members
of its current member list for that group, if one does
not already exist. MUTS then breaks the message into
packets, and hands these packets to the transport pro
tocol for transmission. A connection is associated with
exactly one group and is simply a logical end-toend
data path from the originating site to the other sites in
the originator's member list. If a site is removed from
the originator's member list, it is also removed from
the connection, but if a site is added to the origina-
tor's member list, the old connection is disassembled
and a new connection is negotiated for the new mem-
ber list. Each packet carries with it the connection
number and a sequence number for the connection.
Connection numbers are unique system-wide, and the
sequence numbers for a connection form an increas-
ing sequence. When the sequence reaches its upper
bound, the connection is disassembled and a new one
is negotiated.
Techniques for authenticating messages (or in this
case, packets) have existed in the literature for many
years. Traditionally, these methods have employed
encryption, but methods based upon pseudo-random
functions are also theoretically attractive. Informally,
a pseudorandom function f has the property that if
f is unknown, then it is computationally infeasible to
produce f(m) for any m with a probability of suc-
cess greater than random guessing, even after having
seen other (m', f(m')) pairs. Thus, given a family of
pseudo-random functions [fKlKEK, indexed by keys
from some key space K, two parties that share a se-
cret key K can authenticate messages between each
other by appending f?(rn) to each message m [22].
(In Isis, we will efficiently approximate this technique,
e.g., with one-way hash functions [27].)
For MUTS we generalize these ideas to take advan-
tage of hardware multicast capabilities that may be
5
exploited by the transport protocol. Instead of estab-
lishing a shared key for every pair of MUTS layers, we
establish a shared key per connection, called a connec-
tion key. The connection key is a secret held by the
sites involved in the connection and is used to authen-
ticate packets sent on the connection. When a connec-
tion is created, the site initiating the connection gen-
erates a new connection key K and distributes it, in a
fashion to be discussed below, to the sites on its mem-
ber list. Then, the multicast "m, 1?(m)" of packet m
on the connection can be verified at all destinations.
In addition, an application can request that its mes-
sage be encrypted, in which case any fragment of that
message included in packet m will also be encrypted
under K (e.g., using DES [6]). Provided that the con-
nection is fresh (i.e., established with a non-replayed
message), each destination can verify that m is not a
replay, because it contains the sequence number for
the connection. Here we do not detail the protocol
by which a connection is opened, although we remark
that the freshness of a connection is guaranteed by in-
corporating a timestamp into the connection initiation
message.
Because the establishment of a connection is a
somewhat frequent occurrence, it is important that a
connection key be distributed efficiently. The method
for distributing a connection key should, if possible,
require a single multicast and a single encryption (ver-
sus one encryption for each site on the originator's
member list). In Isis, we achieve this by employing
a group communication key (or just communication
key). A communication key is a shared key possessed
by all sites in the group. The communication key for
a group is created by the site hosting the first member
of the group, and as other processes join, it is given
to their sites as described below. The connection key
for a connection is thus communicated in a single mul-
ticast, encrypted with the communication key of the
group.
In an open network environment, key exchange
eventually requires the intervention of some a priori
trusted authority, which often takes the form of an
authentication service. In Isis we employ such a ser-
vice to establish secure channels by which communica-
tion keys can be distributed. We choose a public key
authentication service due to the security advantages
that can be achieved [9]. Associated with the authen-
tication service is a private key (known only to the
service) and a corresponding public key, The public
key is given to each site, along with the site's own site
key (a private key/public key pair), when it is booted.3
The boot procednre appropriate for each site in a particu-
Once booted, the site obtains from the authentication
service its certificate, which contains the identifier and
public key of the site and the expiration time of the
certificate, all signed by the private key of the authen-
tication service. Each site's certificate is subsequently
disseminated from the site itself, with the site con-
tacting the authentication service for a new certificate
when its certificate expires. The exact implementa-
tion of the authentication service is a topic of ongoing
research; one possible approach is described in [20].
A communication key is sent to a site after obtain-
ing the site's certificate and encrypting the communi-
cation key under the site's public key. This exchange
takes place as part of the group join protocol, which
will be described in the next section. We emphasize
that no interaction with the authentication service is
required when a communication key is distributed.
To summarize, we propose to protect group com-
munication via a hierarchical key distribution scheme.
The initial keys in the system are the site keys. A
group communication key is created when the group
is created and distributed using site keys when group
joins take place. This communication key, in turn, is
used to establish connection keys within the group.
The benefits of this scheme are many. First, the use
of shared keys and efficient algorithms at the level of
connections should result in minimal performance cost
for group multicasts, which are by far the most com-
mon operations in most Isis applications today. Sec-
ond, since a different key is used per connection, the
lifetime of a connection key is limited, and a different
key is used for each multicasting source. This should
limit an intruder's ability to cryptanalytically attack
connection keys. Third, the more costly public key
operations are performed less frequently, when groups
are joined.
Finally, we emphasize that sites hold connection
keys, communication keys, and private keys of sites;
user processes do not. This prevents a malicious user
process on an uncorrupt site from improperly dis-
tributing or using these keys. Moreover, when a pr?
cess is removed from a group, the site on which it re-
sides can destroy the communication and connection
keys that it held on behalf of the process. By doing so,
if the site is subsequently corrupted, then the intruder
will not be able to masquerade as a group member. If
lar setting is dependent on many factors, such as the physical
security of the site, whether the site is diskless, and the role of
the site in the system. Thus, a complete discussion of this issue
is outside the scope of this paper. However, the hoot proce-
dure used at each site should prevent an intruder from booting
the site with false operating system or Isis code or with a false
authentication service public key.
6
the entire site crashes, we rely upon the loss of volatile
storage to eliminate all keys from memory.
4.2 Joining groups
The protocol by which a process joins a group is
crucial to the process group abstraction, because if
this is not secure, an intruder may cause the process
to observe fallacious group views and thus to act in-
correctly. In Isis, the protocol for a process to join a
group is as follows. First, the requesting process spec-
ifies the group address of the group it wishes to join.
This address contains the address of a group contact,
which is a distinguished site in the group. The pr?
cess' site sends the join request to the group contact
and, once admitted, is sent a list of group members
by some site in the group. Note that if the requesting
site includes its certificate in the request, then the site
that returns the member list can also return the group
communication key encrypted under the site's public
key.
In order for the join protocol to be secure, the pr?
cess site must be able to authenticate the response as
being from a site in the group. And, since the pr?
cess site does not know what sites are in the group,
the site keys of section 4.1 do not suffice for this. To
facilitate the required authentication, we introduce a
new type of key. When a group is first created, the ini-
tial site in the group creates a public key/private key
pair, the private key of which is called the group key
(or just the private key of the group). The group key
is then communicated to group members' sites just as
the communication key is, as part of the join protocol.
While these operations will reduce the performance of
group creates and joins, they have no effect on the
performance of group communication. Like communi-
cation keys, the group key is destroyed by a site when
all group members it hosts are removed from the group
(or when the site itself fails). We utilize this new type
of key by including the public key of the group in the
group address. This enables a joining process' site to
verify a site's membership in the group by challenging
it to prove possession of the group key.
Of course, the success of this scheme hinges on the
ability of a process to obtain the authentic address of
a group it wishes to join; for the remainder of this sec-
tion we address this issue. Other than by creating the
group, in Isis a process can obtain a group address in
either of two ways: it can simply receive it from an-
other application process, or if the group is registered
at the Isis name service, then the process can request
the group address from the name service by specifying
the group name. The name service is a fault tolerant
Isis service that implements a hierarchical name space,
like that of a file system except with group addresses
(or other information) at the leaves instead of files. A
group name is a path from the root to a leaf in that
hierarchical name space. A process can register the
group address under some name at the name service
anytime after the group is created. A group that has
not been registered with the name service is an anony-
mous group, and the address of an anonymous group
can be obtained only from another application process
(or by creating the group).
If a process receives an address from another appli-
cation process, it can trust that address only as much
as it trusts the other process. In particular, if it can
be verified that the sending process is a member of
either a "trustworthy" process group or a group that
was delegated by such a group (see section 5), then the
address may be perfectly acceptable. But, to verify
the claims of the sending process, the receiving pr?
cess must obtain the group addresses (i.e., the pub-
lic keys) of the delegating groups and the group of
which the sending process claims to be a member. So,
in many cases verification of group addresses received
from other processes requires that the verifying pr?
cess be able to obtain authentic group addresses from
the name service.
Thus, the ability to obtain authentic group ad-
dresses through the name service is fundamental to
the security of group joins. The authentication mech-
anisms of section 4.1 can easily be adapted to allow a
site to authenticate the name service, e.g., by having
the name service sign group addresses with its pri-
vate key and having the authentication service pro-
duce a certificate for the name service. However, as
it stands there is still no reason for the process to be-
lieve an address obtained from the name service, be-
cause the name service cannot verify the integrity of
the addresses it receives and stores. To compensate
for this problem, we allow processes to impose access
controls upon the directories of the hierarchical name
space. That is, when a process creates a directory of
the name space, it specifies access control policy for
the directory that restricts which processes can reg-
ister a group or create a directory in that directory;
in section 5, we describe a method by which this ac-
cess control policy can be represented and enforced.
The name service will allow only an authorized pr?
cess (residing on an authorized site, which can be au-
thenticated as in section 4.1) to register a group in the
directory. A process can then obtain a group address
from a directory it "trusts" based upon the directory's
owner and access control policy.
7
4.3 Causal multicast
As previously described, the CBCAST protocol im-
plements Isis' causal delivery ordering property and is
central to the Isis system. For pedagogical reasons,
we begin this section with two illustrations of causal
multicast ordering.
Consider first an instance of single group causality,
illustrated in part (a) of figure 1. This shows a single
process group with four members Pi, P2, P3 and p?,
residing respectively on sites 5i, ?2, 53 and 54. Time
increases down the vertical lines, and a group of arrows
emanating from a point on a vertical line represents
a CBCAST (i.e., causal multicast) to the group. An
arrow ending at the vertical line below a process indi-
cates the delivery of the multicast represented by the
arrow to the process. (We have omitted drawing the
delivery of the message to the sending process, which
can be done immediately.) In this example, Pi multi-
casts m1 to the group, and after ?2 delivers it to P2, P2
multicasts m2 to the group. Causality requires that
m2 be delivered to p? after m1, as indicated in part (a)
of figure 1. The method by which 54 decides upon this
delivery ordering depends on the particular CBCAST
protocol used.
The more complex flavor of causality is called mul-
tiple group causality, illustrated in part (b) of figure 1.
In this example the four processes are organized into
three process groups G1, G2 and G3, respectively in
views [P1,P2,P4J, [P2,P31 and fp?,p?]. First Pi mul-
ticasts message mi to group Gi. After mi is delivered
to P2, P2 multicasts m2 to G2, and upon delivery of
m2 to P3, P3 multicasts m3 to G3. Multiple group
causality requires that m3 be delivered to P4 after mi,
as indicated in the figure.
The CBCAST protocol is implemented above the
MUTS layer. Thus, given the authentication mecha-
nisms of section 4.1, the CI3CAST protocol can rely
upon the MUTS abstractions (i.e., at-most-once, se-
quenced multicast) in an uncorrupt group. As we will
see in a moment, this enables us to use certain Isis
protocols originally designed for benign environments
to provide causal orderings among messages in a set
of uncorrupt groups.
However, we argue that for applications that must
interact with untrusted principals (e.g., the trading
service of section 1), this guarantee may not suffice.
To see why, suppose that 53 is corrupt in part (b)
of figure 1. Depending on the particular CBCAST
protocol used, it may be possible for 53, by not fol-
lowing the protocol, to trick 54 into delivering m3 to
P4 before m1, as in part (c) of figure 1. Intuitively,
53 might do this by omitting to include information
on m3 that conveys m3s causal relationship with mi.
Such an attack is possible with several of the causal
multicast protocols described in [3]. The danger in this
is apparent in the OTC example of section 1: suppose
that Gi is the replicated trading service, m1 contains
a client's request to purchase stock, and m2 reflects
that (intended) purchase. Then, after seeing m2, the
intruder at 53 could attempt to effect the delivery of a
request m3 for the same stock before mi at replica P4
of the service, in order to raise the apparent demand
for that stock and thus the price offered to the correct
client. Therefore, if a causal delivery ordering between
mi and m3 is not enforced, a type of "insider trading"
may occur.
This problem illustrates a form of attack that must
be considered in any system that attempts to detect
causal orderings among messages. We call this type of
attack a backdating attack. Informally, a message m is
said to be backdated if there exists another message m'
such that m is causally after (i.e., could have been af-
fected by) m', but at some correct site, it appears that
m is not causally after ?? So, in the example above,
the message m3 is backdated, because the causality
detection mechanisms at 54 could not detect that m3
should not be delivered until mi was. Naturally, there
is a complementary form of attack called postdating,
although in general it poses no threat to applications
concerned with potential causality only. A more for-
mal discussion of postdating and backdating attacks
with respect to various forms of causality is outside the
scope of this paper and will be presented elsewhere.
Message encryption is, in general, a prerequisite to
preventing backdating attacks, because the intruder
can eavesdrop on all messages and can initiate activ-
ity from a corrupt site or malicious process based upon
the information so observed. To illustrate this, sup-
pose that in the previous trading service example, the
intruder observes mi on the network and sends m3
based only upon information obtained from mi (i.e.,
remove m2 from the figure). Now we have precisely
the same scenario as before, in the sense that m3 must
be delivered to P4 after mi in order to prevent the "in-
sider trading" previously described. However, there is
no apparent way for 54 to detect this causal relation-
ship. This problem can be prevented by encrypting
mi, which prevents an intruder from viewing mi's con-
tents. Whether encryption is justified in a specific case
depends upon the particular application and message,
although for simplicity we assume in the remainder
of this section that all communication is encrypted as
described in section 4.1.
The set of causal guarantees we provide prevents
8
Figure 1: Causal Multicast
Pi			p4
P2
pi
(a) Single group causality
(b) Multiple group causality
backdating attacks, in addition to providing the nor-
mal causal guarantees in uncorrupt groups. To specify
these guarantees, we first introduce some terminology.
We say that a message is receivedat a site when MUTS
at that site gives the message to the CBCAST layer,
and we further stipulate that a message is receivedat
the site from which it is multicast immediately after
it is multicast. It is also convenient to redefine
to avoid making any assumptions regarding events at
corrupt sites or the semantics of multicasts in corrupt
groups. Henceforth, is the smallest relation satis-
fying the following conditions.
For any i and p, if e?? and e??+1 are executed on an
uncorrupt site, then e??
For any p, q, m and G, if G is uncorrupt and
if mcast?(m, G) and deliverq(m, G) are exe-
cuted on uncorrupt sites, then mcastp(m, G)
deliverq(m, G).
As before, is defined as the transitive closure of
?. Suppose that mcast?(m, G) mcastq(m', G'),
where G is uncorrupt. Note that by the definition
of ?, p and q reside on uncorrupt sites (when these
events are executed), although G' may be corrupt. Let
r be any process to which m is delivered in G. Then,
we provide the following guarantees.
o+ If G' is uncorrupt and m' is delivered to r in G',
then m' is delivered to r after m.
o+ If G and G' are different groups and a message
m is (i) received at r's site after the multicast of
9
(c) Causality violated
m' from q's site but (ii) delivered to r before m,
then iii was multicast before m' was multicast.
The first guarantee is simply the usual causal
guarantee of section 2 applied to communica-
tion among uncorrupt groups: deliverr(m, G)
deliverr (m', G'). The second guarantee is intended
to prevent backdating attacks. To see this, suppose
that G' is corrupt. Clearly any message vi sent on
the basis of information the intruder obtains from vi'
can be received at r's site only after vi is multicast.
And, if the attempt to backdate vi to before vi were
successful, then vi would be delivered before vi. How-
ever, this guarantee says that if both of these condi-
tions hold, then the intruder must have sent vi before
seeing vi'. For instance, in the OTC example of figure
1, this prevents vi3 (= iii) from being delivered before
vi1 (--H--H vi) at s4 (= r's site), because vi3 is received at
s4 after the multicast of vi2 (= vi').
We provide these guarantees through a combina-
tion of several protocols described in [3]. Here we de-
scribe protocols that suffice when group memberships
do not change; in the remainder of this section we treat
each (uncorrupt) group as simply a static set of pr?
cesses. (Although we synchronize communication on
view changes precisely as in [3], this introduces com-
plexities that are best omitted for the sake of brevity.)
The protocols described here also require that commu-
nication with corrupt sites be performed in a point-t?
point fashion, as suggested at the beginning of section
4. We have extended these protocols to provide the
above guarantees even without this requirement; one
such protocol is described in appendix A.
We begin with the vector timestamp protocol for
a single group, which provides single group causality
only. More precisely, suppose we define ?c for an un-
corrupt group G to be the smallest relation satisfying
the following conditions.
o+ For any p E G and any i, e?? ?G
o+ For any m and any p, q E G,
mcastp(m, G) ?G deliverq(m, G).
As usual, let ?G denote the transitive closure of
?G The vector timestamp protocol guarantees
that if mcastp(m, G) HG mcastq(m', G), then
deliverr(m, G) ?G deliverr(m', G) at any common
destination r.
In this protocol, a vector timestamp VT?(m) is ap-
pended to each multicast m in group G by the site
multicasting m. Vector timestamps are assigned to
messages in such a way that VT?(m) ? VT?(m') iff
mcastp(m, G) ?G mcastq(m', G), where ? is an ir-
reflexive partial order on the timestamps. When a
message is received in a group G at a site, it is placed
in the delivery sequence for a destination immediately
before the earliest message rn' already in that de-
livery sequence such that inI was received in G and
VTc(m) ? VT?(m'); if no such m' exists, then rn is
placed at the end of the delivery sequence. So, mes-
sages are delivered in order of receipt, except when
that would result in a violation of single group causal-
ity. If G is a static group of size two created for point-
t?point communication, then messages in G can be
delivered in the order they are received, and vector
timestamps are not used in G; i.e., a message received
in G is simply placed at the end of the delivery se-
quence for the destination.
We extend this protocol to provide the above multi-
ple group guarantees by using the conservative proto-
col. In this protocol, a multicast is defined to be stable
if it has been received at all of its destination sites. A
group G is active for a process p if p's site does not
know of the stability of a multicast to 0 either sent
by or delivered to p. The conservative multicast rnle
states that a process p may multicast to group 0 if
and only if 0 is the only active group for p or p has
no active groups. If p attempts to multicast when this
condition is not satisfied, the multicast is delayed, and
during this delay no multicasts are delivered to p. So,
in part (b) of figure 1, ?2 simply delays sending m2 un-
til it knows that m1 has been received by 54, and then
54 delivers m1 before m3, because they were received
in that order.
The proof that these protocols satisfy the first guar-
antee is given in [3]. We now argue that these protc>?
cols provide the second guarantee. Suppose that 0
and 0' are different groups, and that m is received at
r 5 site 5r after m was multicast, but delivered to r
before m. By the conservative protocol, m was sta-
ble and thus received at 5r before m' was multicast.
Therefore, m must have been received at 5r after m.
By the above protocol descriptions, m could have been
delivered before iii only if (i) m were multicast in 0
and VT?(m) ??VT?(m), or (ii) m were multicast in
another group 0, and for some m previously received
in 0 and placed before m in the delivery sequence,
? VT0(m). Now, suppose for a contradic-
tion that m was actually sent after (or at the same
time that) m' was multicast. Possibility (i) could not
happen due to the correctness of the vector timestamp
protoco) for group 0, and similarly (ii) could not hap-
pen if 0 were uncorrupt. So, 0 must be corrupt. But,
assuming that 0 is really a point-t?point connection,
vector timestamps in 0 are not used, and (ii) could
not happen. Thus, m must have been sent before m'.
5 Delegation and access control
As stated before, the work of section 4 presupposes
uncorrupt groups (except where otherwise stated). In
light of this, it is obvious that in real systems, access
to groups must be restricted. In the "secure island
of sites" model discussed in section 1, access control is
obviously needed to prevent a process on an untrusted
site from joining a group. Access control is also needed
within the secured island, because while the sites in
that island are assumed to be secure, the processes
they execute should not necessarily be trusted to join
any group whatsoever.
In this section we propose an access control scheme
based upon access control lists (ACLs) that we plan
to employ in our system. We have chosen ACLs over
classic capabilities to avoid several well-known short-
comings of capabilities, such as difficulties involved in
revoking access rights, the inability to specify denial of
access rights, and the need to confine capability prop-
agation. And, while in some settings these problems
are offset by the relative efficiency of capabilities, we
have found that in majority of Isis applications, group
joins are infrequent in comparison to other group op-
erations (e.g., multicasts). Thus, we expect that the
economy of capabilities would impact overall system
performance only minimally. The scheme we propose
here is sufficiently powerful to be used as the sole
means to control access to groups, although it could
10
also easily be adapted for use in a hybrid scheme (e.g.,
[12]).
The straightforward criteria on which to restrict ac-
cess to groups are the owner and site of the process
requesting access. That is, when a group is created,
the creating process would specify a set (i.e., ACL)
of (owner, site) pairs that indicates the processes that
would be allowed to join the group. While this may
suffice for many applications, there may be some for
which this is insufficient. Consider an extension of the
OTC example of section 1 in which a client group au-
thorizes the trading service to purchase certain stocks
with funds in the client's bank account. Suppose that
the service must then send a representative process to
a group established by the client's bank to arrange the
fund transfer for the stock purchase.4 But, the bank
will admit this process to the group only if the process
has been duly authorized by one of the bank's clients.
In this case, determining whether to admit the pro-
cess based upon its owner (e.g., an individual broker)
and hosting site is insufficient for two reasons: this in-
formation neither convinces the bank group that the
process represents the trading service nor conveys the
authorization to access the client's account.
This flavor of authorization is related to many con-
cepts that have appeared in the literature in recent
years, including anthentication forwarding [26], cas-
caded anthentication [25], and delegation [11]. Infor-
mally, each of these terms connotes the means by
which one party confers access rights to another, as
exemplified by the client delegating authority to the
trading service in the previous example. Delegation
in a group oriented system is different from that in
other systems only in that groups are delegating and
being delegated. In practical terms, this means that
groups need to be authenticated. Fortunately, we al-
ready have the mechanisms to do this, namely group
keys and the name service introduced in section 4.2.
The approach we take to delegation is best illus-
trated by an example. Suppose that group Gi wishes
to delegate some authority to group G2. To do so,
some member of G1 causes the credential
Gi,Ti,G2,S1(Gi,T1,G2)
(1)
to be produced, where "Ti" is the time at which this
credential expires, "S1,, denotes the signature function
of G1 (i.e., signature with the private key of Gi), and
In practice, the representative would probably request to
become an Isis client of the bank group. Isis would then invis-
ibly create another group containing the client and the group
members. The access control scheme presented in this section
is particularly well-suited to restricting client access, although
for simplicity we will explain it in terms of member access only.
"Gi" and "G2,, identify groups G1 and G2, respec-
tively, either by address or name. Intuitively, a mem-
ber of G2 can present (1) to another party to prove
that Gi has delegated some access rights to G2 until
time T1; in general, the access granted to members of
G2 based on (1) is left to the discretion of individ-
ual object monitors. Any party can verify (1) with
the address of Gi, which contains Gi `s public key (see
section 4.2). A process in G2 can delegate further to
group G3 by forming
G1,T1,G2,T2,G3,S2(S1(Gi,T1,G2),T2,G3).			(2)
(In the notation of (2), we are assuming that the sig-
nature scheme allows any party possessing the pub-
lic key of G2 to invert S2(S1(Gi,T1,G2),T2,G3) to
obtain Si(Gi,Ti, G2), T2, G3.) This credential should
be considered valid until time min[Ti, T2]. Of course,
G3 could delegate yet further in a similar fashion, and
in general, credentials could become arbitrarily long.
This delegation scheme is similar to that in [25], and
the reader is referred there for a general discussion of
its features.
The choice of whether to delegate to a group name
or a group address has subtle implications. If a delega-
tion is made to a group address (e.g., if "G2,, is a group
address in (1)), then only the group that possesses the
private key corresponding to the public key in that
group address can utilize that delegation. However, if
a delegation is made to a group name, then any group
that is registered under that name before the delega-
tion expires can possibly exploit it. We expect that
both types of delegation will be useful to applications.
For instance, in the previous OTC example, the client
might delegate to the name of the trading service, if it
wants the "current" trading service, whatever group
that may be, to perform the transaction for it. The
trading service, however, may delegate to the address
of a satellite group that will handle the transaction
with the bank. By delegating to a group name, the
delegator implicitly trusts the directories that are pre-
fixes of the name to allow only "trusted" groups to be
registered under the name to which it delegated au-
thority. Below we will describe a scheme that can be
used to control access to directories.
The method by which a delegating group identi-
fies itself is also important. This is true because the
delegating group can restrict what access rights are
transferred to the delegated group by identifying it-
self appropriately. This is known as delegating by
roles and has been used in other delegation schemes
(e.g., [11,17]). Intuitively, associated with each role
11
of a group is some subset of the access rights that the
group is allowed to delegate to others. When a group
delegates the authority of a role, the authority trans-
ferred to the delegated group is at most that of the
role, and not of the delegating group. So, in the OTC
example, the client group could delegate authority to
the trading service under a role that was used to estab-
lish the bank account and that would be useless, e.g.,
for reading the client's mail. As another example, cre-
dential (1) could represent a referral made by a bank
group G1 for a client G2, which is required before the
bank's loan service will negotiate with the client. In
this case, G1 would probably delegate by a role with
which no access rights of Gi, per se, are associated
but that nevertheless indicates the needed referral. In
our setting, a role corresponds to just another group
name or group address. That is, a group can create
roles for itself by registering other names for the group
with the name service or by "duplicating" the group
to obtain several group addresses (i.e., public keys).
This delegation scheme extends easily to an ac-
cess control scheme for group membership as follows.
Replicated at each site in a group is a set of delegation
templates in addition to the set of (owner, site) pairs
previously described. Each delegation template is a
list gig? where each g? is either a group name
or address. (This does not imply that a group must
know in advance the addresses or names of all groups
that should appear in its delegation templates. The
method of specifying these templates could employ,
e.g., wild cards.) A credential
Gi, TiGm--Hi, Tm?i, Gm, Sm--Hi(. . .)			(3)
is said to match the delegation template ..... . ,
if m > n and for all j satisfying 1 < 5 < n,
Gm--Hn+j = g?. (Here, two addresses are equal if they
contain the same public key.) That is, the credential
in (3) matches the template g1g? if the creden-
tial ends with a sequence of delegations beginning with
g1, followed by g2, and soon, and ending with q?. In-
tuitively, the credentials that match some delegation
template of a group are those that the group accepts
as legitimate patterns of delegation.
Given sets of delegation templates and (owner, site)
pairs, access to a group is controlled as follows. If the
group contact receives credential (3) embedded in a
request from some process p to join the group, p is
allowed to join if and only if all of the following hold.
The authenticity of credential (3) can be verified
with the appropriate group addresses (i.e., public
keys).
o+ p's site can vouch that p is in Gm (by illustrating
knowledge of the private key for Gm).
o+ Message (3) matches a delegation template for the
group.
o+ None of the delegations in message (3) have ex-
pired.
o+ The (owner, site) pair of p is listed in the set of
(owner, site) pairs for the group.
The group contact obtains any group addresses it
needs to check these conditions from the name service
(or from the credential itself).
We are currently considering extensions to this
scheme to enable the group being joined to automat-
ically limit the duration for which an admitted pr?
cess is allowed to remain a member. These limitations
could be based upon the credential used by the process
to gain admittance and could vary depending on the
meaning assigned to the credential by the application.
For instance, depending on the meaning of (3), in the
above scenario p could be allowed to remain a member
(i) indefinitely, (ii) until time min(T1, .. . , Tm?i1 is
reached, (iii) until p is removed from Gm, or (iv) until
either (ii) or (iii) occurs. In cases (ii), (iii), or (iv), p's
site could remove p from the group when the appropri-
ate condition occurs. Which of (i)-(iv) is chosen for a
particular joining process could be determined on the
basis of which delegation template and (owner, site)
pair were matched to be admitted. Other extensions
to this access control scheme are being considered but
will not be discussed here.
This access control mechanism can be extended to
objects other than groups. We have already seen one
need for this, namely the directories of the hierarchi-
cal name space implemented by the name service de-
scribed in section 4.2. As in many file systems, a name
service directory has three natural types of access to
it, namely search, read and write. So, as when cre-
ating a group, a process can specify when creating a
directory in the name service a set of delegation tem-
plates and a set of (owner, site) pairs for each of these
types of access. A request to perform an operation
on a directory would then be allowed subject to the
above five conditions on the requesting process and
the credential it supplies.
6 Conclusion and future work
In this paper we have described a security architec-
ture for use in the Isis toolkit, but structured in such
12
a way that most mechanisms should also be useful
in other group oriented settings. The major features
of the security architecture include a group oriented
authentication subsystem, secure methods for joining
groups, and protocols that provide certain causal de-
livery ordering guarantees. In addition, we have pr?
posed an access control scheme based upon delegation
for use in group oriented settings.
Implementation of the basic mechanisms has begun
at Cornell University, in conjunction with the reimple-
mentation of Isis. This implementation should provide
valuable insight into the efficiency of our architecture
and mechanisms, and it is also forcing us to consider
user interface issues. In addition, we are in the pr?
cess of developing the necessary information exchange
protocols.
Future work on this system is heading in several
directions. We are considering several different exten-
sions to the design of the system. In particular, we
are currently considering ways to employ the basic ar-
chitecture described here at multiple security levels, as
would be appropriate if islands of sites were secured at
different levels. However, we are still unclear as to the
consequences of such a design. We are also considering
techniques to recover, e.g., after an intruder has infil-
trated a group. Finally, we are exploring techniques
for building secure, fault tolerant applications, given
the secured abstractions provided by this architecture.
Acknowledgements
We are deeply appreciative of the distributed
systems group at Cornell University for contribut-
ing many interesting discussions regarding this re-
search. In particular, we thank Navin Budhiraja,
Thshar Chandra, Robert Cooper, Brad Glade, Cliff
Krumvieda, Keith Marzullo, Aleta Ricciardi, Patrick
Stephenson, Sam Toueg, and Robbert van Renesse.
Richard Platek and Raphael Yahalom also provided
helpful discussions. Mark Steiglits developed a mecha-
nism for authenticating user identifiers under Isis; this
work did not become a permanent part of the system
but was a useful source of insight. Finally, we thank
the anonymous referees for many useful comments.
References
[1]
BIRMAN, K. P., CoOPER, R., AND GLEESoN
B. Design alternatives for process group mem-
bership and multicast. Tech. Rep. 91-1257, De-
partment of Computer Science, Cornell Univer-
sity, Dec. 1991.
[2] BIRMAN, K. P., AND JoSEPH, T. A. Reliable
communication in the presence of failures. ACM
Transactions on Computing Systems 5, 1 (Feb.
1987), 47--H76.
[3] BIRMAN, K. P., SCHIPER, A., AND STEPHEN-
SON, P. Lightweight causal and atomic group
multicast. ACM Transactions on Computing gus-
tems 9, 3 (Aug. 1991), 272--H314.
[4] BIRRELL, A. D. Secure communication using
remote procedure calls. ACM Transactions on
Computing Systems 3,1 (Feb. 1985), 1--H14.
[5] CHERITON, D. R., AND ZwAENEPOEL, W. Dis-
tributed process groups in the V kernel. ACM
Transactions on Computing Systems 3, 2 (May
1985), 77--H107.
[6] Data encryption standard. National Bureau of
Standards, Federal Information Processing Stan-
dards Publication 46, Government Printing Of-
fice, Washington, D. C., 1977.
[7] DEsMEDT, Y. Society and group oriented cryp-
tography: A new concept. In Proceedings of
CRYPTO `87 (Aug. 1987), pp. 120-127. Pub-
lished as Lecture Notes in Computer Science 293.
[8] DESMEDT, Y., FRANKEL, Y., AND YUNG,
M. Multi-receiver/multi-sender network security:
Efficient authenticated multicast/feedback. In
Proceedings of IEEE INFOCOM (May 1992).
[9] DIEFIE, W. The first ten years of public-key cryp-
tography. Proceedings of the IEEE 76, 5 (May
1988), 560--H577.
[10] FRANKEL, Y. A practical protocol for large
group oriented networks. In Proceedings of EU-
ROCRYPT `89 (Apr. 1989), pp. 56-61. Pub-
lished as Lecture Notes in Computer Science ?34.
[11]
[12]
GASSER, M., AND McDERMOTT, E. An archi-
tecture for practical delegation in a distributed
system. In Proceedings of the IEEE Symposium
on Research in Security and Privacy (May 1990),
pp. 20--H30.
GONG, L. A secure identity-based capability sys-
tem. In Proceedings of the lEFE Symposium on
Research in Security and Privacy (May 1989),
pp. 56--H63.
13
[13] KAAsHoEK, F. M., AND TANENBAUM, A. 5.
Group communication in the Amoeba distributed
operating system. In Proceedings of the IFEE In-
ternational Conference on Distributed Computing
Systems (May 1991), pp. 222--H230.
[14] LADIN, R., LIsKov, B., AND SHRIRA, L. Lazy
replication: Exploiting the semantics of dis-
tributed services. In Proceedings of the ACM
Symposium on Principles of Distributed Comput-
:ng (Aug. 1990), pp. 43--H57.
[15] LAIH, C. 5., AND HARN, L. Generalized
threshold cryptosystems. In Proceedings of ASI-
ACRYPT `91 (Nov. 1991).
[16]
[17]
[18]
[19]
[20]
[21]
[22]
LAMPORT, L. Time, clocks, and the ordering of
events in a distributed system. Communications
of the ACM 21, 7 (July 1978), 558--H565.
LAMPsoN, B., ABADI, M., BURRoWS, M., AND
WoBBER, E. Authentication in distributed sys-
tems: Theory and practice. In Proceedings of the
ACM Symposium on Operating Systems Princi-
ples (Oct. 1991), pp. 165--H182. Published as ACM
Operating Systems Review 25, 5.
OUSTERHOUT, J. K., ScELzA, D. A., AND
SINDHU, P. 5. Medusa: An experiment in dis-
tributed operating system structure. Communi-
cations of the ACM 23, 2 (Feb. 1980), 92--H105.
PETERSoN, L. L., BUcHHoLz, N. C., AND
ScHLIcHTING, R. D. Preserving and using con-
text information in interprocess communication.
ACM Transactions on Computing Systems 7, 3
(Aug. 1989), 217--H246.
REITER, M. K., AND BIRMAN, K. P. How to
securely replicate services. Submitted for publi-
cation, Jan. 1991.
RICCIARDI, A. M., AND BIRMAN, K. P. Us-
ing process groups to implement failure detection
in asynchronous environments. In Proceedings of
the ACMSymposium on Principles of Distributed
Computing (Aug. 1991), pp. 341--H351.
RIVEST, R. L. Cryptography. In Handbook of
Theoretical Computer Science, Volume A, Algo-
rithms and Complexity, J. van Leeuwen, Ed. El-
sevier Science Publishers B. V., 1990, ch. 13,
pp. 717--H755.
RoZIER, M., ETAL. Overview of the Chorus dis-
tributed operating systems. Tech. Rep. CS/TR-
90-25, Chorus Systemes, Apr. 1990.
[24] SATYANARAYANAN, M. Integrating security in a
large distributed system. ACM Transactions on
Computing Systems 7, 3 (Aug. 1989), 247--H280.
[25] SoLLINS, K. R. Cascaded authentication. In
Proceedings of the IFEE Symposium on Research
in Security and Privacy (Apr. 1988), pp. 156--H163.
[26] STEINER, J. G., NEUMAN, C., AND SCHILLER,
J. I. Kerberos: An authentication service
for open network systems. In Proceedings of
the USENIX Winter Conference (Feb. 1988),
pp. 191--H202.
[27] TSUDIK, G. Message authentication with one-
way hash functions. In Proceedings of IEEE IN-
FOCOM (May 1992).
[28]
[29]
[30]
TYGAR, J. D., AND YEE, B. 5. Strongbox. In
Camelot and Avalon, A Distributed Transaction
Facility, J. L. Eppinger, L. B. Mummert, and
A. Z. Spector, Eds. Morgan Kaufmann, San Ma-
teo, California, 1991, ch. 24, pp. 381--H400.
VAN RENESSE, R., BIRMAN, K., GLADE, B.,
AND STEPHENSoN, P. Reliable multicast be-
tween micro-kernels. In Proceedings of the
USENIX Microkernels and Other Kernel Archi-
tectures Workshop (Apr. 1992).
VoYDoCH, V. L., AND KENT, 5. T. Secu-
rity mechanisms in high-level network protocols.
ACM Computing Surveys 15, 2 (June 1983)135--H
171.
A Causal multicast, continued
In this appendix, we describe a modification to the
CBCAST protocol described in section 4.3 that pro
vides the causal guarantees described there without
requiring that communication with corrupt sites be
only point-topoint. By removing this requirement, we
provide somewhat stronger causal guarantees to, e.g.,
a process that finds itself in the intersection of uncor-
rupt and corrupt (non-point-topoint) groups. How-
ever, this protocol does not directly provide any other
guarantees in a corrupt group, and so processes that
require other guarantees should continue to communi-
cate with potentially corrupt sites in a point-topoint
fashion only. We assume that group memberships (of
uncorrupt groups) are static, as before, and we treat a
group as simply a set of processes. Again, the exten-
sions to handle group view changes are precisely those
14
[23]
in [3], although we omit them for the sake of brevity.
The relations and ??? are defined as in section 4.3.
The essential modification to the protocol of section
4.3 occurs in the placement of received messages in a
destination's delivery sequence. When a message m is
received at a site, it is simply placed at the end of the
delivery sequence. Then, beginning with the earliest
undelivered message in the sequence, the sequence is
stepped through, and the following rule is applied in
turn to each message m' (until rn is reached): if m'
was received in the same group G as m and VTG (in) ?
VTG(m'), then in' is moved to the back of the delivery
sequence. The placement of in and this processing of
the sequence are done atomically, in the sense that no
new messages are delivered or added to the delivery
sequence until both are complete. We claim that with
no further modifications, this new protocol provides
the two guarantees of section 4.3.
We begin by sketching the proof of the second guar-
antee. Suppose that G and G' are different groups,
and that ?5? is received at r's site 8r after in1 was mul-
ticast. By the conservative protocol of [3], in was sta-
ble before in' was multicast, as was any in such that
mcastq(in, G) ?o mcastp(in, G). Therefore, once
in' was multicast, in was already received at 5r and
could never again be moved back in the delivery se-
quence for r. Since in as received after in' is multicast,
it follows that in must be delivered to r after in. So,
the antecedent of the second guarantee cannot hap-
pen, and the condition is satisfied trivially.
We now sketch the proof for the first guarantee. If
G and G' are different groups, then the second guaran-
tee with in = in' implies the first. If G and G' are the
same group and mcastp(in, G) ?G mcastq(in', G),
then the first guarantee holds by the normal vector
timestamp protocol and the new placement rule, be-
cause once in1is placed behind in in the delivery se-
quence for r, it will again be moved behind in each
time in is moved to the end of the sequence. The
last case is if G and G' are the same group and
mcastp(in, G) #*G mcastq(in', G). In this case, there
must be some ii, in and G different from G such that
mcastp(in, G) ? mcastq(in, G)			mcastq(in', G).
As in the argument above for the second guarantee,
once in is multicast, in is received at 5r and can never
again be moved back in the delivery sequence for r.
And, since in' can be received at 5r only after in is
multicast, in is delivered to r before in'.
15
