hash-like algorithm to identify passwords which are “too similar” to previous ones from history

Question

One common issue with secure passwords is that users tend to "cheat", one common cheating pattern we meet recently is the "password swap" antipattern where the user basically keeps using the same two passwords forever. e.g.:

• Password1!
• Secret2$
• Password3!
• Secret4$

This antipattern works because:

• any new passwords is completely different from the previous one
• the history of hashes does not contain any exact match

is there any algorithm which is "similar" to an hash but allows to extract a distance metric from the current plain text password in order to avoid those risks?

Here is my analysis so far

• Hashing explicitly requires that "similiar" passwords turn to very different hashes: otherwise it would be very easy to converge from a generic password toward the one that generated the hash. Any "hash"-like algorithm which allows to calculate a metric of distance from the current password would be a security threat.
• I can't think of any workaround to come up with an hash which allows to measure "similarity" without giving away some kind of "distance" metric: which as stated above would render it insecure
• Another approach would be storing hashes of subsets of the password. E.g. we store the hash of the previous 10 passwords + the hash of the previous passwords minus the last two chars: this one would block the above example. However in order to work we might have to collect too many hashes of too small substrings (eg. every group of 6 chars) and this would give away the plain text password!

Answer 1

My understanding is that the typical solution for this is to keep a history of the old password hashes and associated salts.

Then when a new password is being set, apply a number of simple variations to the new string (including none) and generate the hash for it. This is similar to what cracking engines do but on a more limited scale. If any of these variations match one of the historical hashes, you reject the password.

It's worth nothing, however, that forcing the user to change passwords regularly is not necessarily a good practice

No more expiration without reason. This is my favourite piece of advice: If we want users to comply and choose long, hard-to-guess passwords, we shouldn’t make them change those passwords unnecessarily.

https://pages.nist.gov/800-63-FAQ/#q-b05

Answer 2

Similarity hashing and all such related techniques are highly insecure when applied to passwords. Currently, it seems that best practices are:

• DO apply password strength metrics
  • minimum length
  • check against databases of known compromised passwords
• DO NOT keep data about historical passwords
• MAYBE ensure that a new password is substantially different from the previous password

Whether the new password should be different depends on the reason why the password was changed.

• “I forgot my password” → no substantial changes required
• scheduled password rotation → such policies encourage insecure passwords and should be replaced in favour of strong passwords and/or 2FA
• password is known compromised → ensuring a different password makes sense

When updating a not-forgotten password, the update form will require the old password for confirmation. At that point you can compare the old password against the new password, and perform similarity checks on the plaintext. Afterwards, the plaintext can be discarded.

Answer 3

I don't think this is possible. You need information about the previous passwords in order to compare them, but you don't want to store the same information. The two are mutually exclusive.