Paper 2013/833

Verifier-Based Password-Authenticated Key Exchange: New Models and Constructions

Fabrice Benhamouda and David Pointcheval

Abstract

While password-authenticated key exchange (or PAKE) protocols have been deeply studied, a server corruption remains the main threat, with many concrete cases nowadays. Verifier-based PAKE (or VPAKE) protocols, initially called Augmented-PAKE, have been proposed to limit the impact of any leakage. However, no satisfactory security model has ever been proposed to quantify the actual security of a protocol in the standard model. The unique model proposed so far is an ideal functionality in the universal composability (\UC) framework, but is only meaningful in idealized models. In this paper, we first formally define some properties for the transform (password hashing) applied to the password for the storage on the server-side, for an efficient VPAKE use. A tight one-wayness is required to prevent improved password searches. We then enhance the Bellare-Pointcheval-Rogaway game-based model for PAKE to VPAKE protocols, in such a way that it allows a VPAKE protocol to be secure in the standard model. In addition, we show how to further extend this model to handle non-uniform and related passwords, both in case of PAKE and VPAKE. Finally, we propose very efficient constructions of password hashing and \VPAKE protocols, which are nearly as efficient as the best PAKE protocols to date.