Abstract
The secure multicast field has been extensively studied for more than a decade now and there exist numerous proposals throughout academic literature. This paper presents a selection of those most important and popular to the date, focusing on centralized schemes due to their high popularity and the recent publication of alternatives that do not appear in previous revisions. Comparisons are provided and special attention is paid to communications and storage overhead.
Keywords: key distribution, secure group communication, centralized secure multicast.
Introduction
Secure multicast communications imply establishing a common encryption key that can be used to cipher the transmitted information. The first and trivial approach for achieving that is to establish n secure channels (one for each recipient), which obviously soon becomes impractical as the number of recipients scales. Therefore a wide variety of schemes have appeared in the last decade. Regardless of their nature, schemes must provide: information privacy while in transit, an efficient and fault-tolerant rekeying process so an acceptable quality of service (QoS) is guaranteed, and forward and backward secrecy. The former implies that a member which leaves the network (i.e., her membership expires) should not be able to decrypt any ciphered information transmitted thereafter, while the latter implies that an arriving member should not be able to decrypt any ciphered information transmitted before her arrival. Both impose a refreshment of the encryption key used to cipher the transmitted information. These two restrictions may become an efficiency problem at high churn rates (avalanches of members joining and/or leaving). Some less restrictive scenarios may not require backward secrecy. Additionally, schemes must be resistant to collusion, i.e., old recipients allying together to use their expired key material in order to illegally decrypt new information. There are other features of schemes that are directly related to reliability. One of them is the self-healing property: in some schemes members are able to obtain lost keying material without needing to make new requests to the Key Server. Finally, secure multicast protocols can be divided into stateful and stateless. In the former, re-key messages contain modifications on the previous keying states and thus users must be aware of all re-key operations performed since their arrival. In the latter, members may obtain all the keying material from scratch at every re-key operation, which clearly makes them more resilient against faulty networks. Addressing these reliability issues has become the trend in the last years due to the popularization of mobile and ad-hoc networks.
Centralized secure multicast schemes are of great use thanks to its simplicity and the popularization of services like IPTV [1] and ad-hoc networks. Even in decentralized architectures for huge audiences they appear at the core of every separate group. Therefore, centralized schemes are an important part of the secure multicast global field. This paper presents a selection of the most important centralized secure multicast protocols to the date, due to the recent appearance of new proposals that, for obvious reasons, were not included in previous surveys [2][3] (another interesting, updated survey is [4]). Schemes are discussed and compared attending to the properties mentioned above, and divided into three main categories attending to the scenario they are addressed to: (1) general-purpose schemes, suitable for a wide range of applications, (2) multi-group schemes, specially useful in scenarios that involve several different information channels (such as IPTV platforms) and (3) self-healing schemes for ad-hoc networks. The following notation will be used along the paper. The single entity that manages the re-keying process receives the name Key Server. Hosts that conform the main body of the network are named members. h and d denote trees height and degree, respectively. The total number of members is given by n. b is the bitlength of a symmetric key. Additional specific notation will be indicated where needed. Sections 2, 3 and 4 review the three categories respectively, discuss them and show comparisons. Section 5 concludes the survey and gives a global vision of the field.
General-Purpose Schemes: LKH and Extensions
General purpose schemes were the first ones to appear and have been around for more than ten years now. One of the earliests is the Group Key Management Protocol (GKMP) [5], in which the Key Server shares a key with every member in the audience and a common group key. Some re-key operations require a uni-cast connection with each member, hence the scheme scales poorly. Among the different existing approaches, the hierarchical tree of keys is clearly the preferred one, due to its smart arrangement of users and keys. The first scheme of that kind was the Logical Key Hierarchy (LKH) [6] [7]. In order to reduce the number of re-key messages per join/leave operation of the trivial approach, a logical tree is built with randomly chosen user keys at the leaves. Figure 1(a) depicts such a tree. Every user key is only known by its owner and the Key Server. A Data Encryption Key (DEK), namely group key, is placed at the root node: it encrypts the actual broadcast information, while intermediate tree nodes keep Key Encryption Keys (KEKs), used in the re-key process. A user knows only the keys in her key path, i.e., the keys in the path from its leave to the root. The arrival or departure of a member implies that the group key, the member’s keypath and those nodes that are siblings to the keypath must be refreshed. For balanced trees, the number of required multicast messages for a single join operation is 2h — 1 while the new member must receive h +1 keys. A leave requires 2h keys updated. Appropriate tree configurations for optimal bandwidth usage are discussed in [8] and [9]. Subsequent efforts seek to reduce the number of messages sent by LKH. A widely adopted approach is to use one-way functions or combinations of one-way functions with pseudo-random number generators (PRNGs). LKH+ [10], LKH++ [11] and the recent SKD [12] use this approach in a temporary manner: new keys are derived from old ones by means of a one-way function, independently of their position within the tree. LKH++ and SKD approximately halve LKH’s bandwidth usage in join operations. Additionally, SKD claims a large reduction of the computation effort required at the Key Server. One-way Function Trees (OFT) [13], One-way Function Chain Trees (OFCT) [14] and ELK [15] use the one-way function approach in a spatial manner: every key in the tree is derived from its children, therefore the tree is built in a bottom-up fashion, starting at user keys (which are randomly picked by the Key Server). These schemes assume one-way functions to be perfect, but Horng proposed a collusion attack against OFT in [16] which was taken into account by Ku and Chen in order to develop an improved collusion resistant version of that protocol [17]. ELK addresses bandwidth reduction and reliability simultaneously: a communication-computation tradeoff is introduced, and some degree of tolerance against message losses is achieved. Members need no aid from the Key Server to derive their key path and, with the use of batch and scheduled re-keys, no multicast messages are required in joins.
The Flat Table (FT) approach [18] (contemporary to LKH) also uses a hierarchical key tree arrangement though there are subtle differences which allow storage-communication-optimality [19]. However, vulnerabilities against collusion attacks were soon discovered [20]. The recent EGK scheme [20] retakes the Flat Table idea and smartly solves the collusion problem. Its authors claim to obtain storage-communication-optimality and constant small message sizes. The Clustering approach [21] groups members within clusters of fixed size (say c). Every cluster is placed at a tree leave and assigned a KEK. The storage overhead at the Key Server is reduced, but leaves require one by one key encryptions within the affected cluster.
SecureLock [22], and the scheme proposed in [23] may be also included in the general-purpose category although their approach is mainly focused on using the computational capabilities of the Key Server rather than arranging members in a given structure. The scheme in [23] is stateless but needs large re-key messages which prevent it from being used in very large networks. The SecureLock is also stateless but its computation complexity becomes excessive when increasing the number of members. To alleviate that problem, Scheikl et al. combine it with the LKH approach, thus obtaining a stateful protocol [24].
Table 1. General-purpose secure multicast schemes comparison
|
Storage overhead |
Communications overhead |
||
|
Key Server Member |
Join Multicast Unicast |
Leave Multicast |
|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
Most of the protocols reviewed above can handle large, dynamic audiences in many multicast services that demand privacy. Regarding security, they are mainly collusion free except for OFT and FT. Finally, and regarding reliability, we must remark that LKH was introduced in the late 90′s, a time when the main part of communications were held on reliable links. That is the main reason why these schemes normally do not address reliability issues and therefore they are statefull and not self-healing. Probably ELK is the most reliable protocol in this family. Table 1 shows a comparison in terms of storage and communication costs of the most important schemes along with recent proposals (SKD and EGK). Data are expressed in bits. There are small but subtle variations in the results shown. It can be seen that older schemes focus on reducing communications in re-key operations, while acquiescing in linear storage needs. More recent proposals focus on the latter, given that acceptable bandwidth usage results were already obtained. Other reasons for storage reduction are the popularization of smart devices (with low storage capabilities) and the ever increasing audiences as multimedia multicast services become more and more popular. As a last remark we note that statistical improvements can be applied to member arrangement in tree-based schemes in order to gain efficiency and scalability [25].
Multi-group Schemes
There exist scenarios in which several, different information channels are encrypted separately and reach different, not disjoint groups of members. Typical examples are multimedia platforms with several pay-per-view channels and communications in hierarchically managed networks. Schemes shown next can be seen as an extension of the tree approach: multiple trees are built from a single, global set of leaves, thus obtaining several roots. Figure 1(b) shows an arrangement example. Since a single member may now belong to more than one group, her key path includes all keys from her leaf to the different roots she is connected to, therefore re-key operations will normally affect more than one tree (however, note that not all users are always connected to all roots). The pioneer proposal, the MG scheme, appears in [26] and [27].
Table 2. Multi-group secure multicast schemes comparison
|
|
Storage overhead |
Communications overhead |
|
|
|
Key Server Member |
Join Multicast Unicast |
Leave Multicast |
|
MG[26] [27] |
 |
 |
 |
|
HAC[28] |
 |
 |
 |
|
Zhang et al.[29] |
 |
 |
 |
Fig. 1. Tree hierarchies of keys
Due to the intricate resultant network, single re-key operations become significantly complex in terms of overhead and therefore batch re-keyings are used. The HAC scheme [28] reduces both bandwidth and communications overhead by improving the multi-tree arrangement and using one-way functions. Both schemes are statefull. Zhang et al. present a stateless protocol based on the bilinear Diffie-Hellman Problem [29]. Table 2 shows a comparison of [27], [28] and [29] in big—O notation terms. M is the number of groups/trees and n0 the average number of members in a subgroup. Other multi-group schemes are [30] and [31]. To the best of our knowledge, it is the first time this kind of schemes is included in a survey.
Self-healing Schemes for Ad-Hoc Networks
Last decade advances on smart devices have led to the development and massive use of MANETS: mobile ad-hoc networks with unreliable links, limited bandwidth, highly dynamic topologies and unpredictable member behavior (there is no guarantee that members will be online at a given time or for a given period of time). What’s more, most of the devices used in these networks have low computational capacities given their need to manage energy efficiently. Due to the specific restrictions that MANETS impose, re-keying is usually performed on a batch manner. An interval between two batch re-keys is called a session. Zhu et al. present one of the earliests schemes in [32]. They add reliability and self-healing to a traditional scheme in order to obtain m-recoverability at a low additional bandwidth overhead. m-recoverability implies that a member may still recover the current keying material after missing a maximum of m key updates.
An important family within self-healing schemes are those based on polynomials and secret sharing techniques. The scheme in [33] by Staddon et al. also achieves m-recoverability. It combines the transmission to members of an initial set of shares with the transmission of additional, redundant shares at every update round. With that information, members are able to recover a given key even if they miss its corresponding update. The price for that is an increase in bandwidth overhead, up to O(mt2): m is the maximum number of updates a member can miss, while t is both the polynomial degree and the minimum number of ex-members that must collude in order to break the system. The protocol presented in [34] by Liu et al. goes further by reducing the bandwidth overhead to O(tj). The value j is the current session within the interval m: note that the re-key information transmitted is a multiple of j and therefore increases depending on the current session, to a maximum of m times. More recent schemes involve the use of one way functions. The scheme in [35] by Dutta et al. achieves a better bandwidth usage, constant member storage requirements, presumably unconditional security and is not restricted to only m sessions recoverability. However, Du et al. reveal security weaknesses of [35] and propose an improved, collusion-free protocol [36]. Finally, the same authors propose another constant storage scheme [37] but they do not guarantee its resistance to collusion.
Table 3 compares the schemes found in [33], [34], [35] and [37], focusing on the storage requirements at the member and the communication overhead per key update (q is a large prime involved in calculations, greater than n). Data are expressed in terms of bits. Given the limited memory space of smart devices, constant storage requirements are desirable. As we see, Dutta et al. [35] and Du et al. [37] offer the best results in those terms. Regarding the communication overhead, Dutta et al. [35] shows the best results again. However, its vulnerability to collusion attacks makes it a weak option to choose. Du et al. [37] and Liu et al. [34] show good results and achieve resistance against collusion.
Table 3. Self-healing secure multicast schemes comparison
|
|
Storage at member |
Communication overhead |
Collusion Key long resistant life-span |
|
|
Staddon et al. [33] |
 |
 |
Yes |
No |
|
Liu et al. [34] |
 |
 |
Yes |
No |
|
Dutta et al. [35] |
 |
 |
No |
Yes |
|
Du et al. [37] |
 |
 |
Yes |
Yes |
Table 4. Feature comparison for the different schemes reviewed
|
Cat. |
Stful/ Stless |
Coll. Res. |
Rel. |
Keys tree |
|
Cat. |
Stful/ Stless |
Coll. Res. |
Rel. |
Keys tree |
|
|
SL [22], 1989 |
1 |
Stless |
 |
 |
 |
SKD [12], 2009 |
1 |
Stful |
 |
 |
 |
|
CKMP [5], 1997 |
1 |
Stful |
 |
 |
 |
EGK [20 , 2010 |
1 |
Stful |
 |
 |
 |
|
Cluster 21], 1997 |
1 |
Stful |
 |
 |
 |
Naranjo 23], 2010 |
1 |
Stless |
 |
 |
 |
|
LKH [6 7], 1999 |
1 |
Stful |
 |
 |
 |
Zhang [29], 2006 |
2 |
Stless |
 |
 |
 |
|
LKH+ 10], 1999 |
1 |
Stful |
 |
 |
 |
MG [26] [27], 2007 |
2 |
Stful |
 |
 |
 |
|
OFCT [14], 1999 |
1 |
Stful |
 |
 |
 |
HAC [28], 2008 |
2 |
Stful |
 |
 |
 |
|
FT [18], 1999 |
1 |
Stful |
 |
 |
 |
Staddon [33], 2002 |
3 |
Stless |
 |
 |
 |
|
ELK [15], 2001 |
1 |
Stful |
 |
 |
 |
Zhu [32], 2003 |
3 |
Stless |
 |
 |
 |
|
LKH++ [11], 2002 |
1 |
Stful |
 |
 |
 |
Liu [34], 2003 |
3 |
Stless |
 |
 |
 |
|
SL+HTA[24],2002 |
1 |
Stful |
 |
 |
 |
Dutta 35], 2007 |
3 |
Stless |
 |
 |
 |
|
OFT [13], 2003 |
1 |
Stful |
 |
 |
 |
Du [36 , 2008 |
3 |
Stless |
 |
 |
 |
|
Ku [17], 2003 |
1 |
Stful |
 |
 |
 |
Du [37 , 2009 |
3 |
Stless |
 |
 |
 |
Note that overhead depends, among other values, on the security parameter, which results in a tradeoff between security and bandwidth usage. Key life-span refers to user keys lifetime: some schemes, such as Staddon et al. [33] and Liu et al. [34], require the user key to be renewed after m sessions. That is clearly a drawback since it increases the workload at the Key Server side and bandwidth usage, specially in faulty networks which is the case. To conclude, we believe that self-healing schemes still have several challenges to overcome, mainly: costly setup phases that must be repeated after m sessions, generalizing a constant use of storage, going further on bandwidth usage reduction and overcoming the usual security-communication overhead tradeoff.
Conclusions
This paper shows a survey on the field that includes some of the latest proposals. Table 4 compares the different schemes introduced along the paper according to their features: "Cat.", category, either (1) general-purpose, (2) multi-group or (3) ad-hoc oriented; "Stful/Stless", stateful or stateless; "Coll.Res.", collusion resistant; and "Keys tree", use of the hierarchical tree approach. Still new proposals appear each year and, with the popularization of new scenarios like IPTV and specially ad-hoc networks, the desirable features for a secure multicast scheme are evolving: low bandwidth and faulty links demand to reduce the number and frequency of communications with the Key Server and the possibility to recover from information loss. It seems clear that this trend will increase in the foreseeable future.
