This is really more of an addendum to @Brian's clever answer. Hats off also to @Martijn Pieters for adding details about how to brute force the old passwords based on the current one and to @ratchet freak for "hamming distance." I'm not deleting my answer because I think it provides interesting background to back them up.
State of the art password storage requires using multiple rounds of a strong one-way cryptographic hash (SHA-512+) with unique salt (128-bits+) for each user. But do not be tempted to store additional information about each password. The more information you will store about each password, the more you undermine the security of your hashing algorithm.
Consider how easy it becomes to brute-force a password if you know that:
- It's 7 characters long
- Characters 3-5 are upper-case (4 is lower)
- 1 and 7 are numbers
- 6 is a symbol
A US keyboard has 95 printable characters, so knowing that the password is 7 characters long yields 95^7 = 69,833,729,610,000 = 7x10^13 permutations. If it were truly random, it might take a year to crack this on a single 3Ghz processor. But:
- There are only 26 upper-case and 26 lower-case characters
- There are only 10 digits yielding 100 possiblities for those two numbers
- There are only 32 symbols
So (corrected thanks to @Hellion):
26^4 (charcters 2-5 are known upper or lower-case)
x 100 (characters 1 & 7 are digits)
x 32 (character 6 is a symbol)
1,462,323,200 possible passwords.
That's 50,000 times easier to crack! Storing good information to prevent similar passwords in this case has taken your crack time for a 7-character password from a year down to a couple hours. Decoding all your passwords with on a powerful multi-processor desktop with a good video card and a little patience is now very feasible. I hope this simple example demonstrates that the more meaningfully you can compare similar passwords, the less secure your hashing will be.
Importance of Strong Hashing
Databases with passwords are stolen regularly, with gargantuan break-ins in the news every month. Heck, just last month the state of SC lost everyone's social security numbers - oops! How many more of these breaches are covered up?
The most frightening thing for me is when people choose the same or similar password for multiple sites so that breaking into one gives the attacker access to them all. I'd love to see a proven method of preventing that situation, though I think preventing the most common bad passwords would help more than preventing an individual user from reusing their bad password within the same site. The best I can suggest is a company-wide policy to use a secure password manager that generates highly random passwords for each of your users and stores them securely.