Password-Only Authenticated Three-Party Key Exchange with Provable Security in the Standard Model

Junghyun Nam, Kim‐Kwang Raymond Choo, Junghwan Kim, Hyun-Kyu Kang, Jin‐Soo Kim, Juryon Paik, Dongho WonThe Scientific World JOURNAL 2014 · DOI

TL;DR

This paper introduces the first three-party password-only authenticated key exchange (PAKE) protocol that is provably secure in the standard model, meaning it doesn't rely on idealized assumptions like random oracles. Crucially, it also offers robust security against insider attacks and undetectable online dictionary attacks, addressing significant vulnerabilities in existing three-party PAKE schemes.

What Problem Does This Paper Address?

In secure communication, establishing a shared secret key between parties is fundamental. Password-Only Authenticated Key Exchange (PAKE) protocols offer a practical solution by allowing parties to derive a strong secret key using only low-entropy passwords, which are commonly used and easier to remember than complex cryptographic keys. While two-party PAKE protocols are well-studied, three-party PAKE protocols, where two clients and a server are involved, present unique challenges.

Existing three-party PAKE protocols often suffer from two main weaknesses:

  1. Reliance on Idealized Models: Many are proven secure only in models that assume the existence of "random oracles" or "ideal ciphers." These are theoretical constructs that simplify security proofs but don't perfectly reflect real-world cryptographic primitives like hash functions. This means a protocol proven secure in such a model might be vulnerable when implemented with actual, imperfect functions.
  2. Vulnerability to Insider Attacks: In a three-party setting, one client might attempt to attack another client (an "insider attack"). Existing protocols often fail to provide security against such attacks, especially when the adversary can corrupt participants or launch dictionary attacks to guess passwords.

This paper aims to bridge this gap by proposing a three-party PAKE protocol that is secure in the "standard model" (without random oracles) and explicitly addresses the threat of insider attacks and undetectable online dictionary attacks.

Methods

The paper introduces a novel three-party PAKE protocol and provides rigorous security proofs for it. The core of their methodology involves:

  • Standard Model Security Proofs: The protocol's security is proven in the standard model, meaning it relies on well-established cryptographic assumptions like the Decisional Diffie-Hellman (DDH) assumption and the security of Message Authentication Codes (MACs). This is a significant improvement over protocols relying on random oracles.
  • Indistinguishability-Based Model: The security of session keys is proven using a variant of the indistinguishability-based model by Bellare, Pointcheval, and Rogaway. This is a widely accepted framework for analyzing key exchange protocols, ensuring that an adversary cannot distinguish a real session key from a random one.
  • Explicit Modeling of Insider Attacks: The security model used allows the adversary to corrupt protocol participants. This is crucial for capturing insider attacks, where one party might have compromised credentials or access.
  • Undetectable Online Dictionary Attack Security: The authors introduce a specific definition and proof for security against undetectable online dictionary attacks. This type of attack is particularly insidious because an adversary can repeatedly guess passwords and test them against the system without leaving obvious traces.

The proposed protocol itself builds upon a secure two-party PAKE protocol (referred to as 2PAKE) and incorporates MACs for message integrity and authentication. The protocol involves clients and a server establishing shared secret keys, exchanging nonces, computing Diffie-Hellman-like values, and using MACs to authenticate messages.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Standard Model Gap: The most significant insight is the successful construction of a three-party PAKE protocol that achieves provable security in the standard model, a long-standing goal in the field. This means the protocol's security is more reliably guaranteed in real-world implementations.
  • Comprehensive Security Against Insider Threats: By explicitly modeling participant corruption, the paper demonstrates that their protocol is resilient to insider attacks, a critical consideration for multi-party systems.
  • Tackling Undetectable Dictionary Attacks: The paper provides a formal definition and proof for security against undetectable online dictionary attacks. This is a challenging aspect of PAKE security, and their solution offers a strong guarantee against this sophisticated threat.
  • Modular Security Proofs: The proofs are structured in a modular fashion, building from the security of the underlying two-party PAKE protocol and MAC scheme. This approach makes the proofs more manageable and highlights the dependencies of the overall security.

Key Results

  • First Standard Model Three-Party PAKE: The paper presents the first three-party PAKE protocol proven secure in the standard model against active adversaries with corruption capabilities.
  • Provable Security Against Undetectable Online Dictionary Attacks: The protocol is shown to be secure against undetectable online dictionary attacks, a significant advancement.
  • Mathematical Guarantees: The security proofs provide quantitative bounds on the adversary's advantage, expressed in terms of the complexity of the underlying cryptographic primitives (DDH, MAC security) and the adversary's query complexity. For instance, Theorem 5 bounds the SK security advantage by terms involving the advantage of the underlying 2PAKE protocol, MAC forgery probability, and DDH advantage. Theorem 7 bounds the probability of an undetectable online dictionary attack occurring.

Limitations and Future Work

  • Efficiency: The authors acknowledge that designing a three-party PAKE protocol that is more efficient than their proposed one, while still maintaining provable security in the standard model, is a direction for future work.
  • Protocol Complexity: While the security proofs are rigorous, the protocol itself involves several steps and cryptographic operations, which might impact its practical performance in highly constrained environments.

The paper concludes by emphasizing the importance of their contribution in providing a robust and secure three-party PAKE solution that addresses critical vulnerabilities, paving the way for more secure communication systems in multi-party settings.

Summary updated

Abstract

Protocols for password-only authenticated key exchange (PAKE) in the three-party setting allow two clients registered with the same authentication server to derive a common secret key from their individual password shared with the server. Existing three-party PAKE protocols were proven secure under the assumption of the existence of random oracles or in a model that does not consider insider attacks. Therefore, these protocols may turn out to be insecure when the random oracle is instantiated with a particular hash function or an insider attack is mounted against the partner client. The contribution of this paper is to present the first three-party PAKE protocol whose security is proven without any idealized assumptions in a model that captures insider attacks. The proof model we use is a variant of the indistinguishability-based model of Bellare, Pointcheval, and Rogaway (2000), which is one of the most widely accepted models for security analysis of password-based key exchange protocols. We demonstrated that our protocol achieves not only the typical indistinguishability-based security of session keys but also the password security against undetectable online dictionary attacks.
BibTeX
@article{nam2014password,
  author = {Junghyun Nam and Kim‐Kwang Raymond Choo and Junghwan Kim and Hyun-Kyu Kang and Jin‐Soo Kim and Juryon Paik and Dongho Won},
  title = {{Password-Only Authenticated Three-Party Key Exchange with Provable Security in the Standard Model}},
  journal = {The Scientific World JOURNAL},
  year = {2014},
  doi = {10.1155/2014/825072},
}
Figure