How can a system enforce a minimum number of changed characters in passwords, without storing or processing old passwords in cleartext?

Question

In some environments, it is required that users change a certain number of characters every time they create a new password. This is of course to prevent passwords from being easily-guessable, especially with knowledge of old passwords such as a departed employee might have for a shared service account.

I have separate questions open to address button-pushing side of this enforcement. However, I'm also curious as to how this enforcement works on the back end. If a cleartext password cannot be derived from a strong hashing algorithm, how does the system determine how many characters have been changed in new passwords?

Answer 1

I'm not sure about comparing with all the passwords the user has previously used, as it really depends on the hashing system your using and I would say if its possible to derive any similarity from the hash then its not a very good system to begin with.

But assuming that the user has to supply their current password when setting their new password, you could at least check the new one against the current one as you'll have both as unhashed at that point.

The pam_cracklib module on Linux checks passwords like this and does a few basic checks by default.

• Is the new password just the old password with the letters reversed ("password" vs. "drowssap") or rotated ("password" vs. "asswordp")?
• Does the new password only differ from the old one due to change of case ("password" vs. "Password")?
• Are at least some minimum number of characters in the new password not present in the old password? This is where the "difok" parameter comes into play.

You can find some more details about it here.

Answer 2

This is easily done on password change (where the user is and should be asked to provide both old and new password).

Answer 3

Usually, when you change your password, you need to enter the old password first. This is useful for security, to ensure that someone walking by your computer can't very quickly change the password and lock you out while your back is turned. It also allows the server to enforce password distance rules. The server only needs to keep the old password in memory for as long as it takes to verify that the new password is sufficiently different from the old one. It never needs to store the unhashed password.

By the way, such password changing rules are bad for security. (Yes, I know you're the victim here.) If users have to change their password often, they will either choose a password that's very easy to remember, or write it down in an easily-accessible place. There is little advantage in password expiration, and the expected loss in password strength from making users change their password every few months more than offsets those advantages. For a more in-depth treatment of password expiration, see How does changing your password every 90 days increase security? and Is forcing users to change passwords useful? and Requiring regular password change but storing previous passwords?

Answer 4

Usually, when you change your password, you need to enter the old password first. This is useful for security, to ensure that someone walking by your computer can't very quickly change the password and lock you out while your back is turned. It also allows the server to enforce password distance rules. The server only needs to keep the old password in memory for as long as it takes to verify that the new password is sufficiently different from the old one. It never needs to store the unhashed password, and can erase the old hash as soon as it has stored the new one.

If the server checks equality with older passwords, not just the last one, that's a different story. It's easy enough to check password reuse with old hashes: for each old hash, compute the hash of the new password with the old salt and compare with the old hash value. On a properly configured system, this should take a few seconds.

It's a different matter if the server is checking similarity with older passwords, and not just equality with older passwords plus similarity with the previous one. If the server is using proper hashes, then it must try variations on the new password and hash each variation with all of the old salts. That could take minutes or more with a non-negligible number of variations. So if the server is complaining about similarity with an older password, I would be wary that they may be storing improperly-hashed passwords.

There is another approach for similarity, which is to store the hash of each password variation, each independently salted, as soon as the password is set. But that doesn't buy you much: the server still needs to calculate the hash of the new password with all these salts, which still takes a long time, too long for a typical password change.

A way to recover old passwords that actually works, but that I've never seen implemented anywhere, is to do the following on a password change, after prompting the user for the old password and before erasing the old password from memory:

• Derive a symmetric key from the new password (using a key strengthening algorithm).
• Derive a key from the old password in the same way.
• Decrypt the list of old passwords with the old key.
• Append the former password to the list.
• Make the policy checks — all prior passwords are known at this point. If the new password passes the checks…
• Encrypt the list of old passwords with the new key.
• Change the password and the encrypted list of prior passwords the database.

This is somewhat risky because if the current password is compromised, all prior passwords are also exposed. But it does allow to enforce a password distance policy to any number of prior passwords with a reasonable computation effort.

Answer 5

The user should enter both old and new password for a password change. So comparing the new password to the old one can easily be done because the plaintext version is given by the user.

For comparing the new password against previous passwords (other than the current one), checking can only be done by comparing the hash-results. Any method that would allow any other comparison would be a security hole.

Answer 6

It can be done only by keeping hashes, it could even be done over several iterations.

The method would be to take the password and iterate it through the hashing algo and check for comparisons against the stored values.

For instance, most users (and service desk folks love to fallback on this as a last resort with angry-important types) will iterate their passwords incredibly simply.

So taking the password: #foob@r1 and making it #foob@r2 which you're likely to see can be tested without knowledge of #foob@r1 by performing a brute force on the algo quickly. With modern processing power you could iterate through the first 4 characters in less than ten seconds.

Though for efficiency sake the last four are typically the ones people change so you're likely to see bigger bang for your buck there. If you're going to do non-consecutive and consecutive you're looking at a pretty big wait for the end user and a big chunk of processor.