On the Security Analysis of Lee, Hwang & Lee (2004) and Song & Kim (2000) Key Exchange / Agreement Protocols

Kim-Kwang Raymond Choo

Abstract

This paper provides a critical security analysis of two prominent cryptographic key exchange protocols: the password-based group key agreement by Lee et al. (2004) and the two-party protocol by Song & Kim (2000). We demonstrate that the Lee et al. protocol, despite possessing a formal mathematical proof of security, is vulnerable to a Key Replicating Attack. Furthermore, we show that the Song & Kim protocol is susceptible to a classic reflection attack. These vulnerabilities highlight significant gaps in the "provable security" paradigm and emphasize the need for meticulous proof verification in cryptographic design.

Introduction

Modern secure communication relies on the establishment of temporary session keys via cryptographic protocols. To ensure these protocols are robust, the community increasingly employs the "computational complexity approach," where security is mathematically tied to the hardness of intractable problems like Decisional Diffie-Hellman (DDH). However, the complexity of these proofs often masks subtle structural flaws. This paper addresses the discrepancy between claimed provable security and actual protocol resilience by exposing vulnerabilities in two protocols previously considered secure.

Methodology and Notation

The analysis evaluates the protocols against formal adversary models, specifically the Bresson et al. model for group authenticated key establishment. The following notation is used throughout the analysis to define the cryptographic primitives and identities involved:

Notation and cryptographic primitives used in the protocol analysis.

Analysis of the Lee et al. (2004) Protocol

The Lee et al. protocol is a password-based group key exchange designed to allow multiple users to establish a shared secret. The author identifies a "Key Replicating Attack" that violates the security definitions of the Bresson et al. model.

The Key Replicating Attack

The attack succeeds because the protocol's key derivation function fails to adequately bind participant identities to the final session key. An adversary $\mathcal{A}$ can intercept broadcast messages and impersonate a participant (e.g., $U_4$) without knowing the underlying secrets. By manipulating the message flow, the adversary tricks participants into establishing a session key that matches a test session, thereby exposing the key and violating the goal of key independence.

The Key Replicating Attack on the Lee et al. (2004) protocol, showing how an adversary $\mathcal{A}$ impersonates a user to compromise the session key.

The failure of the original security proof stems from an incorrect simulation of the environment. Specifically, the proof's reduction to the DDH/CDH problem did not account for the adversary's ability to use Send and Reveal oracle queries to distinguish real keys from random ones in non-partner sessions. This allows an Unknown Key Share attack where a party is tricked into thinking they share a key with the adversary when they actually share it with another legitimate user.

Analysis of the Song & Kim (2000) Protocol

The Song & Kim protocol (specifically Protocol 4) is found to be vulnerable to a reflection attack. This vulnerability arises from a lack of asymmetry in its two-flow message structure. An adversary can intercept an initiation message from a user and "reflect" it back to them. The user, believing they are communicating with a peer, completes the protocol and establishes a session key with themselves, failing both entity authentication and secure key establishment goals.

Proposed Remediation

To address the flaws in the Lee et al. protocol, the author suggests two primary fixes:

  1. Identity Binding: Incorporating sender identities directly into the encryption steps to prevent impersonation during the broadcast phase.
  2. Transcript Hashing: Hashing the complete session identifier ($sid$) into the final key derivation function to ensure a strict binding between the specific session transcript and the resulting key.

Conclusion

The discovery of flaws in "provably secure" protocols serves as a cautionary tale for the cryptography community. It demonstrates that mathematical proofs are not infallible and are subject to human error in simulation and modeling. Protocol designers must ensure that identity binding is central to key derivation and that proof simulations rigorously handle all possible adversary oracle queries to maintain the credibility of formal security analysis.

Summary updated

Abstract

We revisit the password-based group key exchange protocol due to Lee et al. (2004), which carries a claimed proof of security in the Bresson et al. model under the intractability of the Decisional Diffie–Hellman problem (DDH) and Computational Diffie–Hellman (CDH) problem. We reveal a previously unpublished flaw in the protocol and its proof, whereby we demonstrate that the protocol violates the definition of security in the model. To provide a better insight into the protocol and proof failures, we present a fixed protocol. We hope our analysis will enable similar mistakes to be avoided in the future. We also revisit protocol 4 of Song and Kim (2000), and reveal a previously unpublished flaw in the protocol (i.e., a reflection attack).
BibTeX
@article{choo2006security,
  author = {Kim-Kwang Raymond Choo},
  title = {{On the Security Analysis of Lee, Hwang \& Lee (2004) and Song \& Kim (2000) Key Exchange / Agreement Protocols}},
  journal = {Informatica},
  year = {2006},
}
Figure