Securing group key exchange against strong corruptions

ABSTRACT

When users run a group key exchange (GKE) protocol, they usually extract the key from some auxiliary (ephemeral) secret information generated during the execution. Strong corruptions are attacks by which an adversary can reveal these ephemeral secrets, in addition to the possibly used long-lived keys. Undoubtedly, security impact of strong corruptions is serious, and thus specifying appropriate security requirements and designing secure GKE protocols appears an interesting yet challenging task --- the aim of our paper.

We start by investigating the current setting of strong corruptions and derive some further refinements such as opening attacks that allow to reveal ephemeral secrets of users without their long-lived keys. This allows to consider even stronger attacks against honest, but "opened" users.

Further, we define strong security goals for GKE protocols in the presence of such powerful adversaries and propose a Tree Diffie-Hellman protocol immune to their attacks. Our security definitions in particular include the case of malicious insiders, for appropriate security goals such as mutual authentication, key confirmation, contributiveness and key-replication resilience. The proposed protocol proceeds in three rounds and is provably secure in the standard model.

REFERENCES

• 1: M. Abdalla, E. Bresson, O. Chevassut, and D. Pointcheval. Password-Based Group Key Exchange in a Constant Number of Rounds. In Proc. of PKC'06, vol. 3958 of LNCS, p. 427--442. Springer, April 2006.
• 2: Giuseppe Ateniese , Michael Steiner , Gene Tsudik, Authenticated group key agreement and friends, Proceedings of the 5th ACM conference on Computer and communications security, p.17-26, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288097]
• 3: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 4: Jens-Matthias Bohli , María Isabel González Vasco , Rainer Steinwandt, Secure group key establishment revisited, International Journal of Information Security, v.6 n.4, p.243-254, June 2007 [doi>10.1007/s10207-007-0018-x]
• 5: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 6: Colin A. Boyd , Anish Mathuria, Protocols for Key Establishment and Authentication, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 7: E. Bresson and D. Catalano. Constant Round Authenticated Group Key Agreement via Distributed Computation. In Proc. of PKC'04, vol. 2947 of LNCS, p. 115--129. Springer, 2004.
• 8: Emmanuel Bresson , Olivier Chevassut , David Pointcheval, Provably Authenticated Group Diffie-Hellman Key Exchange - The Dynamic Case, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.290-309, December 09-13, 2001
• 9: Emmanuel Bresson , Olivier Chevassut , David Pointcheval, Dynamic Group Diffie-Hellman Key Exchange under Standard Assumptions, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.321-336, May 02, 2002
• 10: Emmanuel Bresson , Olivier Chevassut , David Pointcheval, Group Diffie-Hellman Key Exchange Secure against Dictionary Attacks, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.497-514, December 01-05, 2002
• 11: Emmanuel Bresson , Olivier Chevassut , David Pointcheval , Jean-Jacques Quisquater, Provably authenticated group Diffie-Hellman key exchange, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502018]
• 12: E. Bresson and M. Manulis. Malicious Participants in Group Key Exchange: Key Control and Contributiveness in the Shadow of Trust. In Proc. of ATC '07, vol. 4610 of LNCS, p. 395--409. Springer, 2007.
• 13: E. Bresson, M. Manulis, and J. Schwenk. On Security Models and Compilers for Group Key Exchange Protocols. In Proc. of IWSEC '07, vol. 4752 of LNCS, p. 292--307. Springer, 2007.
• 14: Christian Cachin , Reto Strobl, Asynchronous group key exchange with failures, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011820]
• 15: Ran Canetti , Hugo Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.453-474, May 06-10, 2001
• 16: K.-K. R. Choo, C. Boyd, and Y. Hitchcock. Examining Indistinguishability-Based Proof Models for Key Establishment Protocols. In ASIACRYPT'05, vol. 3788 of LNCS, p. 585--604. Springer, 2005.
• 17: G. D. Crescenzo, N. Ferguson, R. Impagliazzo, and M. Jakobsson. How to Forget a Secret. In Proc. of STACS'99, vol. 1563 of LNCS, p. 500--509. Springer, 1999.
• 18: Y. G. Desmedt, J. Pieprzyk, R. Steinfeld, and H. Wang. A Non-Malleable Group Key Exchange Protocol Robust Against Active Insiders. In Proc. of ISC'06, vol. 4176 of LNCS, p. 459--475. Springer, 2006.
• 19: R. Dutta, R. Barua, and P. Sarkar. Provably Secure Authenticated Tree-Based Group Key Agreement. In Proc. of ICICS'04, vol. 3269 of LNCS, p. 92--104. Springer, 2004.
• 20: Jonathan Katz , Ji Sun Shin, Modeling insider attacks on group key-exchange protocols, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102146]
• 21: J. Katz and M. Yung. Scalable Protocols for Authenticated Group Key Exchange. In CRYPTO'03, vol. 2729 of LNCS, p. 110--125. Springer, 2003.
• 22: H.-J. Kim, S.-M. Lee, and D. H. Lee. Constant-Round Authenticated Group Key Exchange for Dynamic Groups. In ASIACRYPT'04, vol. 3329 of LNCS, p. 245--259, 2004.
• 23: Group Key Agreement Efficient in Communication, IEEE Transactions on Computers, v.53 n.7, p.905-921, July 2004 [doi>10.1109/TC.2004.31]
• 24: Yongdae Kim , Adrian Perrig , Gene Tsudik, Tree-based group key agreement, ACM Transactions on Information and System Security (TISSEC), v.7 n.1, p.60-96, February 2004 [doi>10.1145/984334.984337]
• 25: H. Krawczyk. HMQV: A High-Performance Secure Diffie-Hellman Protocol. In CRYPTO'05, vol. 3621 of LNCS, p. 546--566. Springer, 2005.
• 26: B. LaMacchia, K. Lauter, and A. Mityagin. Stronger Security of Authenticated Key Exchange. In Proc. of ProvSec'07, vol. 4784 of LNCS, p. 1--16. Springer, 2007.
• 27: M. Manulis. Survey on Security Requirements and Models for Group Key Exchange. Technical Report 2006/02, Horst-Görtz Institute, November 2006.
• 28: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 29: C. J. Mitchell, M. Ward, and P. Wilson. Key Control in Key Agreement Protocols. Electronic Letters, 34(10):980--981, 1998.
• 30: Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
• 31: V. Shoup. On Formal Models for Secure Key Exchange (Version 4). Technical Report RZ 3120, IBM Research, November 1999.
• 32: V. Shoup. Sequences of Games: A Tool for Taming Complexity in Security Proofs. Cryptology ePrint Archive, Report 2004/332, January 2006.
• 33: M. Steiner. Secure Group Key Agreement. PhD thesis, Saarland University, March 2002.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Security, Theory

Keywords:
authenticated group key exchange, contributiveness, insider attacks, mutual authentication, strong corruptions