International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Spelling-Error Tolerant, Order-Independent Pass-Phrases via the Damerau-Levenshtein String-Edit Distance Metric

Authors:
Gregory V. Bard
Download:
URL: http://eprint.iacr.org/2006/364
Search ePrint
Search Google
Abstract: It is well understood that passwords must be very long and complex to have sufficient entropy for security purposes. Unfortunately, these passwords tend to be hard to memorize, and so alternatives are sought. Smart Cards, Biometrics, and Reverse Turing Tests (human-only solvable puzzles) are options, but another option is to use pass-phrases. 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.
BibTeX
@misc{eprint-2006-21855,
  title={Spelling-Error Tolerant, Order-Independent Pass-Phrases via the Damerau-Levenshtein String-Edit Distance Metric},
  booktitle={IACR Eprint archive},
  keywords={applications / Passwords, Password-Based Authenticated Key Exchange, PAKE, Damerau-Levenshtein String-Edit Distance Metric, Usable Security},
  url={http://eprint.iacr.org/2006/364},
  note={Full version of paper appearing in the Proceedings of the Australasian Information Security and Privacy Workshop gregory.bard@ieee.org 13441 received 20 Oct 2006},
  author={Gregory V. Bard},
  year=2006
}