Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Computer Security

On the impossibility of building secure Cliques-type authenticated group key agreement protocols

Olivier Pereira, Jean-Jacques Quisquater

Published Apr 20, 2006• 12 citations
Publisher

Abstract

The A-GDH.2 and SA-GDH.2 authenticated group key agreement protocols showed to be flawed in 2001. Even though the corresponding attacks (or some variants of them) have been rediscovered in several different frameworks, no fixed version of these protocols has been proposed until now. In this paper, we prove that it is in fact impossible to design a scalable authenticated group key agreement protocol based on the same design assumptions as the A-GDH ones. We proceed by providing a systematic way to derive an attack against any A-GDH-type protocol with at least four participants and exhibit protocols with two and three participants which we cannot break using our technique. As far as we know, this is the first generic insecurity result reported in the literature concerning authentication protocols.

DOI
10.3233/jcs-2006-14204

Related papers

Modelling and Security Analysis of Authenticated Group Key Agreement Protocols

Olivier Pereira

Authenticated Group Key Agreement Protocols are protocols allowing\na group of principals to contributively generate a key by the\nexchange of messages on a network possibly controlled by an\nattacker. Furthermore, their execution also guarantees all group\nmembers that the key they obtained can only be known by the other\nintended protocol participants. These protocols can be exploited\nin many applications such as audio or videoconferencing,\nreplicated servers (such as database, web, time servers), chat or\nnetwork games for instance. \n AGKAP's present several particularities that make them interesting\ncase studies for research in the theory of security. At first, the\nconsideration of the number of protocol participants as a\nparameter raises several complexity problems that are not present\nin the classical two or three-party frameworks. Furthermore, up to\nnow, the security properties of group protocols have roughly been\nconsidered as direct extensions of two-party properties, what does\nnot capture several plausible attack scenarios. A second\ninteresting aspect of the analysis of AGKAP's is the consideration\nof Diffie-Hellman-type primitives, that present properties out\nof the scope of most classical models. \n We started our study with the construction of a simple model for\nthe analysis of a classical family of protocols: the Cliques\nAGKAP's. This allowed us to discover several attacks and define\ndifferent flavors of group security properties. We then tried to\nfix these protocols, what led us to extend our model in order to\nprove that it is in fact impossible to build a secure AGKAP based\non the same design assumptions as the Cliques protocols. Finally,\nwe designed a new AGKAP based on different cryptographic\nprimitives (signature and hash functions) for which we proved\nauthentication, freshness and secrecy properties. A comparison\nwith a similar AGKAP developed in parallel to ours is also\nproposed.

•Jan 1, 2003•19 citations

On The Deniability of Ma et al.'s Deniable Authenticated Key Agreement Protocol

Meng-Hui Lim, Sang-Gon Lee

A deniable authentication protocol enables the protocol participants to authenticate their respective peers, while able to deny their participation after the protocol execution. In 2007, Ma et al. have proposed a chameleon-based deniable authenticated key agreement protocol. However, we discover that this scheme is in fact undeniable due to some flaws in it’ s protocol design. In this paper, we prove the opposite of their claims and discuss the undeniability of the scheme in detail.

한국멀티미디어학회 학술발표논문집•May 1, 2008•0 citations

Enhancement of an Authenticated 3-round Identity-Based Group Key Agreement Protocol

Wei Yuan, Liang Qing Hu, Hongtu Li +2 more

In 2008, Gang Yao et al. proposed an authenticated 3-round identity-based group key agreement protocol, which is based on Burmester and Desmedt’s protocol proposed at Eurocrypt 94. However, their protocol can only prevent passive attack. If the active attack is allowed, the protocol is vulnerable and an internal attacker can forge her neighbor’s keying material. It is obvious that the protocol do not achieve the aim of authentication. In this paper, we discuss the flaws to attack this protocol and propose an enhanced provably-secure protocol based on their protocol. At last, we make a detailed security analysis of our enhanced authenticated identity-based group key agreement protocol.

Journal of Networks•Oct 19, 2011•0 citations

Security properties of two authenticated conference key agreement protocols

Qiang Tang

Abstract. In this paper we analyse the security of two authenticated group key agreement schemes based on the group key agreement protocol of Burmester and Desmedt. One scheme was proposed by Burmester and Desmedt, and uses a separate authentication scheme to achieve authentication among the participants. We show that this scheme suffers from a number of security vulnerabilities. The other scheme was generated using the general protocol compiler of Katz and Yung. We show that in some circumstances, even if key confirmation is implemented, this scheme still suffers from insider attacks (which are not covered by the security model used by Katz and Yung). 1

•Jan 1, 2005•0 citations

Robust privacy-preserving group key agreement protocols

Gene Tsudik, Stanisław Jarecki, Jihye Kim

The last decade has witnessed a sharp spike in the popularity of group applications, such as multi-media conferencing, collaborative workspaces, as well as dynamic coalitions common in law enforcement and disaster rescue scenarios. Standard security services required in such group settings (such as confidentiality, integrity and authentication) can be efficiently achieved if all group members share a secret key. A group key agreement protocol (GKA) provide a technique for any set of participating players to collaboratively establish a shared key. In this thesis, we tackle two challenging issues in GKA: robustness and privacy-preserving authentication. Robustness improves performance by guaranteeing completion of GKA protocols despite participating player or communication failures. Affiliation-hiding authenticated GKA prevents from man-in-the-middle-attacks by authenticating players in a privacy-preserving manner. We propose a two-round group key agreement protocol, which offers a natural trade-off between message size and the desired level of fault-tolerance. We demonstrate that in a realistic setting of random player faults, the new protocol has logarithmic-sized messages and expected round complexity close to two. We generalize a robust group key agreement protocol to support heterogeneous players for a general environment. We prove the security of the proposed protocols under the standard cryptographic assumptions. We present the formal definition of the affiliation-hiding GKA in a standard PKI model with re-usable certificates. The model includes strong security properties, called perfect forward secrecy (PFS) and linkable affiliation-hiding (LAH)—that an key agreement protocol might provide in the face of player corruptions and session compromises. We construct two variants of optimal-cost AH-AGKA protocols, which satisfy PFS and LAH notions under the standard cryptographic assumptions in the random oracle model. The protocol yields minimal costs: three rounds of interaction matches the round complexity of non-private PFS authenticated GKA and its computation costs are comparable to the cost of unauthenticated GKA.

•Jan 1, 2008•0 citations

ID-Based Authenticated Dynamic Group Key Agreement

王莺洁, 潘军, 诸鸿文

Two ID-based authenticated group key agreement schemes, proposed by Choi et al and Du et al, are insecure against an impersonation attack and they only discussed the static group. This paper proposed a variant of BD protocol, which is fully authenticated by a proven-secure ID-based signature scheme. The protocol can resist the impersonation attack, and other security attributes are also satisfied. Compared with Choi et al and Du et al schemes, the proposed one is more efficient and applicable for dynamic groups.

上海交通大学学报:英文版•Jan 1, 2005•4 citations
The A-GDH.2 and SA-GDH.2 authenticated group key agreement protocols showed to be flawed in 2001. Even though the corresponding attacks (or some variants of them) have been rediscovered in several different frameworks, no fixed version of these protocols has been proposed until now. In this paper, we prove that it is in fact impossible to design a scalable authenticated group key agreement protocol based on the same design assumptions as the A-GDH ones. We proceed by providing a systematic way to derive an attack against any A-GDH-type protocol with at least four participants and exhibit protocols with two and three participants which we cannot break using our technique. As far as we know, this is the first generic insecurity result reported in the literature concerning authentication protocols.
Authenticated Group Key Agreement Protocols are protocols allowing\na group of principals to contributively generate a key by the\nexchange of messages on a network possibly controlled by an\nattacker. Furthermore, their execution also guarantees all group\nmembers that the key they obtained can only be known by the other\nintended protocol participants. These protocols can be exploited\nin many applications such as audio or videoconferencing,\nreplicated servers (such as database, web, time servers), chat or\nnetwork games for instance. \n AGKAP's present several particularities that make them interesting\ncase studies for research in the theory of security. At first, the\nconsideration of the number of protocol participants as a\nparameter raises several complexity problems that are not present\nin the classical two or three-party frameworks. Furthermore, up to\nnow, the security properties of group protocols have roughly been\nconsidered as direct extensions of two-party properties, what does\nnot capture several plausible attack scenarios. A second\ninteresting aspect of the analysis of AGKAP's is the consideration\nof Diffie-Hellman-type primitives, that present properties out\nof the scope of most classical models. \n We started our study with the construction of a simple model for\nthe analysis of a classical family of protocols: the Cliques\nAGKAP's. This allowed us to discover several attacks and define\ndifferent flavors of group security properties. We then tried to\nfix these protocols, what led us to extend our model in order to\nprove that it is in fact impossible to build a secure AGKAP based\non the same design assumptions as the Cliques protocols. Finally,\nwe designed a new AGKAP based on different cryptographic\nprimitives (signature and hash functions) for which we proved\nauthentication, freshness and secrecy properties. A comparison\nwith a similar AGKAP developed in parallel to ours is also\nproposed.
In 2008, Gang Yao et al. proposed an authenticated 3-round identity-based group key agreement protocol, which is based on Burmester and Desmedt’s protocol proposed at Eurocrypt 94. However, their protocol can only prevent passive attack. If the active attack is allowed, the protocol is vulnerable and an internal attacker can forge her neighbor’s keying material. It is obvious that the protocol do not achieve the aim of authentication. In this paper, we discuss the flaws to attack this protocol and propose an enhanced provably-secure protocol based on their protocol. At last, we make a detailed security analysis of our enhanced authenticated identity-based group key agreement protocol.
Abstract. In this paper we analyse the security of two authenticated group key agreement schemes based on the group key agreement protocol of Burmester and Desmedt. One scheme was proposed by Burmester and Desmedt, and uses a separate authentication scheme to achieve authentication among the participants. We show that this scheme suffers from a number of security vulnerabilities. The other scheme was generated using the general protocol compiler of Katz and Yung. We show that in some circumstances, even if key confirmation is implemented, this scheme still suffers from insider attacks (which are not covered by the security model used by Katz and Yung). 1
The last decade has witnessed a sharp spike in the popularity of group applications, such as multi-media conferencing, collaborative workspaces, as well as dynamic coalitions common in law enforcement and disaster rescue scenarios. Standard security services required in such group settings (such as confidentiality, integrity and authentication) can be efficiently achieved if all group members share a secret key. A group key agreement protocol (GKA) provide a technique for any set of participating players to collaboratively establish a shared key. In this thesis, we tackle two challenging issues in GKA: robustness and privacy-preserving authentication. Robustness improves performance by guaranteeing completion of GKA protocols despite participating player or communication failures. Affiliation-hiding authenticated GKA prevents from man-in-the-middle-attacks by authenticating players in a privacy-preserving manner. We propose a two-round group key agreement protocol, which offers a natural trade-off between message size and the desired level of fault-tolerance. We demonstrate that in a realistic setting of random player faults, the new protocol has logarithmic-sized messages and expected round complexity close to two. We generalize a robust group key agreement protocol to support heterogeneous players for a general environment. We prove the security of the proposed protocols under the standard cryptographic assumptions. We present the formal definition of the affiliation-hiding GKA in a standard PKI model with re-usable certificates. The model includes strong security properties, called perfect forward secrecy (PFS) and linkable affiliation-hiding (LAH)—that an key agreement protocol might provide in the face of player corruptions and session compromises. We construct two variants of optimal-cost AH-AGKA protocols, which satisfy PFS and LAH notions under the standard cryptographic assumptions in the random oracle model. The protocol yields minimal costs: three rounds of interaction matches the round complexity of non-private PFS authenticated GKA and its computation costs are comparable to the cost of unauthenticated GKA.
Two ID-based authenticated group key agreement schemes, proposed by Choi et al and Du et al, are insecure against an impersonation attack and they only discussed the static group. This paper proposed a variant of BD protocol, which is fully authenticated by a proven-secure ID-based signature scheme. The protocol can resist the impersonation attack, and other security attributes are also satisfied. Compared with Choi et al and Du et al schemes, the proposed one is more efficient and applicable for dynamic groups.