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

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.