Let's say that in the password policy the password history is defined to remember the last 10 passwords.
I understand password history exists so that if a password is recovered from a compromised database by some attacker, chances are way less likely that password is actually the user's current password.
However, if upon periodic password reset, the users simply appends '1' to his old password, and on the next period reset he appends let's say '2', this greatly decreases the effectiveness of periodic password resets. As soon as the attacker recovers two old passwords of the same user in clear text, he will see the pattern and can guess the actual current password of the user...
The best practice is to hash (+ salt) passwords, however as far as I can see this makes it impossible to check whether the user simply appended a single digit to his old password or not.
The passwords could be encrypted instead of hashed, which would address my concern, however I don't like the idea of passwords being reversible to plain text without bruteforce attacks.
I am wondering what the best solution would be to prevent users from making this minor changes to their old password when resetting it? Can it be technically achieved in a very secure manner, or does this definitely require user awareness?