TL;DR
This paper introduces the first provably secure, two-round, three-party password-only authenticated key exchange (PAKE) protocol. It also identifies a critical flaw in a previously proposed two-round PAKE protocol, demonstrating its failure to achieve implicit key authentication against active adversaries.
What Problem Does This Paper Address?
In modern digital communication, securely establishing shared secret keys between parties is fundamental. Password-Only Authenticated Key Exchange (PAKE) protocols aim to achieve this using easily remembered passwords instead of complex cryptographic keys. This is particularly useful for scenarios where users might not manage complex keys. The paper focuses on the "three-party setting," which involves two clients and a trusted server. This setting is more complex than two-party PAKE due to the increased attack surface, especially from malicious clients attempting dictionary attacks against each other. A key challenge in PAKE protocol design is achieving security with minimal communication rounds, as fewer rounds translate to faster and more efficient communication. While several three-party PAKE protocols exist, many lack formal security proofs, are proven only in restricted models, or have been found vulnerable. Specifically, the paper addresses the lack of a provably secure, two-round, three-party PAKE protocol that is secure against active adversaries.
Methods
The authors propose a novel two-round, three-party PAKE protocol, dubbed "2R3PAKE." This protocol is designed to be generic, meaning it can be constructed from any secure two-party PAKE protocol. The core idea is to combine a secure two-party PAKE protocol with message authentication codes (MACs) and symmetric encryption to achieve the desired three-party security properties. The protocol's security is rigorously proven in a widely-accepted adversary model that allows for participant corruption and active attacks. This model is adapted from Bellare, Pointcheval, and Rogaway's work.
A significant part of the paper is dedicated to analyzing a previously proposed two-round, three-party PAKE protocol (NWPAKE-2 by Wang, Hu, and Li). The authors demonstrate a specific attack that exploits a weakness in NWPAKE-2, showing that it fails to provide implicit key authentication, a crucial security property. This attack involves an unregistered adversary who can intercept messages and compute session keys without being a legitimate participant.
The security proof for 2R3PAKE employs a standard hybrid argument, progressively transforming the security experiment into one where the adversary has no advantage. This involves reducing the security of 2R3PAKE to the security of the underlying two-party PAKE protocol, MAC scheme, symmetric encryption scheme, and the Decisional Diffie-Hellman (DDH) assumption.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The first provably secure two-round, three-party PAKE: This is a significant contribution, filling a gap in the existing literature for efficient and secure PAKE protocols in a common setting.
- Generic construction: The proposed 2R3PAKE protocol's ability to be built from any secure two-party PAKE protocol makes it flexible and adaptable.
- Critical flaw in NWPAKE-2: The paper highlights a subtle but important security failure in a previously published protocol, demonstrating the importance of thorough security analysis even for protocols with claimed proofs. The failure to achieve implicit key authentication is particularly concerning as it can lead to session key compromise.
- No idealizing assumptions: The security proof for 2R3PAKE is conducted without making simplifying assumptions about the cryptographic primitives, making the proof more robust and applicable to real-world implementations.
- Importance of message encryption: The authors emphasize that encrypting ephemeral public values (X and Y) is crucial for security, a lesson learned from the flaws in previous protocols.
Key Results
- 2R3PAKE Protocol: The paper presents a new two-round, three-party PAKE protocol that is proven secure in a robust adversary model.
- NWPAKE-2 Vulnerability: The paper demonstrates that the NWPAKE-2 protocol fails to achieve implicit key authentication against active adversaries, invalidating its claimed security proof.
- Security Proof: The security of 2R3PAKE is formally proven, showing its advantage is bounded by the advantages of its underlying components (2PAKE, MAC, symmetric encryption, DDH). Specifically, the advantage is bounded by: $Adv^{AKE}_{2R3PAKE}(t, Q) \leq 2 \cdot Adv^{AKE}_{2PAKE}(t', Q') + 2q_{send} \cdot Adv^{suf-cma}_{MAC}(t', 2, 2) + 2q_{send} \cdot Adv^{ind-seav}_{SE}(t') + 2 \cdot Adv^{DDH}_{G}(t')$ where $q_{send}$ is the number of send queries, and $t'$ and $Q'$ are related to the time and query complexity of the adversary.
Limitations and Future Work
- Simplified Protocol: The authors note that Steps 3 and 6 of their proposed protocol can be omitted if security against undetectable online dictionary attacks is not strictly required. This simplified version would still be AKE-secure.
- One-Round Impossibility: The paper suggests that designing a provably secure, one-round, three-party PAKE protocol might be impossible, though they do not formally prove this statement. This opens a direction for future research to explore the theoretical limits of PAKE protocols in this setting.
- Efficiency: While the protocol is efficient in terms of communication rounds, further analysis of its computational efficiency and practical performance in real-world scenarios would be valuable.
Summary updated