Cryptanalysis and Improvement of an Elliptic Curve Diffie-Hellman Key Agreement Protocol

Shengbao Wang, Zhenfu Cao, Maurizio Adriano Strangio, Lihua Wang

Abstract

This paper provides a critical security analysis of the ECKE-1 elliptic curve key agreement protocol, identifying a significant vulnerability to Key-Compromise Impersonation (K-CI) attacks. To address this, the authors propose an improved version, ECKE-1N, which achieves full security resilience while maintaining computational efficiency comparable to industry standards like the MQV protocol.

Introduction

Key agreement protocols are fundamental to secure communication, allowing two parties to establish a shared secret over insecure channels. A robust protocol must satisfy several security properties, most notably Key-Compromise Impersonation (K-CI) resilience. This property ensures that if an attacker steals a user's long-term private key, they cannot use it to impersonate other honest parties to that compromised user. The authors demonstrate that the ECKE-1 protocol, proposed in 2005, fails this critical test.

Cryptanalysis of ECKE-1

The paper's primary contribution begins with a mathematical proof-of-concept attack on ECKE-1. The authors show that by intercepting and replacing messages in the exchange, an adversary possessing Alice's private key can manipulate the algebraic structure of the session key calculation. This "cancellation" vulnerability allows the attacker to force the calculation to a value they can compute, effectively impersonating Bob to Alice.

The Proposed ECKE-1N Protocol

To rectify these flaws, the authors designed ECKE-1N. The core innovation lies in the binding of ephemeral public keys to the peer's long-term public key and the use of a non-linear recursive equation for session key derivation that incorporates hashes of identities and public keys.

Detailed steps of the improved ECKE-1N protocol

This structure ensures that an attacker cannot mathematically neutralize unknown terms without solving the Discrete Logarithm Problem (DLP), which is computationally infeasible. Furthermore, by explicitly including identities ($id_A, id_B$) in the hash functions, the protocol prevents Unknown Key-Share (UK-S) attacks.

Comparative Analysis and Results

The authors evaluated ECKE-1N against several established protocols, including MTI/A0, MQV, and the original ECKE-1, across security and performance metrics.

Security Attributes

As shown in the comparative analysis, ECKE-1N satisfies all six major security properties, most notably fixing the K-CIR vulnerability present in the original ECKE-1.

Security attribute comparison of ECKE-1N against existing protocols

Computational Efficiency

Despite the added security, ECKE-1N remains highly efficient. It requires approximately 2.5 point multiplications per party, matching the performance of high-speed protocols like MQV and HMQV. Notably, it reduces the number of field multiplications from two (in ECKE-1) to just one, optimizing the overall computational load.

Conclusion

The ECKE-1N protocol successfully addresses the security shortcomings of its predecessor while maintaining a competitive performance profile. While the current security arguments are heuristic, they provide a strong mathematical foundation for the protocol's resilience, with future work aimed at formal proofs in distributed computing models.

Summary updated

BibTeX
@article{wang2008cryptanalysis,
  author = {Shengbao Wang and Zhenfu Cao and Maurizio Adriano Strangio and Lihua Wang},
  title = {{Cryptanalysis and Improvement of an Elliptic Curve Diffie-Hellman Key Agreement Protocol}},
  journal = {IEEE Communications Letters},
  year = {2008},
  doi = {10.1109/lcomm.2008.071307},
}
Figure