How does Linux know that the new password is similar to the previous one?

A few times I tried to change a user password on various Linux machines and when the new password was similar to the old one, the OS complained that they were too similar.

I always wondered, how does the system know this? I thought that the password is saved as a hash. Does this mean that when the system is able to compare the new password for similarity the old one is actually saved as plain text?

Since you need to supply both the old and the new password when using passwd, they can be easily compared in plaintext, in memory, without writing them somewhere on the drive.

Indeed your password is hashed when it's finally stored, but until that happens, the tool where you're entering your password can of course just access it directly like any other program can access things you entered on your keyboard while it was reading from STDIN.

This is a feature of the PAM system which is used in the background of the passwd tool. PAM is used by modern Linux distributions.

More specifically, pam_cracklib is a module for PAM which allows to reject passwords based on several weaknesses that would make them very vulnerable.

It's not just passwords which are too similar that can be considered insecure. The source code has various examples of what can be checked, e.g. whether a password is a palindrome or what the edit distance is between two words. The idea is to make passwords more resistant against dictionary attacks.

See also the pam_cracklib manpage.

At least in my Ubuntu, the "too similar" messages cames out when: "...more than half of the characters are different ones...." (see below for details). thanks to the PAM support, as clearly explained in the @slhck answer.

For other platform, where PAM is not used, the "too similar" messages comes out when: "...more than half of the characters are different ones...." (see below for details)

To further check this statement on your own, it's possible to check the source-code. Here is how.

The "passwd" program is included in the passwd package:

verzulli@iMac:~$ which passwd
/usr/bin/passwd
verzulli@iMac:~$ dpkg -S /usr/bin/passwd
passwd: /usr/bin/passwd

As we're dealing with Open Source technologies, we have unrestricted access to source code. Getting it is as simple as:

verzulli@iMac:/usr/local/src/passwd$ apt-get source passwd

Afterwards it's easy to find the relevant fragment of code:

verzulli@iMac:/usr/local/src/passwd$ grep -i -r 'too similar' .
[...]
./shadow-4.1.5.1/NEWS:- new password is not "too similar" if it is long enough
./shadow-4.1.5.1/libmisc/obscure.c:     msg = _("too similar");

A quick check to the "obscure.c" gives out this (I'm cut-and-pasting only the relevant piece of code):

static const char *password_check (
    const char *old,
    const char *new,
    const struct passwd *pwdp)
{
    const char *msg = NULL;
    char *oldmono, *newmono, *wrapped;

    if (strcmp (new, old) == 0) {
            return _("no change");
    }
    [...]
    if (palindrome (oldmono, newmono)) {
            msg = _("a palindrome");
    } else if (strcmp (oldmono, newmono) == 0) {
            msg = _("case changes only");
    } else if (similar (oldmono, newmono)) {
            msg = _("too similar");
    } else if (simple (old, new)) {
            msg = _("too simple");
    } else if (strstr (wrapped, newmono) != NULL) {
            msg = _("rotated");
    } else {
    }
    [...]
    return msg;
}

So, now, we know that there's a "similar" function that based on the old-one and the new-one check if both are similar. Here's the snippet:

/*
 * more than half of the characters are different ones.
 */
static bool similar (const char *old, const char *new)
{
    int i, j;

    /*
     * XXX - sometimes this fails when changing from a simple password
     * to a really long one (MD5).  For now, I just return success if
     * the new password is long enough.  Please feel free to suggest
     * something better...  --marekm
     */
    if (strlen (new) >= 8) {
            return false;
    }

    for (i = j = 0; ('\0' != new[i]) && ('\0' != old[i]); i++) {
            if (strchr (new, old[i]) != NULL) {
                    j++;
            }
    }

    if (i >= j * 2) {
            return false;
    }

    return true;
}

I haven't reviewed the C code. I limited myself in trusting the comment just before the function definition :-)

The differentiation between PAM and NON-PAM aware platforms is defined in the "obscure.c" file that is structured like:

#include <config.h>
#ifndef USE_PAM
[...lots of things, including all the above...]
#else                           /* !USE_PAM */
extern int errno;               /* warning: ANSI C forbids an empty source file */
#endif                          /* !USE_PAM */

The answer is far simpler than you think. In fact, it almost qualifies as magic, because once you explain the trick, it's gone:

$ passwd
Current Password:
New Password:
Repeat New Password:

Password changed successfully

It knows your new password is similar... Because you typed the old one in just a moment before.