On the security of group communication schemes based on symmetric key cryptosystems

ABSTRACT

Many emerging applications in both wired and wireless networks, such as information dissemination and distributed collaboration in an adversarial environment, need support of secure group communications. There have been many such schemes in the setting of wired networks. These schemes can be directly adopted in, or appropriately adapted to, the setting of wireless networks such as mobile ad hoc networks (MANETs) and sensor networks. In this paper we show that the popular group communication schemes that we have examined are vulnerable to the following attack: an outsider adversary who compromises a legitimate group member could obtain some or all past group keys as well as the current group key; this is in sharp contrast to the widely-accepted belief that a such adversary can only obtain the current group key. This attack is very powerful also because it provides the adversary the following flexibility: since the adversary knows which members are the "most valuable" ones from its own perspective of view, compromise of any such member leads to the exposure of all the past and current group keys. This flexibility is particularly relevant in the setting of MANETs and sensor networks because they are typically deployed in a small area and the adversary can capture and compromise the easiest-to-obtain node. In order to deal with this powerful attack, we formalize two security models for stateful and stateless group communication schemes, respectively. We show that some practical methods can make a subclass of the group communication schemes immune to this attack at the following extra expense: at each rekeying event, a group member conducts logarithmically-many pseudorandom function evaluations.

REFERENCES

• 1: R. Anderson. On the forward security of digital signatures. http://www.cl.cam.ac.uk/TechReports /UCAM-CL-TR-549.pdf.
• 2: D. Balenson, D. McGrew, and A. Sherman. Key Management for Large Dynamic Groups: One-Way Function Trees and Amortized Initialization. Internet Engineering Task Force, Feb. 1999.
• 3: Mihir Bellare , Sara K. Miner, A Forward-Secure Digital Signature Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.431-448, August 15-19, 1999
• 4: M. Bellare and B. Yee. Forward-security in private-key cryptography. In Cryptographer's Track - RSA Conference (CT-RSA), pp 1--18.
• 5: Dan Boneh , Glenn Durfee , Matthew K. Franklin, Lower Bounds for Multicast Message Authentication, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.437-452, May 06-10, 2001
• 6: R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas. Multicast security: A taxonomy and some efficient constructions. In IEEE INFOCOM 1999, pp 708--716, 1999.
• 7: R. Canetti, T. Malkin, and K. Nissim. Efficient communication-storage tradeoffs for multicast encryption. In Proc. EUROCRYPT 99, pp 459--474.
• 8: Amos Fiat , Moni Naor, Broadcast encryption, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.480-491, January 1994, Santa Barbara, California, United States
• 9: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 10: N. Jho, J. Hwang, J. Cheon, M. Kim, D. Lee, and E. Yoo. One-way chain based broadcast encryption schemes. In Proc. EUROCRYPT 2005, pp 559--574.
• 11: Jonathan Katz , Moti Yung, Complete characterization of security notions for probabilistic private-key encryption, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.245-254, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335335]
• 12: T. Kaya , G. Lin , G. Noubir , A. Yilmaz, Secure multicast groups on ad hoc networks, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986872]
• 13: L. Lazos and R. Poovendran. Energy-aware secure multicast communication in ad-hoc networks using geographic location information. In Proc. IEEE ICASSP 2003.
• 14: L. Lazos and R. Poovendran. Cross-layer design for energy-efficient secure multicast communications in ad hoc networks. In Proc. IEEE ICC'04.
• 15: L. Lazos and R. Poovendran. Power proximity based key management for secure multicast in ad hoc networks. ACM Journal on Wireless Networks (WINET), ??(?), to appear.
• 16: L. Lazos, J. Salido, and R. Poovendran. Vp3: Using vertex path and power proximity for energy efficient key distribution. In Proc. IEEE VTC'04 (invited paper).
• 17: Xiaozhou Steve Li , Yang Richard Yang , Mohamed G. Gouda , Simon S. Lam, Batch rekeying for secure group communications, Proceedings of the 10th international conference on World Wide Web, p.525-534, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372153]
• 18: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 19: D. Micciancio and S. Panjwani. Optimal communication complexity of generic multicast key distribution. In Proc. EUROCRYPT 2004, pp 153--170.
• 20: Dalit Naor , Moni Naor , Jeffrey B. Lotspiech, Revocation and Tracing Schemes for Stateless Receivers, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.41-62, August 19-23, 2001
• 21: Sandro Rafaeli , David Hutchison, A survey of key management for secure group communication, ACM Computing Surveys (CSUR), v.35 n.3, p.309-329, September 2003 [doi>10.1145/937503.937506]
• 22: Sanjeev Setia , Samir Koussih , Sushil Jajodia , Eric Harder, Kronos: A Scalable Group Re-Keying Approach for Secure Multicast, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.215, May 14-17, 2000
• 23: Alan T. Sherman , David A. McGrew, Key Establishment in Large Dynamic Groups Using One-Way Function Trees, IEEE Transactions on Software Engineering, v.29 n.5, p.444-458, May 2003 [doi>10.1109/TSE.2003.1199073]
• 24: M. Waldvogel, G. Caronni, D. Sun, N. Weiler, and B. Plattner. The VersaKey framework: Versatile group key management. IEEE Journal on Selected Areas in Communications, 17(9):1614--1631, Sept. 1999.
• 25: D. Wallner, E. Harder, and R. Agee. Key management for multicast: Issues and architectures. Internet Draft, Sept. 1998.
• 26: Chung Kei Wong , Mohamed Gouda , Simon S. Lam, Secure group communications using key graphs, IEEE/ACM Transactions on Networking (TON), v.8 n.1, p.16-30, Feb. 2000 [doi>10.1109/90.836475]
• 27: S. Xu. On the security of group communication schemes based on symmetric key cryptosystems. Full version available from the author, 2005.
• 28: S. Zhu, S. Setia, S. Xu, and S. Jajodia. Gkmpan: An efficient group rekeying scheme for secure multicast in ad-hoc networks. In MobiQuitous 2004, pp 42--51.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Security

Keywords:
backward-security, broadcast encryption, forward-security, group communication, key management, security