How can a company tell if my password is similar to the previous 5 passwords?
Could be done in a variety of ways:
- Keep a list of the last five passwords used, hopefully encrypted. Not the safest thing obviously, but certainly do-able.
- Keep a list of hashes related to the last five passwords, e.g. full password, first X characters, last Y characters
- Keep a list of characteristic patterns of the last five passwords, e.g. llllllllds. l being letter, d being digit, s being a special character. If the pattern is the same, but the hash different, then it's just too close.
They could store a clear text or encrypted version of your old passwords once they're changed. You said that you'd have to give your previous password, which is clearly available at the time of change. Once changed , it could be stored in a way that allows comparison.
There's a possibility that it's done "right" for certain values of "right". E.g. If you reuse any of those passwords on other sites, that'd still not be good.
They can do that even if all they have is proper strong hashes from the previous passwords, as long as their idea of “similar” is sufficiently narrow. Take the new password and enumerate all the passwords they consider similar. For each variation, calculate the hash with the salt for each previous password. If there are P previous passwords and N similar passwords, the cost is P × N hash calculations. Those calculations may be performed in parallel if they have enough hardware, so you can't tell how many hash calculations they perform from the time it takes to do the verification.
5 × N gets large pretty quickly. Just trying all one-letter variations on an 8-letter case-insensitive password would be 1000 calculations, for example. But with heuristics such as only varying digits (e.g. swordfish5 → swordfish4) or removing repeated letters (e.g. swordfishh → swordfish), the number could stay manageable.
A mild way in which they can cheat is to always use the same salt for a given account. Then the cost of trying variations is independent of the number of previous passwords. Reusing the same salt after a password change on the same account immediately reveals if two passwords are the same, but other than that it doesn't make attacks easier.