Password-Based Public-Key Cryptography: Submissions and Research Contributions


Strong Password-Only Authenticated Key Exchange
David Jablon, September 1996.
Presented at the November 1996 meeting.

A new simple password exponential key exchange method (SPEKE) is described. It belongs to an exclusive class of methods which provide authentication and key establishment over an insecure channel using only a small password, without risk of off-line dictionary attack. SPEKE and the closely-related Diffie-Hellman Encrypted Key Exchange (DH-EKE) are examined in light of both known and new attacks, along with sufficient preventive constraints. Although SPEKE and DH-EKE are similar, the constraints are different. The class of strong password-only methods is compared to other authentication schemes. Benefits, limitations, and tradeoffs between efficiency and security are discussed. These methods are important for several uses, including replacement of obsolete systems, and building hybrid two-factor systems where independent password-only and key-based methods can survive a single event of either key theft or password compromise.

Paper:

External Reference:


The Secure Remote Password Protocol
Thomas Wu, August 1997 (Updated November 1997).
Presented at the
August 1997 meeting.

SRP-3 is a new password authentication and key-exchange protocolsuitable for authenticating users and exchanging keys over anuntrusted network. It resists dictionary attacks mounted by eitherpassive or active network intruders, provides perfect forwardsecrecy, and stores passwords in a form that is not plaintext-equivalentto the password itself, so an attacker who captures the passwordfile cannot use it directly to compromise security and gain immediateaccess to the host. This new protocol combines techniques of zero-knowledgeproofs with asymmetric key exchange protocols and offers significantlyimproved performance over comparably strong extended methods.

Paper:

External Reference:


Secure Network Authentication with Password Identification
Philip MacKenzie and Ram Swaminathan, August 1999.
Presented at the August 1999 meeting.

A password authentication protocol called SNAPI is proposed for inclusion in the P1363adocument. SNAPI provides mutual authentication between a client and server based solely ona password, and does not require the client to store any other information (except the codethat runs the protocol). SNAPI is the first protocol of this type that is provably secure againstactive adversaries (i.e., adversaries that can not only eavesdrop on communication, but alsoimpersonate parties and replay messages), and in particular, does not reveal any informationto active adversaries that would allow an off-line dictionary attack on the password. Security isproven in the random-oracle model and is based on the security of RSA. SNAPI also provides forkey exchange (as secure as Diffie-Hellman), allowing a secure session to be initiated. A variant,SNAPI-X, is also proposed, in which the server stores a one-way function of the password,and does not allow an adversary who compromises the server to impersonate a client (withoutactually running a dictionary attack on the password file).

The protocols described in this contribution are from the paper, Secure Network Authentication with Password Identification [MS].

Paper:


The AuthA Protocol for Password-Based Authenticated Key Exchange
Mihir Bellare and Phillip Rogaway, February 2000 (updated March 2000).

We suggest a simple protocol, AuthA, for the problem of password-based authenticated key exchange (AKE). We assume the asymmetric trust model: the client A has a password pwa and the server B has a particular one-way function of this, pwb. Then an authentication tag, AuthA, is flowed from the client to the server. This tag is just the hash of some values easily computable by both parties. The server checks the received tag prior to accepting the session key.The protocol just sketched provides security against dictionary attack, and it ensures forward secrecy and client-to-server authentication. Server-to-client authentication can be added cheaply, by flowing a second authentication tag, AuthB, from server to client.

Paper:


Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords
Jonathan Katz, Rafail Ostrovsky & Moti Yung, February 2000.

There has been much interest in password-authenticated key-exchange protocols which remain secure even when users choose passwords from a very small space of possible passwords (say, a dictionary of English words). Under this assumption, one must be careful to design protocols which cannot be broken using off-line dictionary attacks in which an adversary enumerates all possible passwords in an attempt to determine the correct one. Many heuristic protocols have been proposed to solve this important problem. Only recently have formal validations of security (namely, proofs in the idealized random oracle and ideal cipher models) been given for specific constructions [3,10,22].

Very recently, a construction based on general assumptions, secure in the standard model with human-memorable passwords, has been proposed by Goldreich and Lindell [17]. Their protocol requires no public parameters; unfortunately, it requires techniques from general multi-party computation which make it impractical. Thus, [17] only proves that solutions are possible "in principal". The main question left open by their work was finding an efficient solution to this fundamental problem.

We show an efficient, 3-round, password-authenticated key exchange protocol with human-memorable passwords which is provably secure under the Decisional Diffie-Hellman assumption, yet requires only (roughly) 8 times more computation than "standard" Diffie-Hellman key exchange [14] (which provides no authentication at all). We assume public parameters available to all parties. We stress that we work in the standard model only, and do not require a "random oracle" assumption.

Paper:

External Reference:
Proposal for P1363 Study Group on Password-Based Authenticated-Key-Exchange Methods
Bellare, Jablon, Krawczyk, MacKenzie, Rogaway, Swaminathan & Wu, February 2000 (updated March 2000).

We suggest standardizing methods for password-based authenticated key exchange. The scope of this effort is focused on methods where the client uses only a password; No supplementary keys or certificates are required. We believe this to be an important problem for cryptographic practice, and judge the area to be about ready for a standard.The scope of this effort may include methods with different forms and trust models, with varying degrees of functionality. The standard will be written in a manner that describes the security goals for these methods, and presents the essential structure of these methods with respect to these goals. The standard should specify requirements for underlying primitive operations used by these methods to facilitate the use of replaceable or upgradable components where necessary and practical.

Proposal:


Ultimate Solution to Authentication via Memorable Password
Taekyoung Kwon, May 2000.

A new password authentication and key agreement protocol called AMP is proposed in a provable manner. Human-memorable password authentication is not easy to provide over insecure networks due to the low entropy of the password. A cryptographic protocol, based on the public-key cryptography, is the most promising solution to this problem. AMP provides the password-verifier based authentication and the Diffie-Hellman key agreement, securely and efficiently. AMP is easy to generalize in any other cyclic groups. Verifier-based protocols allow the asymmetric model in which a client possesses a password, while a server stores its verifier. AMP is actually the most efficient protocol among those protocols. The number of exponentiation in AMP is exactly the same to the number in the Diffie-Hellman scheme. We give a rigorous comparison to the related protocols.

Proposal:


Paper:


Addendum:


Extended Password Key Exchange Protocols Immune to Dictionary Attacks
David Jablon, June 1997.
Presented at the March 2001 meeting.

This paper describes an extension to password-authenticated key exchange protocols that further limits exposure to theft of a stored password-verifier, and applies it to several protocols, including SPEKE. Alice proves knowledge of a password C to Bob, who has a stored verifier S, where S=gC mod p. They perform a SPEKE exchange based on the shared secret S to derive ephemeral shared key K1. Bob chooses a random X and sends gX mod p. Alice computes K2=gXC mod p, and proves knowledge of {K1,K2}. Bob verifies this result to confirm that Alice knows C. Implementation issues are summarized, showing the potential for improved performance over Bellovin & Merritt's comparably strong Augmented-Encrypted Key Exchange.

The paper also corrects a problem in [Jab96].

Paper:

External Reference:
EC-SRP
Yongge Wang, June 2001.
Presented at the
May 2001 meeting, updated May 2002.

This document contains possible additions to IEEE P1363.2/D2001-05-14 (rough draft), namely, inclusion of an elliptic curve group based SRP protocol.

Paper:


Server-Assisted Generation of a Strong Secret from a Password
Warwick Ford & Burt Kaliski, June 2000.
Presented at the August 2001 meeting.

A roaming user, who accesses a network from different client terminals, can be supported by a credentials server that authenticates the user by password then assists in launching a secure environment for the user. However, traditional credentials server designs are vulnerable to exhaustive password guessing attack at the server. We describe a new credentials server model and supporting protocol that overcomes that deficiency. The protocol provides for securely generating a strong secret from a weak secret (password), based on communications exchanges with two or more independent servers. The result can be leveraged in various ways, for example, the strong secret can be used to decrypt an encrypted private key or it can be used in strongly authenticating to an application server. The protocol has the properties that a would-be attacker cannot feasibly compute the strong secret and has only a limited opportunity to guess the password, even if he or she has access to all messages and has control over some, but not all, of the servers.

Paper:

External Reference:
Password Authentication Using Multiple Servers
David Jablon, April 2001.
Presented at the
May 2002 meeting.

Safe long-term storage of user private keys is a problem in client/server systems. The problem can be addressed with a roaming system that retrieves keys on demand from remote credential servers, using password authentication protocols that prevent password guessing attacks from the network. Ford and Kaliski's methods [11] use multiple servers to further prevent guessing attacks by an enemy that compromises all but one server. Their methods use a previously authenticated channel which requires client-stored keys and certificates, and may be vulnerable to offline guessing in server spoofing attacks when people must positively identify servers, but don't. We present a multi-server roaming protocol in a simpler model without this need for a prior secure channel. This system requires fewer security assumptions, improves performance with comparable cryptographic assumptions, and better handles human errors in password entry.

Paper:

Slides:

External Reference:
SRP-4
David Jablon, May 2002.
Presented at the
May 2002 meeting.

This document describes APKAS-SRP4, a password-authenticated key agreement scheme that is a hybrid of the APKAS-SRP (SRP-3) and APKAS-BSPEKE2 (B-SPEKE) schemes that are defined in the current draft of [P1363.2], blending benefits of each. It uses an optimized exponential computation similar to that used in APKAS-SRP, and a prime order password-derived generator as in APKAS-BSPEKE2. Some other benefits of SRP4 over other methods in [P1363.2] are increased speed over APKAS-BSPEKE2 and elimination of the "two-for-one" guessing attack and message ordering requirement of APKAS-SRP.

Further definition of and references for SRP-3 and B-SPEKE can be found in [P1363.2], and a related Internet Draft that discusses SRP-4 is [Jab2002].

Paper:


The PAK suite: Protocols for Password-Authenticated Key Exchange
Philip MacKenzie, May 2002.
Presented at the
May 2002 meeting.

The main purpose of this document is to give a complete and accurate description of the PAK protocol and some variants, in support of standardization efforts in password-authenticated key exchange. We provide complete proofs of security for PAK and its variants, which we believe are more straighforward than the original proofs. We also show a new general method (called the Z-method) for making these protocols resilient to server-compromise, so as to not allow an attacker that obtains password verification data from a server to then impersonate a user. When this method is applied to PAK, we call the resulting protocol PAK-Z. Finally, we discuss the current state-of-the-art in password authenticated key exchange, with respect to both theory and practice.

Paper:


Submission Update to PAK Schemes
Philip MacKenzie, received September 9, 2002.
.

This is a proposed update to P1363.2 draft D2002-08-10, with changes highlighted in Red. With reference to the PAK suite submission, it replaces the PAK-X scheme with the PAK-Z scheme, which only uses the normal PAK primitives, and deletes the PAK-X primitives.

Paper:


SRP-6: Improvements and Refinements to the Secure Remote Password Protocol
Thomas Wu, Arcot Systems, October 29, 2002.
.

Abstract. This document addresses two specific security and operational issues with the Secure Remote Password Protocol, the first being the "two-for-one" active password guessing attack by an attacker posing as a server, and the second being the message ordering property which requires that the server wait for the client's first exponential residue before sending its own. The effect that these improvements have on real-world implementations of SRP is also explored.

This submission update was accompanied by the suggestion that P1363.2 draft D2002-08-10 be amended to have distinct schemes for both SRP3 and a new amended scheme (here named SRP6), with all of the explanations and footnotes for the two-for-one attack moved to the SRP6 schemes, leaving SRP3 for RFC2945 compatibility.

Paper:


Authentication via Memorable Passwords - Revised Submission to IEEE P1363.2
Taekyoung Kwon, received October 31, 2002.
.

This submission update includes changes to the AMP schemes and primitives described in P1363.2 draft D2002-08-10 to address two-for-one guessing and improved efficiency.

Abstract. Authentication via Memorable Passwords (AMP) protocols were proposed lately as one of password security protocols being discussed by the IEEE P1363 standards working group. This revised submission makes indispensable revision and extension to the AMP. A complete set of AMP protocols will include AMP, TP-AMP, TP-AMP2, N-AMP, M-AMP, EC-AMP, and XTR-AMP. Note that this revised submission is yet in draft. The complete submission is expected sooner or later. Firstly, in this document, {DL,EC}PEPKGP-AMP-SERVER, {DL,EC}SVDP-AMP-CLIENT, {DL,EC}SVDP-AMP-SERVER, and {DL,EC}APKAS-AMP-{CLIENT,SERVER} were partly modified for AMP.

Paper:


Authentication via Memorable Passwords - Revised Submission to IEEE P1363.2
Taekyoung Kwon, received June 14, 2003.
.

Submission update on the AMP schemes and primitives.

Paper:


Summary of AMP (Authentication and key agreement via Memorable Passwords
Taekyoung Kwon, received August 22, 2003.
.

This document summarizes the so-called AMP protocols.

Paper:


Addendum to Summary of AMP
Taekyoung Kwon, received November 20, 2003.
.

This document corroborates the AMP protocols by making some minor modification to the previous work. So the final versions of AMP are described for November 2003 discussion by the IEEE P1363 Standard Working Group. The contribution includes AMP and TP-AMP protocols.

Paper:


Revision of AMP in IEEE P1363.2 and ISO/IEC 11770-4
Taekyoung Kwon, received June 8, 2005.
.

This document describes a security problem in the draft version of APKAS-AMP and proposes the substitution of either of the formerly submitted AMP+ or AMP2 protocols for resolving it.

Paper:


OPAKE: Password Authenticated Key Exchange based on the Hidden Smooth Subgroup assumption,
Craig Gentry, Philip MacKenzie, and Zulfikar Ramzan, presented August 19, 2005.
.

Presentation of a new password-based public key technique.

Slides:


PAK-Z+,
Craig Gentry, Philip MacKenzie, and Zulfikar Ramzan, presented August 19, 2005.
.

Paper presents a revised version of the PAK-Z protocol, PAK-Z+, and a proof of its security.

Paper:


This page was last modified on December 8, 2005.
IEEE Logo IEEE Standards Logo IEEE P1363 Logo
IEEE Home Page IEEE Standards IEEE P1363