This paper explores methods for making pass-phrases suitable for use with password-based authentication and key-exchange (PAKE) protocols, and in particular, with schemes resilient to server-file compromise. In particular, the $\Omega$-method of Gentry, MacKenzie and Ramzan, is combined with the Bellovin-Merritt protocol to provide mutual authentication (in the random oracle model [CGH04,BBP04,MRH04]. Furthermore, since common password-related problems are typographical errors, and the CAPSLOCK key, we show how a dictionary can be used with the Damerau-Levenshtein string-edit distance metric to construct a case-insensitive pass-phrase system that can tolerate zero, one, or two spelling-errors per word, with no loss in security. Furthermore, we show that the system can be made to accept pass-phrases that have been arbitrarily reordered, with a security cost that can be calculated.
While a pass-phrase space of $2^{128}$ is not achieved by this scheme, sizes in the range of $2^{52}$ to $2^{112}$ result from various selections of parameter sizes. An attacker who has acquired the server-file must exhaust over this space, while an attacker without the server-file cannot succeed with non-negligible probability.
Category / Keywords: applications / Passwords, Password-Based Authenticated Key Exchange, PAKE, Damerau-Levenshtein String-Edit Distance Metric, Usable Security Publication Info: Full version of paper appearing in the Proceedings of the Australasian Information Security and Privacy Workshop Date: received 20 Oct 2006 Contact author: gregory bard at ieee org Available format(s): PDF | BibTeX Citation Version: 20061103:161300 (All versions of this report) Short URL: ia.cr/2006/364 Discussion forum: Show discussion | Start new discussion