INTERNET-DRAFT R. Canetti, B. Pinkas draft-canetti-secure-multicast-taxonomy-00.txt IBM Research and Expire in two months the Weizmann Institute May 1998 A taxonomy of multicast security issues (temporary version) <draft-canetti-secure-multicast-taxonomy-00.txt> Status of this Memo This document is an Internet Draft. 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." To view the entire list of current Internet-Drafts, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). 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 a temporary version of the document. The authors will be grateful for remarks, and will update and revise this document accordingly. Canetti, Pinkas [Page i]
INTERNET DRAFT May 1998 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.................... 9 5.3 Works on membership revocation........................10 5.4 Working prototypes....................................11 Acknowledgments.... .........................................12 References...................................................12 Authors address..............................................13 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. Yet, multicast transmission introduces security concerns that are far more complex than those of simple unicast. Even dealing with the `standard' issues of message 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 May 1998 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. One is individual authentication, where it is required to make sure that information is arriving from a particular group member (as opposed to information coming from "one of the group members"). The other is membership revocation: here it is required 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 May 1998 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? unbounded amount of time? Number and type of senders: Is there a single party that sends data? several such parties? all parties? Does few senders generate most of the traffic? Is the identity of the senders known in advance? Are non-members expected to send data? 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 issues. Not all issues are relevant to all multicast applications; yet they should be kept in mind when designing a system. 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. Ephemeral secrecy: Preventing non group-members from easy access to the transmitted data. Here a mechanism that delays access, or prevents access only to crucial parts of the data is 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.) Canetti, Pinkas [Page 3]
INTERNET DRAFT May 1998 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. Key refreshment: The need to refresh (change) the key during a lengthy multicast session, in order to foil cryptanalysis and other methods for compromising the key. It should be remembered that key refreshment in a multicast setting is more complex than for unicast. Service availability: Maintaining service availability against malicious attack is ever more relevant in a multicast setting, since clogging attacks are easier to mount and are much more harmful. Group management and ownership: Several tasks related to a secure multicast group need handling. We list these tasks below. These tasks can be handled either by a centralized entity or in a distributed way (and then it should be decided which entities or coalitions of entities can perform each security critical operation) . It should be remembered that putting trust in centralized centers is a security Achilles-heel (although it usually makes solutions much simpler). Group management tasks include: * Key management * Logging/Audit * Error and exception handling * Access control (see below) Access control: Controlling group membership, and perhaps keeping reliable records of the amount of usage of each member. The problem becomes more complex if members may join with time, and even more complex if members may leave the group (and then the group has to make sure that the leaving members lose the cryptographic abilities reserved to members). Canetti, Pinkas [Page 4]
INTERNET DRAFT May 1998 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 definitely be minimized. Here distinction should be made between the load on strong server machines and on weak end-users. 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. Key generation and distribution overhead. Congestion, 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 May 1998 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 or even several millions. The source is typically a top-end machine with ample resources. It can also be parallelized or even split to several sources in different locations. The recipients are typically lower-end machines with limited resources. Consequently, and security solution must optimize for efficiency at the recipient side. Although the life-time of the group is usually long, 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. In addition, 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. Another important concern is preventing non-members from using the service. This can be achieved by encrypting the data; yet the encryption may be weak 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 should 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 usually 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 May 1998 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} is the most crucial security concern. In some scenarios maintaining secrecy of data and anonymity of members may be crucial as well; in many 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 May 1998 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 not sufficient for individual authentication. The GKMP protocol [GKMPA,GKMPS] generates and maintains symmetric keys for the members of a multicast group. In this protocol each 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 by a key mutually shared between the GC and that member. This approach is non-scalable 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 joining of 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. Yet, since every router in the delivery tree obtains the same keys as the group controller the scheme does not provide a high level of security against corrupt routers in the group tree. 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 subkey 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. Canetti, Pinkas [Page 8]
INTERNET DRAFT May 1998 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 (the method which is used for key generation is left outside the scope of the MKMP draft). Then it delegates the key distribution authority 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 to changes occurring 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. 5.2 Works on individual authentication In order to authenticate that a message was sent by a group member it is enough 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. to authenticate a message as being 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 verifier. It is also 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 signatures schemes [Even]. 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. The schemes of Gennaro and Rohatgi [Gennaro] enable to efficiently sign streams of data. Basically, the idea is to partition the data packets into chains; each data packet will include a hash of the next packets in the chain; now only the first packet in the chain needs to be signed. However, these schemes do not deal well with unreliable communication channels, and might not be efficient enough for on-line data which should be transmitted "on-the-fly". Canetti, Pinkas [Page 9]
INTERNET DRAFT May 1998 Building on previous work [FN1,Dyer], 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 newly joined members (respectively, leaving members) from accessing data sent before they joined (respectively, after they leave), one needs to change a multicast group key whenever membership in the group changes. It is particularly difficult to make sure that a leaving member does NOT know the newly distributed key. The approach taken when removing untrusted members in most existing group key management protocols [GKMPA,SMKD,MKMP] is to generate a new group key and distribute it to all the remaining group members, thus essentially creating a new multicast group without the untrusted member. This approach is highly non-scalable. The same approach is also taken by the Iolus protocol [Mittra] for the subgroup which contained the removed member, but since this subgroup is smaller than the entire group this solution is more scalable. However, if a Group Security Intermediary becomes untrusted then a more complex operation (which is not described in [Mittra]) should be performed. Broadcast encryption is a scheme designed in [FN] 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 is large for small numbers of leaving members, but becomes more attractive when 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 the corrupt coalition members do not suffice for decryption, whereas the keys of any other member do. Canetti, Pinkas [Page 10]
INTERNET DRAFT May 1998 The scheme of Wallner et al [Wallner] for user revocation is highly scalable. 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 should send a single message of size 2log(n) to all members, and each member should perform 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 arrange the users as 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. The main drawbacks of this scheme are that it requires the center to keep track of about 2n keys, and requires each member to receive and process all member-revocation messages in order to learn the current group key. In contrast, it may be good to design mechanisms that enable members which have been off-line to receive and process all member-revocation messages that they have not received, in a reasonable amount of work. 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. Canetti, Pinkas [Page 11]
INTERNET DRAFT May 1998 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. References ========== [Ballardie] Ballardie A., "Scalable Multicast Key Distribution", RFC 1949, May 1996. [CEKPS] Chang I., R. Engel, D. Kandlur, D. Pendarakis, D. Sala, "A Toolkit for Secure Iternet Multicast", manuscript, 1998. [CGIMNP] Canetti R., J. Garay, G. Itkis, D. Micciancio, M. Naor, B. Pinkas, "Multicast Security: A Taxonomy and Efficient Authentication", manuscript, 1998. [Dyer] Dyer M., T. Fenner, A. Frieze, A. Thomason, "On Key Storage in Secure Networks", J. of Cryptology, Vol. 8, 1995, 189--200. [Even] 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", Advances 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. [Gennaro] 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 12]
INTERNET DRAFT May 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. [HMAC] Krawczyk H., M. Bellare, R. Canetti, "HMAC: Keyed-Hashing for Message Authentication", RFC 2104, February 1997. [Mittra] Mittra S., "Iolus: A Framework for Scalable Secure Multicast". In Proceedings of ACM SIGCOMM '97, Cannes, France, September 1997. [Wallner] Wallner D. M., E. G. Harder, R. C. Agee, "Key Management for Multicast: Issues and Architecture", internet draft draft-wallner-key-arch-00.txt, June 1997. 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 13]