pam_pwhistory.so is a PAM module and so is pam_pwquality.so, pam_unix.so and others.
When stacked in the file /etc/pam.d/common-password, they are invoked in the same order they are stacked in ... So, breaking down what is happening in your case(i.e. in the order you stacked those modules):
First, your password is evaluated for quality by:
password requisite pam_pwquality.so retry=3
If it passes that, then it is changed with:
password [success=1 default=ignore] pam_unix.so obscure use_authtok try_first_pass sha512
So, as you see, at this point your new password is accepted and set (pam_unix.so is the module that changes your password) without checking your user password history whatsoever.
Later, what this module:
password required pam_pwhistory.so remember=5
does and result in, is merely printing:
Password has been already used. Choose another.
and passwd exits with failure as per the status of the last invoked module:
passwd: Have exhausted maximum number of retries for service
passwd: password unchanged
when it's too late.
To fix that, stack PAM modules in the correct order that yields the result you expect i.e. like this:
# /etc/pam.d/common-password - password-related modules common to all services
#
# This file is included from other service-specific PAM config files,
# and should contain a list of modules that define the services to be
# used to change user passwords. The default is pam_unix.
# Explanation of pam_unix options:
#
# The "sha512" option enables salted SHA512 passwords. Without this option,
# the default is Unix crypt. Prior releases used the option "md5".
#
# The "obscure" option replaces the old `OBSCURE_CHECKS_ENAB' option in
# login.defs.
#
# See the pam_unix manpage for other options.
# As of pam 1.0.1-6, this file is managed by pam-auth-update by default.
# To take advantage of this, it is recommended that you configure any
# local modules either before or after the default block, and use
# pam-auth-update to manage selection of other modules. See
# pam-auth-update(8) for details.
# here are the per-package modules (the "Primary" block)
password requisite pam_pwquality.so retry=3
password required pam_pwhistory.so remember=5 use_authtok
password [success=1 default=ignore] pam_unix.so obscure use_authtok try_first_pass sha512
# here's the fallback if no module succeeds
password requisite pam_deny.so
# prime the stack with a positive return value if there isn't one already;
# this avoids us returning an error just because nothing sets a success code
# since the modules above will each just jump around
password required pam_permit.so
# and here are more per-package modules (the "Additional" block)
# end of pam-auth-update config
Notice, as well, the addition of the use_authtok option to prevent the module from prompting for a password and use the previous stacked module's password instead ... Use that option if you have to use another module like pam_pwquality.so before it or otherwise that option should not be used.
