How to securely counter users from adding a single digit to their old password upon creating a new one?

You can't. Your users are doing this because the reset mechanism has become obtrusive to them getting work done. People are clever enough to get around any of the mechanisms you're going to devise. Those that aren't will quickly learn from those that are. Information like this travels fast.

If you somehow were to figure out how to counter the password1 password2 password3 scheme that people commonly use, you'll almost instantly be confronted with a new scheme. 1password 2password 3password. Now you see a NEW pattern, and simply iterate all numbers. So the user comes up with a yet better scheme. passwordA passwordB passwordC. You'll spend weeks coming up with a counter-measure, only to be defeated in 10 minutes by a clever person who thought of something you didn't.

The point being, that the users ability and cost to get past your counter-measures far outweigh your ability to continually develop new schemes to try to prevent them.

The solution is simply to stop seeing your users as adversaries who you're trying to defeat. They aren't. Users are simply trying to get things done, and you've put up a barrier to do so. If this really bothers you so much, you need to adjust your attitude towards the users and work with them to come up with something that suits BOTH your needs, and doesn't create an adversarial relationship.

Easy enough: You have a prospective password of "password1". Test "password" and "password0" to see if they work with the old hash. There's no need to see the plaintext of the old password for this to work.

However, this isn't going to work for the reasons Steve Sether lays out.

This has been discussed at various points, and most discussions seem to come back to the concept of password topologies - the patterns which lots of passwords have. There is a good OWASP presentation on YouTube, which suggests that a lot of passwords which have to follow complexity rules follow similar patterns:

• Password1! - If you enforce at least one character from each of uppercase letters, lowercase letters, digits, and special characters, lots of people will pick a capitalised word, followed by a number, with the special character at the end, which will often be ?, !, or . - the topology is UL+DS (using a sort of regex style syntax)
• Password1 - if you don't enforce a special character, you usually won't get one
• password1 - if you don't enfore an uppercase letter, you usually won't get one, but if you do, it'll be at the start
• qwertyuiop - if you don't enforce anything, you get things that are easy to type

There is also some dispute about the value of regularly changing passwords, because they tend to encourage exactly the behaviour you are seeing. However, they are sometimes required due to the relatively slow pace of business choices.

This gives rise to the suggestion of enforcing not just a password change, but a password topology change. The password reset process becomes:

1. User enters old password (e.g. Password1!), and new password (MyS3cret$) in reset form
2. System calculates topology of both old password (UL+DS) and new password (ULUDL+S)
3. System rejects password change if the topologies match, or if the new password does not match the complexity rules

It is also possible to reject certain common topologies completely - maybe you don't want any passwords of the Password1! form, in which case you configure your system to reject any password which has the topology UL+DS.

Never store the topology of a password with it - if your database gets compromised, you would have given attackers a fantastic way to minimise their effort to crack the recovered passwords.

Bear in mind that users will still come up with ways to make weak passwords: they might start alternating Password1! and !2Password, but that suggests that the password change frequency is too high.