[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00 01                                                         
INTERNET-DRAFT                                   R. Canetti,  B.  Pinkas
draft-irtf-smug-taxonomy-01.txt  IBM Research and the Weizmann Institute
Expire in six months                                          April 1999


                  A taxonomy of multicast security issues
                            (updated version)
                     <draft-irtf-smug-taxonomy-01.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 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.

   1. Abstract

   With the growth and commercialization of the Internet, the need for
   secure IP multicast is growing. In this draft we present a taxonomy
   of multicast security issues. We first sketch some multicast group
   parameters that are relevant to security, and outline the basic
   security issues concerning multicast in general, with emphasis on IP
   multicast. Next we suggest two `benchmark' scenarios for secure
   multicast solutions. Lastly we review some previous works.

   This is an updated version of the document. The authors will be
   grateful for remarks, and will continue to update and revise this
   document accordingly.

Canetti, Pinkas                                                 [Page i]


INTERNET DRAFT                                                April 1999

   Table of Contents:

   1. Abstract ................................................. i
   2. Introduction ............................................. 1
   3. A Taxonomy of multicast security issues................... 2
      3.1 Multicast group characteristics....................... 2
      3.2 Security requirements and trust issues................ 3
      3.3 Performance  parameters............................... 5
   4. Benchmark Scenarios....................................... 5
      4.1 Single source broadcast............................... 6
      4.2 Virtual Conferences................................... 7
   5. A mini-survey of related work............................. 7
      5.1 Works on group key management......................... 8
      5.2 Works on individual authentication....................10
      5.3 Works on membership revocation........................11
      5.4 Working prototypes....................................13
      5.5 Architectures.........................................13
      5.6 Fighting piracy.......................................14
   Acknowledgments..............................................15
   References...................................................16
   Authors address..............................................18

   2. Introduction

   In addition to traditional  unicast communication, the Internet
   Protocol supports a multicast mode where a packet is addressed to
   a group of recipients. The main motivation behind this mode is
   efficiency, both in sender resources (one transmission serves all
   recipients) and in network resources (far less traffic). The main
   challenge in efficient multicast transmission is routing: how to get
   a packet to its intended recipients with minimal latency and
   bandwidth consumption. See work done at the MBONED and IDMR working
   groups. Reliable multicast is being studied in the IRTF Reliable
   Multicast working group.

   The growth and commercialization of the Internet offers a large
   variety of scenarios where multicast transmission will greatly save
   in bandwidth and sender resources. Immediate examples include news
   feeds and stock quotes, video transmissions, teleconferencing,
   software updates, and more. (See [Quinn] for a more complete survey
   on multicast applications.)  Yet, multicast transmission introduces
   security concerns that are far more complex than those of simple
   unicast. Even dealing with the `standard' issues of message and
   source authentication and secrecy becomes much more complex; in
   addition other concerns arise, such as access control, trust in
   group centers, trust in routers, dynamic group membership, and
   others.

Canetti, Pinkas                                                 [Page 1]


INTERNET DRAFT                                                April 1999

   We are looking for solutions that mesh well with current multicast
   routing protocols, and that have as small overhead as possible.
   In particular, a realistic solution must maintain the current way by
   which {\em data packets} are being routed; yet additional control
   messages may be introduced, for key exchange and access control.
   These messages need not necessarily be sent via multicast.

   As a first step towards a workable solution, we present a taxonomy
   of multicast security concerns and scenarios, with a strong emphasis
   on IP multicast.  First we list multicast group characteristics
   that are relevant to security. Next we list security concerns and
   some trust issues. We also discuss important performance parameters.

   It soon becomes clear that the scenarios are so diverse that there
   is little hope for a single security solution that accommodates all
   scenarios.  Thus we suggest two `benchmark' scenarios for
   multicast security solutions.  One scenario involves a single sender
   (say, an on-line stock-quotes distributor) and a large number of
   passive recipients (say, hundreds of thousands). The second scenario
   depicts relatively small interactive groups of up to few thousands
   of participants.

   Lastly we present a brief survey of existing work on multicast
   security. (The authors apologize in advance for any
   misinterpretations and omissions. Please write and complain. They
   will be happy to update and correct the  draft.) Two main issues
   emerge, where the performance of current solutions leaves much to be
   desired:

    - Individual authentication: How to make sure that information
    is arriving unmodified from a particular group member
    (as opposed to information coming from "one of the group members").

    - Membership revocation: How to prevent a leaving member from
    future access to the group resources.

   3.   A Taxonomy of multicast security issues

   3.1  Multicast group characteristics

   We list salient parameters of multicast groups. These parameters
   affect in a crucial way on the security architecture that should be
   used.

   Group size: Can vary from several tens of participants in small
      discussion groups, through thousands in virtual conferences
      and classes, and up to several millions in large broadcasts.

   Member characteristics: These include computing power (do all members
      have similar computing power or can some members be loaded more
      than others?) and attention (are members on-line at all times?).

Canetti, Pinkas                                                 [Page 2]


INTERNET DRAFT                                                April 1999

   Membership dynamics: Is the group membership static and known in
      advance? Otherwise, do members only join, or do members also
      leave? how frequently does membership change and how fast should
      changes be updated? Are membership changes bursty?

   Expected life time: Is the group expected to last several minutes?
      days? an unbounded amount of time?

   Number and type of senders: Is there a single party that sends data?
     several such parties? all parties?  Do few senders generate most
     of the traffic? Is the identity of the senders known in advance?
     Are non-members expected to send data to the group?

   Volume and type of traffic: Is there heavy volume of communication?
     Must the communication arrive in real-time? what is the allowed
     latency? For instance, is it data communication (less stringent
     real-time requirements, low volume), audio (must be real-time,
     low volume), or video (real-time, high volume)?

   3.2  Security requirements and trust issues

   We list several security requirements and trust-related concerns. Not
   all issues are relevant to all multicast applications; yet they
   should be kept in mind when designing a system.

   Group management and access control: Making sure that only registered
     and legitimate parties have access to the communication addressed
     to the group. (Sometimes it may be necessary also to allow only
     group member to send data to the group.) Sometimes this is enforced
     by having a group key that is known only to group members; other,
     more hierarchical solutions exist as well. Here several security
     concerns are involved:
       * How to authenticate potential group members
       * How to securely distribute the group key(s).
       * How to revoke membership of leaving members
       * How to prevent joining members from access to past group
         communication.
       * How to periodically refresh the group key(s).
       * How to log information and allow for external auditing.


Canetti, Pinkas                                                 [Page 3]


INTERNET DRAFT                                                April 1999




   Ephemeral secrecy: Preventing non group-members from easy access
     to the transmitted data. Here a mechanism that only delays access,
     or prevents access only to crucial parts of the data may be
     sufficient. (For instance, to maintain ephemeral secrecy when
     transmitting a video it is  sufficient to encrypt only the
     low-order Fourier  coefficients in an MPEG encoding.)

   Long-term secrecy: Making sure that  the data remains secret to
     non-group members, for a substantial amount of time after
     transmission. This may often not be a requirement for multicast
     traffic. In particular, the larger the multicast group the
     weaker the secrecy assurance is (even if the cryptography
     is perfect.)

   Perfect Forward Secrecy: Making sure that encrypted data remains
     secret even if the key is compromised (either by cryptanalysis or
     by break-in) at a later date. This requirement is needed only for
     applications that require long-term secrecy. Thus in many
     multicast applications it is not necessary.

   Sender and data authenticity: Making sure that the received data
     originates with the claimed sender and was not modified on
     the way.  Authenticity takes two flavors:  Group authenticity
     means that a group member can recognize whether a message
     was sent by a group member. Individual authenticity means that
     it is possible to identify the particular sender within the group.
     It may also be desirable to verify the origin of messages
     even if the originator is not a group member.

   Anonymity: Several flavors are possible. One is keeping the identity
     of group members secret from outsiders or from other group members.
     Another is keeping the identity of the sender of a message secret.
     A related concern is protection from traffic analysis.

   Non-repudiability: The ability of receivers of data to prove to third
     parties that the data has been transmitted, together with the
     source. Non-repudiability is somewhat contradictory to anonymity,
     and it is not clear whether it should be implemented in an IP-layer
     protocol.

   Service availability: Maintaining service availability against
     malicious attack is ever more challenging in a multicast setting,
     since clogging attacks are easier to mount and are much more
     harmful.


Canetti, Pinkas                                                 [Page 4]


INTERNET DRAFT                                                April 1999

   3.3   Performance  parameters

   We list relevant performance parameters. Relative importance of
   these parameters may vary from application to application. These
   parameters should always be measured against the degree of security
   achieved.

   Latency, bandwidth  and work overhead per data packets. These are
     the most immediate costs and should typically be minimized at the
     highest priority. Here distinction should be made between the load
     on strong server machines and on weak end-users.

   Latency, bandwidth  and work overhead per control packets. These are
     typically less frequent, thus efficiency here is somewhat less
     crucial. The control messages usually deal with  key distribution
     and refreshment.

   Group initialization, and member addition and deletion overheads.
     Group initialization occurs once. In groups with highly dynamic
     membership, efficient addition (and especially deletion) of
     members may be an important concern.

   Sender initialization, the overhead of a sender when it starts
     transmitting to the group.

   Congestion control, especially around centralized control services
     at peak sign-on and sign-off times. (A quintessential scenario
     is a real-time broadcast where many people join right before the
     broadcast begins and leave right after it ends.)

   Resume overhead: The work incurred when a group member becomes
     active after being dormant (say, off-line) for a while.

   4. Benchmark Scenarios

   As seen above, it takes many parameters to characterize a multicast
   security scenario, and a large number of potential scenarios exist.
   Different scenarios call for different solutions; it seems unlikely
   that a single solution will accommodate all scenarios.

   We present two very different scenarios for secure multicast,
   and sketch possible solutions and challenges. These scenarios seem
   to be the ones that require most urgent solutions; in addition, they
   span a large fraction of the concerns described above, and solutions
   here may well be useful in other scenarios as well. Thus we suggest
   these scenarios as benchmarks for evaluating security solutions.

Canetti, Pinkas                                                 [Page 5]


INTERNET DRAFT                                                April 1999

   4.1 Single source broadcast

   Here a single source wishes to continuously broadcast data to a large
   number of passive recipients. The source can be a news agency that
   broadcasts stock-quotes and news-feeds to paying customers, or a
   Pay-TV station. We list a number of characteristics:

   The number of recipients can be up to hundreds of thousands and more.
   The source is typically a top-end machine with ample resources.
   It can also be parallelized or split to several sources in different
   locations. The recipients are typically lower-end machines
   with limited resources. Consequently, the security solution must
   optimize for efficiency at the recipient side.

   The life-time of the group is usually long. Yet,  the group
   membership is dynamic: members join and leave at a relatively high
   rate. In addition, at peak times (say, before and after important
   broadcasts) a high volume of sign-on/sign-off requests are expected.
   It can be assumed that members have a long-term relationship with the
   group; this may facilitate processing of sign-on/sign-off requests.

   The volume of transmitted data may vary considerably: if only
   text is being transmitted then the volume is relatively low (and
   the latency requirements are quite relaxed); if audio/video is
   transmitted (say, in on-line pay-TV) then the volume can be very
   high and very little latency is allowed.

   Authenticity of the transmitted data is a crucial concern and
   should be strictly maintained: a client must never accept a forged
   stock-quote as authentic. In particular, it should it accept a stock
   quote that originated with any other group member than the specified
   sender. Another important concern is preventing
   non-members from using the service. This can be achieved by
   encrypting the data; yet the encryption may be relatively
   weak/ephemeral since there is no real secrecy requirement - only
   prevention from easy unauthorized use.

   The required latency of the communication varies from application
   to application.  Member revocation would would be performed within
   minutes or seconds from the time it is requested (but it is typically
   not required to remove members within fractions of a second)

   There is typically a natural group owner that manages access-control
   as well as key management. However, the sender of data may be a
   different entity (say, Yahoo broadcasting Reuters stock-quotes in its
   home-page).

Canetti, Pinkas                                                 [Page 6]


INTERNET DRAFT                                                April 1999

   4.2  Virtual Conferences

   Typical virtual conference scenarios may include on-line meetings
   of corporate executives or committees, town-hall type meetings,
   interactive lectures and classes, and multiparty video games.
   A virtual conference involves several tens to hundreds of peers,
   often with roughly similar computational resources. Usually most,
   or all, group members may a-priori wish to transmit data
   (although often there is a small set of members that generate
   most of the bandwidth).

   The group is often formed per event and is relatively short-lived
   (say, few minutes or hours). Membership is often static: members
   join at start-up, and remain signed on throughout. Furthermore,
   even if a member leaves it is often not crucial to
   cryptographically revoke their group membership.
   Bandwidth and latency requirements vary from application to
   application, similarly to the case of single source
   broadcast. However, latency (and especially sender initialization)
   should typically be very small in order to facilitate the
   simultaneity and interactivity of virtual conferences.

   Authenticity of data {\em and sender} may be the most crucial
   security concern. In some scenarios maintaining secrecy of data and
   anonymity of members may be important as well; in other
   scenarios secrecy of data is not a concern at all. There is often a
   natural group owner that may serve as a trusted center. Yet,
   it is always beneficial to distribute trust as much as possible.

   5.  A mini-survey of known related work

   Following is a short survey of multicast security related work. The
   authors apologize in advance for any misinterpretations and
   omissions. Please write and complain. They will be happy to update
   and correct the draft.
   The first three sections of the survey describe work on three main
   issues described above: group key management, individual
   authentication, and membership revocation. The last section describes
   work on prototypes which implement various elements of multicast
   security.

Canetti, Pinkas                                                 [Page 7]


INTERNET DRAFT                                                April 1999

   5.1 Works on group key management

   The works below  concentrate on establishing and managing a common
   key among all group members. This key can be used for encryption
   and group authentication, but is insufficient for individual
   authentication. Group management is closely related to user
   revocation methods (see Section 5.3) since it should enable to
   prevent a leaving group member from further decrypting the group
   communication.

   The GKMP protocol [GKMPA,GKMPS] generates and maintains symmetric
   keys for the members of a multicast group. In this protocol a
   multicast group has a dedicated Group Controller (GC) which is
   responsible for managing the group keys. The GC generates the
   group keys in a joint operation with a selected group
   member. Afterwards it contacts each group member validates its
   permissions, and sends it the group keys (encrypted using a key which
   is mutually shared between the GC and that member). This approach may
   have scalability problems since a single entity, the GC, is
   responsible for sending the keys to all group members.

   The Scalable Multicast Key Distribution scheme (SMKD) [Ballardie] is
   based on the Core-Based Tree (CBT) routing protocol and provides
   secure join to a CBT group tree in a scalable approach. It utilizes
   the hard-state approach of CBT in which routers on the delivery tree
   know the identities of their tree-neighbors. When a CBT group is
   initiated in this scheme the core of the tree operates as the group
   controller and generates the group session keys and key distribution
   keys. As routers join the delivery tree they are delegated the
   ability to authenticate joining members and provide them with the
   group key. This approach is highly scalable. However, it is tied to a
   specific routing protocol, and does not provide a separation between
   the routing and the security mechanism. (In particular, it puts hight
   trust in the routers, since each router in the delivery tree obtains
   the same keys as the group controller.)

Canetti, Pinkas                                                 [Page 8]


INTERNET DRAFT                                                April 1999

   The MKMP [MKMP] key management protocol enables the initial Group Key
   Manager to delegate the key distribution authority to other
   parties in a dynamic way. It first generates the group key.
   Then it delegates the key distribution ability to
   selected parties by sending a message to the  multicast group
   soliciting  these parties. This message contains keys and access
   lists which can only be decrypted by the solicited parties. After
   they obtain this material they can operate as Group Key Managers.
   This dynamic approach has the advantage that the group topology can
   be adapted on-line. MKMP uses a single key for the entire group and
   thus does not require hop-by-hop decryption/re-encryption of the
   payload.

   The Iolus scheme [Mittra] handles the scalability problem
   by introducing a "secure distribution tree". The multicast group is
   divided into subgroups which are arranged hierarchically. There is a
   Group Security Controller (GSC) managing the top-level group, and
   Group Security Intermediaries (GSIs) for managing the different
   subgroups. Each subgroup has its own sub-key which is chosen by its
   manager. A GSI knows the keys of its subgroup and of a higher level
   subgroup, so it can "translate" messages to/from higher levels.
   A disadvantage of this approach is the latency incurred by GSIs
   decrypting and re-encrypting each data packet (although the use of
   encryption indirection enables this latency to be constant and
   independent of the packets length). The removal of an untrusted GSI
   is also complex.

   The work of Poovendran et al [PACB] identifies two major drawbacks of
   the GKMP protocol which result from the use of a single group
   controller: the group controller is a single point of failure, and
   its heavy load might affect scalability. It is suggested to use a
   panel of three controllers, where every two panel members can operate
   as a group controller. It is furthermore proposed to improve
   scalability by segmenting the group into  clusters, which are each
   managed by a sub-controller panel.

   The internet draft of Hardjono et al [HCD] suggests a hierarchical
   framework for group key management, similar to that of Iolus. The
   network is divided into regions: many "leaf regions" and a single
   "trunk region" which which is used to connect leaf regions and does
   not contain any member hosts. Each region can have a different key
   management protocol. In particular, different leaf regions can have
   different intra-region group key management protocols, and the trunk
   region operates an inter-region group key management protocol.

Canetti, Pinkas                                                 [Page 9]


INTERNET DRAFT                                                April 1999


   In [HCM] an intra-region group key management protocol is presented
   in detail. To enable scalability a domain is further divided into
   areas, where each host belongs to a single area. There is a single
   Domain-Key-Distributor and many Area-Key-Distributors which are
   responsible for each area. A host only communicates with the AKD of
   its area. A key for the members of a multicast group in a domain is
   generated by the DKD and is propagated to the hosts through the
   AKD's. This scheme presents an interesting new concept: the group key
   is common to members in the the entire domain, while the control
   messages for key updates are transferred via the
   Area-Key-Distributors, using two levels of keys. This method enjoys
   "the best of two worlds": First, the data packets need not be
   re-encrypted en-route and can be routed using any multicast routing
   protocol. Second, the group (or domain) controller need not keep
   track of all group members; instead, it can keep track only of the
   AKDs. This facilitates scalability while maintaining independence
   from the data routing mechanism. Note that this protocol is for
   managing an multicast group inside a domain (a "leaf" in the terms of
   [HCD]) whereas a different protocol can be used for inter-domain
   ("trunk") key management of the group.

   Kruus [Kruus] focuses on identifying and surveying security related
   issues for multicast group key management. The paper describes
   several approaches for group key management and for user revocation.

   5.2 Works on individual authentication

   In order to authenticate that a message was sent by one of the group
   members it is sufficient to use Message Authentication Codes (MACs,
   see e.g. [HMAC]) with a single shared key known to all group
   members. However, this method does not suffice to enable individual
   authentication, i.e. it cannot be used to authenticate a message as
   originating from a specific party.

   Individual authentication can be achieved if the sender of the
   message signs it using a digital signature scheme. However, the
   computational complexity of computing and verifying digital
   signatures, as well as the length of the signature,  may be
   significant. RSA signatures might be an appealing choice of a
   signature scheme since it is possible to use them in a mode  which
   considerably reduces the running time of the verification algorithm.

   It is possible to use signature schemes based on elliptic curves,
   which are very efficient in both the computation and the
   communication requirements. Another interesting approach is to use
   on-line/off-line signature schemes [EGM]. These enable the signer to
   perform most of its computation off-line, even before it learns the
   message that it should sign. When this message becomes known the
   signer only has to perform a very efficient computation in order to
   complete the signature.

Canetti, Pinkas                                                [Page 10]


INTERNET DRAFT                                                April 1999

   The schemes of Gennaro and Rohatgi [GR] enable to efficiently sign
   streams of data. Basically, the idea is to partition data packets
   into chains. Each data packet includes a hash of the next packets in
   the chain, and then only the first packet in the chain needs to be
   signed. There are two types of schemes, for data streams which are
   available off-line (and so the whole stream can be examined by
   the source before it sends the first packet), and for real-time data.
   A major drawback of the suggested schemes is that they do not deal
   well with unreliable communication channels and might therefore not
   be suitable for large scale multicast groups. Furthermore, the scheme
   for real-time data introduces a considerable communication overhead
   per packet.

   Digital signatures for streams are also discussed in [WL], their
   design goal is to enable efficient and delay bounded signatures, and
   efficient verification for individual packets (thus solving the
   problem of unreliable communication). They suggest that the source
   will sign a digest of several packets. Each packet is sent with this
   signature and with additional information that enables the receiver
   to compute the digest. The preferred method for computing the digest
   is using Merkle's hash trees [Merkle]. It is also suggested that
   signatures will be performed using a variant of Fiat-Shamir
   signatures, which (using some heuristics) are more efficient than
   other common signature schemes.

   Building on previous work [FN1,DFFT], Canetti et al [CGIMNP]
   suggest individual authentication schemes which are based on
   efficient MACs rather than on public key signatures. These schemes
   are designed to be secure against coalitions of up to k of group
   members, where k is a parameter which affects the overhead. To
   explain the approach, let us present a simplified example: The idea
   is to use some number, n, of MAC keys. The pre-designated sender has
   all keys, where each one of the receivers has  n/2 keys, chosen at
   random from the n keys. Now, each message is MACed with each one of
   the n keys, and a recipient verifies the MACs whose keys it knows.
   A coalition of bad parties can make some `victim' accept forge
   messages only it the coalition knows all the MAC keys that the victim
   knows. The parameters are set so that the probability that  such a
   bad event occurs is small.

   5.3 Works on membership revocation

   In order to prevent new group members (respectively, leaving members)
   from accessing data sent before they joined (respectively, after they
   leave), the group controller needs to change a multicast group key
   whenever membership in the group changes. While it is rather
   straightforward to efficiently update the group key when a new member
   joins the group, this is not the case when a member is removed from
   the group since this member already knows the group key.

Canetti, Pinkas                                                [Page 11]


INTERNET DRAFT                                                April 1999

   The approach taken in many group key management protocols
   [GKMPA,SMKD,MKMP]  to remove untrusted members is to generate a new
   group key and send it to all the remaining group members (using
   secret keys which are shared between each of the members and the
   group controller), thus essentially creating a new multicast group
   without the untrusted member. This approach is non-scalable.

   As discussed in Section 5.1, an alternative approach is to divide the
   multicast group to subgroups with independent subgroup keys. When a
   member is removed it is only required to send individually encrypted
   messages to members of the subgroup of the removed member. This
   approach, taken in [Mittra,PACB,HCD,HCM], is more scalable. It
   requires that each subgroup contains a trusted controller (e.g. the
   Group Security Intermediary in the Iolus system of [Mittra]). If this
   party becomes untrusted then a more complex revocation procedure
   (which is not described in these drafts) should be run. (Note
   that the scheme of [HCM] suggests that subgroups (domains) are
   further partitioned to smaller subgroups (areas) with their own
   controllers, to provide better scalability).

   Broadcast encryption [FN] is a scheme to encrypt messages from a
   single source to a dynamically changing group of recipients. When a
   member is leaving the scheme can be used to send the new group
   key to the remaining members. The scheme uses a parameter k which is
   the maximum tolerable size of a corrupt coalition of former group
   members that might try to learn a key they should not get. The
   overhead of the scheme depends on the maximum number of potential
   members in the group, and the maximum size of the corrupt coalition,
   but not on the number of members which are removed. Therefore
   overhead is better than in other user revocation methods if the
   number of leaving/joining  members is large. The scheme is based on
   using a set of keys and applying a clever method of assigning subsets
   of these keys to group members. This assignment makes sure that for
   every corrupt coalition of k users it is possible to encrypt a
   message such that the keys known to its coalition members do not
   suffice for decryption, whereas the keys of any other member do.

   Wallner et al [WHA]  (and, independently, [WGL]) introduce a scalable,
   tree based user revocation scheme. For a group of n members there is
   a total of 2n keys but each member is only required to store log(n)
   keys. When a group member is removed the group controller sends a
   single message  of size 2log(n) to all members, and each member
   performs log(n) (rather efficient) computations in order to generate
   the new group key. The removed member cannot compute the new group
   key even if it receives this message. The basic idea of the scheme is
   to imagine the users as the leaves of a binary tree, assign a key to
   each node, give each user the keys in the path from its leaf to the
   root and use the root key as the group key. When a user is removed all
   the keys it holds are replaced. Two drawbacks of the scheme are that
   it requires the center to keep track of 2n keys, and requires each
   member to receive and process each member-revocation message in order
   to learn the current group key.

Canetti, Pinkas                                                 [Page 12]


INTERNET DRAFT                                                April 1999

   The scheme of [WHA] was generalized by [WGL] for trees of arbitrary
   degree (although binary trees achieve the best communication
   overhead). It is possible to reduce the length of the member
   revocation message that the controller broadcasts to only log(n)
   encryptions (instead of 2log(n) in [WHA]). Different schemes that
   achieve this property are presented in [CGIMNP] and in [MS].
   The scheme of [MS] affects the broadcast overhead of the user
   addition operation, it increases it from O(1) in the scheme of [WHA]
   to log(n). The scheme of [CGIMNP] does not increase the overhead of
   user addition. The security of the scheme of [CGIMNP] can be
   rigorously proven based on the security (i.e. pseudorandomness) of
   the cryptographic function that is used.

   5.4 Working prototypes

   A prototype of the Iolus system has been implemented [Mittra]. It
   uses a client application which interfaces between applications and
   the Iolus GSC/GSIs. It is claimed there that the basic prototype is
   rather a simple to implement and to use. There is only small
   penalty for the decryption/encryption process of a GSI, and
   this penalty does not depend on the size of the payload. Note however
   that the Iolus system does not provide any individual authentication
   mechanism.

   A toolkit for secure internet multicast is described in [CEKPS]. It
   emphasizes a separation between control and data functions. This
   enables applications to have fine grain control over the data path,
   while keeping the control plain transparent to the applications. The
   toolkit can operate without end-to-end support for multicast, using
   data reflectors connected via unicast tunnels. It is written in
   Java. Similar to Iolus, a multicast group is divided to subgroups
   (domains), however the toolkit offers better flexibility, supports
   individual authentication (by using digital signatures), and operates
   over non-multicast enabled backbones.

   5.5 Architectures

   Several works address the architectural issues involved in the key
   management aspect of secure multicast [HCD,GMKPA.GMKPS,WHA,WGL].
   These works have been described above.

   In [CCPRRS] a host architecture for  secure IP multicast protocols is
   suggested. The architecture is based on the IPSEC architecture [Ken98]
   and tries to use IPSEC components (IKE, AH, ESP) as much as possible.
   As in IPSEC, the architecture calls for separation of the key
   management (to take place in the application layer) from the data
   trandformations (to take place mostly in the IP layer). Yet, an
   additional data-processing module is added in the application/UDP
   layer. This module is responsible for source authentication, which is
   not taken care of by the IPSEC trandformations. The suggested
   architecture is flexible and can adopt many of the key management
   protocols described above.

Canetti, Pinkas                                                [Page 13]


INTERNET DRAFT                                                April 1999

   5.6 Fighting piracy

   Secure multicast is used to ensure the secrecy of the
   communication inside the multicast group. However nothing
   prevents one of the legitimate members of the group from helping
   other, illegitimate parties to receive the messages that are
   sent to the group. This problem is well known in the context of
   television broadcasting, and is commonly referred to as
   "piracy". There has been a considerable amount of work on this
   subject, motivated by the pay-TV industry. It is mostly relevant
   to the one-to-many multicast scenario.

   The fight against piracy consists of two stages: (1) tracing the
   pirates, and (2) taking action to prevent them from further
   operation. We describe below some methods which can be used for
   tracing. Once the source of piracy is detected it is possible to
   prevent it from further decryption using the user revocation
   schemes we discussed above. It might be also desirable to take
   legal actions against the pirates.

   There are two methods by which pirates can operate. They can either

   (1) distribute decryption keys that enable to decrypt the group
   communication, i.e. perform illegal "key distribution", or
   (2) decrypt the communication themselves and distribute the
   decrypted content, i.e. perform illegal "contect distribution".

   The content distribution attack is harder for large scale
   implementation and easier to detect, since the pirates should
   essentially operate their own broadcast station. The key
   distribution attack is therefore preferable to the pirates.

   In order to prevent illegal key distribution pay-TV providers
   provide decryption keys in smartcards which are supposed to
   be "tamper proof". That is, it should be hard to extract from a
   key from a smartcard. However, most smartcards have weaknesses
   which enable to extract the keys they contain (see e.g. [C]).

   It is easier to trace the source of a key distribution attack
   than that of a content distribution attack. The reason being that
   it is possible to give each user a somewhat different key (and
   then, given a pirate decoder, recognize which keys were used to
   construct it). It is a much harder task to distribute to each
   user a  different copy of the data such that each copy would seem
   to have the same content, but a pirate copy would identify its
   source (even if the content was passed through different
   trasnformations, e.g. lossy compression, and was generated from
   several legal copies). This task is known as watermarking, and
   is discussed below.

Canetti, Pinkas                                                [Page 14]


INTERNET DRAFT                                                April 1999

   Fighting illegal key distribution:

   A obvious method to trace the source of keys is to give each
   user a personal key. The content should be encrypted with a
   random key, which is itself ecnrypted with each of the personal
   keys. The drawback of this scheme is that it sends an additional
   encryption per user, and this overhead is only reasonable for
   small groups. There are more advanced methods whose ovehead is
   much smaller [CFN,NP]. These methods are secure as long as the
   pirates use less than k keys, where k is a parameter.


   Fighting illegal content distribution:

   In order to trace the source of the content it is essential to
   insert in it "watermarks" which the pirates cannot remove. See
   [CKLS] for a discussion of marking methods. An additional
   issue is the distribution of marks into the copies that are
   delivered to users, i.e the problem of efficiently generating
   unique fingerprints. An efficient fingerprinting method is
   suggested in [BS] (however, fingerprinting schemes are less
   efficient than schemes for tracing illegal key distribution).


   Self enforcement is an interesting concept: it intends to
   prevent piracy (rather than trace its source) by discouraging
   legitimate users from giving their keys to others. In order to
   achieve this property each user's key contains some information
   which is private to the user (for example, his credit card
   number). It is hoped for that users would be discouraged from
   providing keys which contain this information to others.
   Efficient tracing schemes are described in [DLN].


   Acknowledgments
   ================

   Much of this text is reproduced from [CGIMNP], written
   with Juan Garay, Gene Itkis, Daniele Micciancio and Moni Naor.
   The authors are grateful to the people with whom they interacted
   on this topic, including all the above and in addition Naganand
   Doraswamy, Rosario Gennaro, Dan Harkins, Shai Halevi, Dimitris
   Pendarakis, Tal Rabin, Pankaj Rohargi and Debanjan Saha.

Canetti, Pinkas                                                [Page 15]


INTERNET DRAFT                                                April 1999

   References
   ==========

   [Ballardie] Ballardie A., "Scalable Multicast Key Distribution", RFC
   1949, May 1996.

   [BS] Boneh D., Shaw D., "Collusion-Secure Fingerprinting
   for Digital date", IEEE Tran. on Information Theory, Vol 44,
   No. 5, pp. 1897-1905, 1998.

   [C] http://www.cryptography.com/dpa/qa/index.html

   [CEKPS] Chang I., R. Engel, D. Kandlur, D. Pendarakis, D. Saha, "A
   Toolkit for Secure Internet Multicast", manuscript, 1998.

   [CCPRRS] Canetti R., Cheng P. C., Pendarakis D., Rao, J., Rohatgi P.,
   Saha D.,  "An architecture for secure IP multicast", manuscript.

   [CGIMNP] Canetti R., J. Garay, G. Itkis, D. Micciancio, M. Naor,
   B. Pinkas, "Multicast Security: A Taxonomy and Efficient
   Authentication", to be presented at INFOCOM '99.

   [CFN] Chor B., Fiat A., Naor M., "Tracing Traitors",   Proc.
   Advances in Cryptology - Crypto '94, Springr-Verlag LNCS 839
   (1994), 257--270.

   [CKLS] Cox I., Kilian J., Leighton T., Shamoon T., "A Secure,
   Robust Watermark for Multimedia",  Information Hiding Workshop,
   Cambridge, UK, Springer-Verlag LNCS 1174,  (1996), 185--206.

   [DLN] Dwork C.,  Lotspiech J., Naor M., "Digital Signets:
   Self-Enforcing Protection of Digital Information", 28th
   Symposium on the Theory of Computation (1996), 489--498.

   [DFFT] Dyer M., T. Fenner, A. Frieze, A. Thomason, "On Key Storage
   in Secure Networks", J. of Cryptology, Vol. 8, 1995, 189-200.

   [EGM] Even S., O. Goldreich, S. Micali, "On-line/off-line digital
   signatures", Advances in Cryptology - Crypto '89, Springer-Verlag
   LNCS 435, pp. 263-277, 1990.

   [FN] Fiat A., M. Naor, "Broadcast Encryption", Adv. in Cryptology
   - Crypto '92, Springer-Verlag LNCS 839, pp. 257-270, 1994.

   [FN1] Fiat A., M. Naor, unpublished work. Appears in Alon N.,
   "Probabilistic Methods in Extremal Finite Set Theory", in
   "Extremal Problems for Finite Sets", 1991, 39-57.

   [GR] Gennaro R., P. Rohatgi, "How to Sign Digital Streams",
   Advances in Cryptology - Crypto '97, Springer-Verlag LNCS 1294,
   pp. 180-197, 1997.

Canetti, Pinkas                                                [Page 16]


INTERNET DRAFT                                                April 1999

   [HCD] Hardjono T., Cain B., Doraswamy N., "A Framework for Group Key
   Management for Multicast Security", internet draft
   draft-ietf-ipsec-gkmframework-00.txt, July 1998.

   [HCM] Hardjono T., Cain B., Monga I., "Intra-Domain Group Key
   Management Protocol", internet draft,
   draft-ietf-ipsec-intragkm-00.txt,
   November 1998.

   [MKMP] Harkins D., N. Doraswamy, "A Secure, Scalable Multicast Key
   Management Protocol (MKMP)".

   [GMKPA] Harney, H., C. Muckenhirn, "Group Key Management Protocol
   (GKMP) Architecture", RFC 2094, July 1997.

   [GKMPS] Harney, H., C. Muckenhirn, "Group Key Management Protocol
   (GKMP) Specification". RFC 2093, July 1997.

   [Ken98] Stephen Kent, Randall Atkinson, "Security Architecture for
   the Internet Protocol",
   Internet Draft draft-ietf-ipsec-arch-sec-07.txt, July 1998.

   [HMAC] Krawczyk H., M. Bellare, R. Canetti, "HMAC: Keyed-Hashing for
   Message Authentication", RFC 2104,    April 1997.

   [Kruus] Kruus P., "A Survey of Multicast Security Issues and
   Architectures," 21st National Information Systems Security Conf.,
   Arlington, VA, October 5-8, 1998.

   [MS] McGrew D. A., and Sherman A. T., "Key Establishment in Large
   Dynamic Groups using One-way Function Trees", submitted to IEEE
   Trans. on Software Engineering. 1998.

   [Merkle] Merkle R. C., "A Digital Signature based on a Conventional
   Encryption Function", Crypto '87.

   [Mittra] Mittra S., "Iolus: A Framework for Scalable Secure
   Multicast". In Proceedings of ACM SIGCOMM '97, Cannes, France,
   September 1997.

   [NP] Naor M., Pinkas B., "Threshold Traitor Tracing", Crypto '98.
   http://www.wisdom.weizmann.ac.il/~bennyp/PAPERS/ttt.ps

   [PACB] Poovendran R., Ahmed S., Corson S., Baras J., "A Scalable
   Extension of Group Key Management Protocol", Proceedings of the 2nd
   ATIRP Conference, University of Maryland, College Park, MD, Feb. 2-6,
   1998.

   [Quinn] Bob Quinn, "IP Multicast Applications: Challenges and
   Solutions",  draft-quinn-multicast-apps-00.txt, Nov 1998.

Canetti, Pinkas                                                [Page 17]


INTERNET DRAFT                                                April 1999


   [WHA] Wallner D. M., E. G. Harder, R. C. Agee, "Key Management
   for Multicast: Issues and Architecture", internet draft
   draft-wallner-key-arch-01.txt, September 1998.

   [WGL] Wong C. K., Gouda M., Lam S. S., "Secure Group Communication
   Using Key Graphs", SIGCOMM '98. Also, University of Texas at Austin,
   Computer Science Technical report TR 97-23.

   [WL] Wong C. K., Lam S. S., "Digital Signatures for Flows and
   Multicasts", IEEE ICNP '98.  Also, University of Texas at Austin,
   Computer Science Technical report TR 98-15.


   Authors'  Addresses:
   ====================

   Ran Canetti                              Benny Pinkas
   IBM TJ Watson Research Center            Weizmann Inst. of Science
   POB. 704, Yorktown Heights,              Rehovot, Israel
   Tel. 1-914-784-7076                      Tel. +972-8-9344310
   canetti@watson.ibm.com                   bennyp@wisdom.weizmann.ac.il

Canetti, Pinkas                                                [Page 18]