Research Abstracts - 2007

Introduction

IP multicast is a very efficient way of disseminating information to a large group of users. In many applications, it is important that only legitimate group members (GMs) can access the multicast data. This is typically enforced by encrypting all data traffic with a (symmetric) cryptographic key and distributing the encryption key selectively, to GMs only. In other words, the access control problem for group data is transformed into access control on the encryption key.

A security concern in this setting is perfect forward secrecy, that is, data transmitted before the compromise of a GM should remain secret, provided they are not stored locally by the compromised GM. This suggests the data encryption key (DEK) should be refreshed periodically, with old versions erased, so that access to the current DEK does not compromise past data.

In a multicast group with dynamic membership (i.e., GMs may join and leave throughout the lifetime of the group), two more security issues arise.

• Group backward secrecy: a new GM should not have access to data that are transmitted before he joins.
• Group forward secrecy: once a GM leaves the group, he should not have access to future data.

Both perfect forward secrecy and group backward secrecy can be addressed efficiently, for instance, by applying a one-way transformation to the DEK at regular intervals. Since one-way functions cannot be inverted efficiently, a new GM, or an intruder with access to the current DEK, cannot recover old DEKs. Group forward secrecy, however, is much harder to achieve, because the leaving GM knows potentially all old DEKs. Any new key efficiently derivable from old ones is insecure. So far, the best solution is to have new DEKs generated independently and delivered securely to remaining GMs. The main challenge is then the efficiency of selective key distribution. This problem is known in the literature as group key management and has been studied extensively for more than a decade. We refer to [1] for a comprehensive survey.

Most of the existing solutions make use of auxiliary keys, often known as key encryption keys (KEKs). Each GM is given a unique subset of KEKs, and the group controller (GC) encrypts rekey messages with a combination of KEKs so that only current GMs can obtain the new DEK. In other words, KEKs provide a means to distinguish any subset of GMs from the rest of the multicast group.

Our approach

In this project, we show that the same concept can be implemented using the ciphertext-policy attribute-based encryption (CP-ABE) primitive proposed by Bethencourt, Sahai and Waters (BSW) [2]. The main idea is to associate to each GM a set of abstract attributes, as opposed to actual KEKs. An attribute can be any statement regarding the GM; for example, ``The 12-th bit in my ID is 0,'' or ``I belong to the subgroup identified by gid.'' Like KEKs, these attributes allow the GC to distinguish current GMs from former/leaving GMs. This is done by computing an access structure that is satisfied by the attribute set of every current GM, but not by the attribute set of any former/leaving GM. This access structure is then used to encrypt the new DEK in the CP-ABE system, which ensures the desired access control.

There are several advantages to using CP-ABE (in particular, the BSW implementation) for group key management. One of them derives from the decoupling between abstract attributes and actual keys. When a secret key SK is issued for a set S of attributes, the components of SK are computed based on S, but they are masked by a combination of randomization factors unique to SK. As a result, even if two users share certain attributes, the group elements in their secret keys are independent. Thus, secret keys of current GMs need not be changed during a join/leave event. This is very different from the traditional approach, where all KEKs affected by the membership change must be refreshed.

Having randomization factors embedded in secret keys brings two other advantages. The first is collusion resistance. In fact, collusion attacks are built into the CP-ABE security game of [2], where the adversary may make repeated secret key queries both before and after submitting the challenges. This allows us to give a collusion-resistant implementation of the flat table scheme [3], which is vulnerable to collusion threats when implemented with traditional KEKs [4,5]. Secondly, we can use the Delegate algorithm of [2] to implement subgroup controllers (SGCs). This algorithm creates new secret keys by re-randomizing an existing secret key, without having access to the master secret. Therefore, the master secret resides only at the central GC, which improves security.

Furthermore, we found a very efficient way to refresh an entire BSW encryption system, including the public parameters, master secret key and user secret keys. This can be used to achieve perfect forward secrecy. Only two multicast messages are necessary for the refresh operation: a new DEK and a conversion factor, which is a single group element, are both sent encrypted with the current DEK. New secret keys can be derived locally using one group multiplication.

Finally, the use of CP-ABE reduces storage overhead for the GC. (Although nowadays storage is not an issue in most practical situations.) Instead of storing all KEKs in the system, the GC stores the public parameters and master secret. For a fixed security parameter, these keys are of constant size, independent of the size of the multicast group.

Related Work

The flat table key management scheme was proposed in [4,5]. Despite its simplicity and good overall performance, flat table has been largely dismissed due to collusion threats. In contrast, tree-based rekey algorithms have gained popularity steadily, including Logical Key Hierarchy (LKH) [6,7], One-Way Function Tree (OFT) [8], One-way Function Chain Tree [9], Hierarchical a-ary Tree with Clustering [10] and Efficient Large-Group Key (ELK) [11]. These algorithms provide different tradeoffs among storage, computation and communication overheads. We refer to [1] for detailed comparisons based on various performance measures.

In [12], Boneh et al. proposed a collusion-resistant broadcast encryption in which both ciphertexts and secret keys are of constant size, but the public key size grows linearly with N, the total number of users. The authors also outlined a secure mailing list application, which is very similar to secure multicast. This approach has the disadvantage that users are represented individually (e.g., two group elements per user in the public key), therefore linear complexity arises both in public key size and in encryption and decryption time. Even with the proposal of parallel instances, the complexities are still linear in the size of each instance (e.g., sqrt(N)). In comparison, attribute-based encryption is more flexible, allowing efficient representations (e.g., O(log(N))) of certain large sets (e.g., the complement of a small set of users).

References:

[1] S. Rafaeli and D. Hutchison. A survey of key management for secure group communication. ACM Computing Surveys, 35(3):309--329, 2003.

[2] J. Bethencourt, A. Sahai and B. Waters. Ciphertext-policy attribute-based encryption. To appear in Proceedings of the 28th IEEE Symposium on Security and Privacy (Oakland), 2007.

[3] L. Cheung, J. Cooley, R. Khazan and C. Newport. Collusion-resistant group key management using attribute-based encryption. In progress.

[4] I. Chang, R. Engel, D. Kandlur, D. Pendarakis and D. Saha. Key management for secure Internet multicast using Boolean function minimization techniques. In Proceedings IEEE Infocomm'99, 1999.

[5] M. Waldvogel, G. Caronni, D. Sun, N. Weiler and B. Plattner. The VersaKey framework: versatile group key management. In IEEE Journal on Selected Areas in Communications, 17(9):1614--1631, 1999.

[6] C.K. Wong, M. Gouda and S.S. Lam. Secure group communications using key graphs. In Proceedings of the ACM SIGCOMM'98 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 1998.

[7] D. Wallner, E. Harder and R. Agee. Key management for multicast: issues and architectures. RFC 2627.

[8] D.A. McGrew and A.T. Sherman. Key establishment in large dynamic groups using one-way function trees. Technical Report 0755, TIS Labs at Network Associates, Inc., May 1998.

[9] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor and B. Pinkas. Multicast security: a taxonomy and some efficient constructions. In Proceedings of the IEEE INFOCOM'99, 1999.

[10] R. Canetti, T. Malkin and K. Nissim. Efficient communication-storage tradeoffs for multicast encryption. Lecture Notes in Computer Science, volume 1592, 1999. (Advances in Crytology -- EUROCRYPT'99.)

[11] A. Perrig, D. Song and J.D. Tygar. ELK: a new protocol for efficient large-group key distribution. In Proceedings of the IEEE Symposium on Security and Privacy (Oakland), 2001.

[12] D. Boneh, C. Gentry and B. Waters. Collusion resistant broadcast encryption with short ciphertexts and private keys. Lecture Notes in Computer Science, volume 3621, 2005. (Advances in Crytology -- CRYPTO'05)