This question is a follow-up to a comment by Tobias Kienzler to an answer to "What is the purpose of the “Password minimum age” setting?".
Consider a password policy that new passwords cannot be identical to the current password or any of the user's five passwords that precede the current password. Nor can they be similar to the current password or any of these previous passwords, where "similar" is defined as Levenshtein distance 2 or less. (For the sake of this question, assume no complexity requirement other than six or more characters, one letter and one digit.) This protects against, say, "bush41", "clinton42", "bush-43" (which should be stopped), "obama44" (which should be allowed), and either "clinton 45" or "bush 45" (either of which should be stopped).
The ordinary password change flow requires the current password so that someone can't run a password change with a Firesheeped session cookie. The alternate password change flow sends a reset token through another channel, such as e-mail, voice, or text. In the ordinary flow, I can test whether the new password is similar to the current password by using the Levenshtein distance function from a library. But I don't have the previous password; all I have are salted PBKDF2 hashes. Nor can I test for similarity to the current password if the user has entered a password reset token instead of the current password.
In the aforementioned comment, Tobias Kienzler recommended to "compute all mutations of the new password within the unacceptable edit distance, calculate their hashes and compare them to old password hashes (with the respective salts)." In an answer to "Password security", an answer to "Does Facebook store plain-text passwords?", and an answer to "How can a system enforce a minimum number of changed characters in passwords, without storing or processing old passwords in cleartext?", apsillers, Michał Šrajer, and Ori suggested something similar.
But I don't see how it's tractable on present hardware to compute the set of all strings with Levenshtein distance 2 from a given 20-plus-character passphrase and hash them all, especially with an intentionally slow hash like PBKDF2 and a large character set like Unicode. It would appear to require around h(nc)s hashes, where h is the length of the history (here 5), n is the number of characters in a password (and thus the number of positions in which a replacement or insertion can occur), c is the number of characters in the character set (95 for printable ASCII or much larger for printable Unicode), and s is the maximum edit distance to call two passwords "similar".
So what is this computationally feasible way to test a password for similarity to previous passwords without storing previous passwords with reversible encryption? Would it require applying any or all of the following simplifications to the definition of similarity, and if so, would those simplifications compromise the password system's security in practice?
- Require all characters in passwords to be printable ASCII (space to ~).
- Reduce the Levenshtein distance of a "similar password" to 1.
- Compare only the current password for similarity and the previous passwords only for identity.
- Willfully sacrifice availability to protect password confidentiality. When a user requests a password change, lock out the user for the remainder of the day while the system enumerates all possible similar passwords, and disallow other users from changing their passwords if too many users' similarity searches are queued.