On the security of a password-only authenticated three-party key exchange protocol

Junghyun Nam, Kim-Kwang Raymond Choo, Juryon Paik, Dongho Won

Abstract

Password-only Authenticated Key Exchange (PAKE) protocols are designed to establish secure communication channels using only low-entropy passwords. This paper presents a cryptanalysis of the S-EA-3PAKE protocol, a three-party PAKE scheme proposed to allow two clients to establish a session key via a trusted server. Despite a formal proof of security in the random oracle model, we demonstrate that the protocol is fundamentally insecure. Specifically, it is vulnerable to man-in-the-middle attacks, allows malicious insiders to perform offline dictionary attacks to recover passwords, and fails to maintain the semantic security of the session key.

Introduction

In a three-party PAKE (3PAKE) setting, two clients, $A$ and $B$, who do not share a common secret, wish to establish a high-entropy session key. They each share a unique, low-entropy password with a trusted server $S$. The S-EA-3PAKE protocol, introduced by Lee and Hwang in 2010, was designed to achieve this goal efficiently. However, a closer examination reveals significant "blind spots" in its design, particularly regarding the threat posed by malicious registered users.

Protocol Overview

The S-EA-3PAKE protocol relies on initial key exchanges between the clients and the server to establish intermediate keys, which are then used to facilitate the final session key between $A$ and $B$. The initial phase involves the generation of keys $k_{AS}$ and $k_{BS}$ using the respective passwords $pw_A$ and $pw_B$.

Figure 1: The initial key exchange phases between clients and the server in the S-EA-3PAKE protocol.

As shown in Figure 1, client $A$ and server $S$ compute $k_{AS} = g^{xu}$ through a series of message exchanges involving blinded values $X^*$ and $U^*$. A similar process is followed by client $B$ and the server to establish $k_{BS} = g^{yv}$.

Cryptanalysis and Vulnerabilities

The authors identify three primary logical attack scenarios that exploit the mathematical structure of the protocol.

1. Identity Spoofing and Man-in-the-Middle Attacks

The protocol fails to provide implicit authentication. An attacker $C$ can intercept communication between $A$ and $B$, tricking the server into believing two separate sessions are occurring. By manipulating the message flow, $C$ can establish independent keys with both $A$ and $B$. Consequently, $A$ and $B$ believe they have a secure direct connection, while $C$ can transparently intercept and modify all traffic.

2. Offline Dictionary Attacks by Malicious Insiders

A major oversight in the original security model was the exclusion of "Corrupt" queries, assuming all clients were honest. A malicious registered client can exploit the mathematical substitution in the key exchange process. By injecting specific random values, an attacker can create a mathematical relationship that allows for an offline dictionary attack. This enables the attacker to test millions of password guesses against captured data on their own hardware until the victim's password is recovered.

3. Failure of Semantic Security

The protocol commits a common cryptographic error: reusing the final session key as a key for a Message Authentication Code (MAC) sent over the public network. This "leaks" information about the key. A passive eavesdropper can verify a candidate session key by checking if it matches the transmitted MAC, thereby breaking the semantic security of the protocol with 100% certainty.

Key Insights

The failure of S-EA-3PAKE underscores several critical principles in protocol design:

  • Identity Binding: Authenticators must explicitly include the identities of the participants and the session-specific exchange values to prevent "cut-and-paste" attacks.
  • Key Separation: Session keys should never be used for multiple purposes (e.g., both encryption and MAC generation) within the same protocol context.
  • Robust Security Models: A "provably secure" protocol is only as strong as the model used for the proof. Models must account for realistic adversaries, including malicious insiders.

Conclusion

The vulnerabilities in S-EA-3PAKE demonstrate that formal proofs can be misleading if the underlying model is insufficient. To mitigate these issues, the authors suggest modifying the authenticators to bind the session to specific participant identities and exchange values. However, providing a formal proof for such a modified protocol in a model that includes malicious insiders remains an open challenge in the field of three-party PAKE design.

Summary updated

BibTeX
@article{nam2013security,
  author = {Junghyun Nam and Kim-Kwang Raymond Choo and Juryon Paik and Dongho Won},
  title = {{On the security of a password-only authenticated three-party key exchange protocol}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2013},
  url = {https://openreview.net/forum?id=Gt3B4Y6C5Se},
}
Figure