[jandrese]

This doesn't seem practical at all. The combinatoral explosion would make the storage requirements impractical for everything but the absolutely most trivial cases like incrementing a number as the very last digit. Even in your simple example you're talking about storing 256 different hashes just to catch one possible mutation on a way too short password.

[andrewaylett]

You can store a normalised form -- so if the password is `PaSsWoRd` and the user tries to change it to `pA55wOrD`, a normalisation that lower-cases, turns 1 and i into l, turns 2 and 5 into s, and turns 4 into a, would normalise both to `password`.

Or if you want a slightly more convoluted mechanism, when someone changes their password you have both in plain-text and you can take a copy of the old password at that point -- after all, it's not being used as a password any more! For bonus fun, submit all previous passwords to pwned passwords. Password reuse makes this a bad idea in general, specific policies attempting to mandate it will not be an issue notwithstanding.

[eqvinox]

Technical/pedantic answer: you can store a 'normalized' hashed form of the password, e.g. before hashing it, convert it to all lowercase, replace all digits with 0, sort the characters, … and then do the same to the new password before hashing it, so a whole bunch of stuff will compare "equal".

Practical/actual answer: this is stupid either way.

[strken]

You could use a Bloom filter, and just gaslight your users when a false positive happens.