Password similarity

OK, so I followed the suggestion of Michael Hampton and went and looked at the code of pam_cracklib.c and it seems as if pam_cracklib gets the old (aka current) password from the PAM via a function call (that I deem totally ok, as I just entered that current password to authenticate) and then performs a similarity analysis (distance function) between that old password and the new one I just entered.

But it does not do this analysis for all old passwords in its history. That would not be possible, cause they are only stored as hashes. For them there can only be a check if they are the same. So everything seems to be in order, just like I expected, but now I do understand why it is... thanks everyone.

Your old passwords are not stored in plain text.

Instead, your old password hashes are stored in /etc/security/opasswd by PAM. It then makes the comparison when you go to change your password, based on what has been specified in the PAM configuration.

An example PAM config:

password required pam_unix.so sha512 remember=12 use_authtok

Here, remember causes it to remember 12 previous passwords.

For further detail, see Linux Password Security with pam_cracklib.