Password-Only Authenticated Three-Party Key Exchange Proven Secure against Insider Dictionary Attacks

Junghyun Nam, Kim‐Kwang Raymond Choo, Juryon Paik, Dongho WonThe Scientific World JOURNAL 2014 · DOI

TL;DR

This paper introduces the first provably secure three-party password-only authenticated key exchange (PAKE) protocol that withstands insider dictionary attacks. They achieve this by presenting a novel protocol compiler that transforms any secure two-party PAKE protocol into a secure three-party one, along with a simplified framework for formally modeling dictionary attacks.

What Problem Does This Paper Address?

Establishing secure communication channels often relies on key exchange protocols. When these protocols use passwords for authentication (PAKE), a significant vulnerability arises from "dictionary attacks," where an attacker tries to guess passwords. This problem is particularly tricky in a three-party setting (e.g., two users and a server) because one user might be a malicious insider, already registered with the server, and can thus launch attacks that are harder to detect. While many three-party PAKE protocols exist, proving their security against these insider dictionary attacks has been a major challenge, with existing protocols often lacking formal proofs or being secure only in restricted models. This paper aims to fill this gap by providing a protocol and a formal framework that guarantees security against these sophisticated attacks.

Methods

The authors propose a two-pronged approach:

  1. A Protocol Compiler (H3PAKE): They introduce a generic construction called H3PAKE that takes any secure two-party PAKE protocol and "compiles" it into a secure three-party PAKE protocol. This compiler adds two communication rounds and uses a hashed session key for enhanced security. Crucially, it doesn't require the underlying two-party protocol to provide client-to-server authentication, making it broadly applicable. The security proof for H3PAKE is based on the Gap Diffie-Hellman (GDH) assumption and the security of the underlying two-party PAKE protocol.
  2. A New Security Modeling Framework: The paper presents a simplified and intuitive way to model dictionary attacks in the three-party PAKE setting. They clarify the relationship between session key indistinguishability and password security, and introduce a specific definition for "undetectable online dictionary attacks" (UD online dictionary attacks). This framework allows for a more direct and less complex security analysis compared to previous approaches.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "Insider" Threat is Critical: The paper highlights that many existing three-party PAKE protocols, while seemingly secure, are vulnerable to attacks from registered users (insiders) who can leverage their legitimate access to compromise the system.
  • A Compiler for Robustness: The H3PAKE compiler is a significant contribution, offering a modular way to build secure three-party protocols from existing secure two-party ones. This "plug-and-play" approach simplifies protocol design and verification.
  • Hashing the Session Key Matters: The use of a hashed session key (H(pid||sid||K)) in H3PAKE, as opposed to just the raw Diffie-Hellman key, is key to achieving security against insider attacks, a feature lacking in some prior constructions.
  • Simplifying Attack Modeling: The new framework for modeling UD online dictionary attacks makes it easier to reason about and prove security against these specific threats, reducing the complexity of formal verification.
  • GPAKE's Vulnerability: The paper demonstrates that even a well-known protocol like GPAKE can be vulnerable to insider UD online dictionary attacks if its underlying components (2-party PAKE and 3-party key distribution) lack sufficient authentication properties.

Key Results

  • First Provably Secure 3-Party PAKE against Insider Dictionary Attacks: The paper presents H3PAKE, the first three-party PAKE protocol with a formal proof of security against both insider and outsider dictionary attacks (online and offline).
  • H3PAKE Security Proof: The protocol is proven secure in the random oracle model under the Gap Diffie-Hellman (GDH) assumption and the security of the underlying two-party PAKE protocol.
  • GPAKE Security Analysis: The paper provides a detailed analysis of GPAKE, showing its security against UD online dictionary attacks depends heavily on the specific instantiations of its building blocks.

Limitations and Future Work

  • Random Oracle Model: The security proof for H3PAKE relies on the random oracle model, which is a common but theoretical assumption. Future work could aim for security proofs in the standard model.
  • Efficiency: While H3PAKE provides strong security guarantees, future research could focus on developing protocols that achieve similar security levels with fewer communication rounds or improved efficiency.
  • Practical Implementations: The paper focuses on theoretical security proofs. Further work could explore the practical implementation and performance of H3PAKE.

Summary updated

Abstract

While a number of protocols for password-only authenticated key exchange (PAKE) in the 3-party setting have been proposed, it still remains a challenging task to prove the security of a 3-party PAKE protocol against insider dictionary attacks. To the best of our knowledge, there is no 3-party PAKE protocol that carries a formal proof, or even definition, of security against insider dictionary attacks. In this paper, we present the first 3-party PAKE protocol proven secure against both online and offline dictionary attacks as well as insider and outsider dictionary attacks. Our construct can be viewed as a protocol compiler that transforms any 2-party PAKE protocol into a 3-party PAKE protocol with 2 additional rounds of communication. We also present a simple and intuitive approach of formally modelling dictionary attacks in the password-only 3-party setting, which significantly reduces the complexity of proving the security of 3-party PAKE protocols against dictionary attacks. In addition, we investigate the security of the well-known 3-party PAKE protocol, called GPAKE, due to Abdalla et al. (2005, 2006), and demonstrate that the security of GPAKE against online dictionary attacks depends heavily on the composition of its two building blocks, namely a 2-party PAKE protocol and a 3-party key distribution protocol.
BibTeX
@article{nam2014password,
  author = {Junghyun Nam and Kim‐Kwang Raymond Choo and Juryon Paik and Dongho Won},
  title = {{Password-Only Authenticated Three-Party Key Exchange Proven Secure against Insider Dictionary Attacks}},
  journal = {The Scientific World JOURNAL},
  year = {2014},
  doi = {10.1155/2014/802359},
}
Figure