At a company I worked at, I had to change my password every 90 days and I could only reuse a password after 8 iterations. This no-reusal included passwords being too similar to the old one, e.g. when I only changed one letter, that new password was not accepted.
Does that mean they were storing this password in plaintext? This seems rather bad practice to me. Or is there some hash function that allows similarity comparisons?
No, it does not mean they are storing the passwords in plain text. The question doesn't completely describe the behavior. Are they matching patterns only from your current password, or patterns from all 8 of your previous passwords?
If it's the first case, the answer is dead simple, and this is that they have the hashes from the 8 previous passwords to compare against, and when you change your password, you enter your current password as well as your new password, and they now have both of these in plain text to compare for patterns. This is more likely what is happening.
If it is the second case, there are still several other ways this could be done, including storing the passwords in an encrypted (rather than hashed) format, so they can be decrypted and compared, or storing the pattern (or mask) of your passwords along with the hashes and then disallowing new passwords that match any of those old masks. Arguably these options are not as secure as just storing the hashes, but that shouldn't particularly concern you... It's risk to the business not to you, and if they feel it's acceptable risk, then that is their decision. Your only concern (and regardless of the password policy at your company, this should always be a concern for you) is to ensure that the passwords you use for work network are different than the passwords you use everywhere else, so a compromise of your work password doesn't endanger your personal accounts and vice versa.
I can think of a few options
Most probably, they're storing passwords encrypted instead of hashed. This is not as secure as hashing with a strong hash algorithm but as long as the encryption key is properly secured it shouldn't be a problem
Another probable option is to just compare the new password with the previous one when you enter it. You can check if this is true using a forgot password function or trying to use a password similar to a previous one but not the last one
Other option is to take the new password and perform some permutations, substitutions, append and/or substract some characters, then hash this modified password and compare with previous hashes. It's essentially the same as storing hashes for similar passwords when you change it, but that's probably infeasible due to the required space to have that much hashes
The last option, is to have the passwords in plaintext. No need to say how insecure it is
A hash by definition should not allow you to find if it's similar to something else.
From wikipedia:
Have you tested if the system really verify this rule? I cannot think a way to do this without storing password in a recoverable format (such as plaintext or encrypting with a symetric key)
