Sequential password updates

Question

Let's say I have a reasonable KDF, and that I make users change their passwords periodically and keep some old password hashes to prevent password reuse.

What's to stop the user from changing the passwords (when they're required to) in some predictable sequence?

hammurabi1
hammurabi2
hammurabi3

or

winona2014Q3
winona2014Q4
winona2015Q1

or some other obvious permutation of a "base" password?

Obviously, I can't store the plaintext of a password to check sequences, and hammurabi3 by itself is innocuous. It might be a pattern or it might not.

Is the benefit to changing passwords invalidated because users have the opportunity to change them to almost-but-not-quite the same password?

Is there something I can do to improve that flaw (if it's a flaw)?

Further reading

• Does Facebook store plain-text passwords?
• Why does Facebook bother comparing old and new passwords?
• Logging "password with counter" use
• How can a system enforce a minimum number of changed characters in passwords, without storing or processing old passwords in cleartext?

Answer 1

You cannot reasonably prevent "sequence passwords" unless you have a human administrator inspect them (which would have its own set of security issues, not even considering the expensiveness of human labour). You can try to automatically detect such patterns, but you cannot hope to find them all; besides, if you only keep hashes of the previous passwords, then pattern detection will have to be a guess-and-try process, which will be expensive.

Moreover, your users will find the pattern detection system inconvenient (since it prevents sequence passwords that they are quite fond of), so they will fight against it: they will be angry (not a good idea when users are customers), and they will be creative, finding new sequences that you did not thought of.

Benefit to changing passwords is not invalidated by sequence passwords. Benefit to changing passwords is invalidated by regular password changes being bloody useless (see this question for more discussions on that subject). The flaw is not in the "sequence passwords"; it is in the policies that mandate regular password changes for the sake of misunderstood very old traditions that don't make sense when the users wield computers and try to buy stuff from Web sites, instead of wielding rifles and trying to send enemy soldiers to the afterworld. These policies are the reason why users resort to sequence passwords in the first place.

Answer 2

There are a few different ways to check whether users' old and new passwords are similar, and each has its own strengths and weaknesses.

String Permutation Comparison

The first approach relies on creating a list of permutations that are not allowed. This might be a list of regular expressions or some similarly defined string changes that you evaluate passwords against. For example, you look for a number in the password and increment it, you look for a month name and try the next month name, etc. The altered new password is then compared to the old password to see if they match.

This can quickly become complicated if you're trying to come up with your own list of forbidden modifications because you need to define a minimum baseline of what transformations pose too great a security risk. If you want some ideas you can look at the appendix of this paper from UNC researchers where they list the transformations they used to compare the password histories of users. That paper is also a great resource for establishing the extent of password history similarities in a normal environment.

Algorithmic Comparison

As an alternative to creating a list of rules, you can evaluate an algorithmic comparison of the two passwords, like the Levenshtein distance or Hamming distance. This allows you to pretty much say 'I just don't want the passwords to be more similar than X' where X is some minimum value of change that you decide. This works pretty well to stop people who are doing things like going from "Muffins10" to "Muffins11" but not as well if they're going from "August14" to "November14".

This article discusses evaluating Levenshtein distance values of passwords in the context of making password cracking rule improvements, but it provides a decent overview (and code) of how this evaluation takes place.

Character Mask/Topology Comparison

A third option is to forgo looking at characters specifically and look instead at the character format. You can convert characters into their respective character types, creating a mask or topology. The password "Muffins10" would become ULLLLLLDD (with U = Uppercase, L = Lowercase, D = Digits, S = Symbol). Then you can prevent a user from choosing a new password with an exact or similar mask to their previous password.

This is a very aggressive policy to implement because it also prevents you from going from "Muffins14" to "Lovedog90" even though they don't appear to be related (unless your dog is named Muffins). KoreLogic has been working on implementing this in their PathWell Topologies project, albeit as part of a larger effort to prevent use of less secure password masks at any point. I believe their system allows you to prevent reuse of masks between the new and previous passwords.

Probably the biggest challenge with any of these approaches is communicating to users why their new password choice was rejected. Do you give them a generic error that the passwords are too similar or do you specifically call out why the new password isn't acceptable?

Some users may struggle to choose a acceptable new password under these systems unless you guide them through correcting the problems. You can offer instructions on how to create better passwords, but this will involve changing habits for a lot of people and will likely be met with resistance.

How To Compare Historic Passwords

Ok, so how do you make these comparisons when you only have a database of strongly hashed historic passwords and not the plaintexts?

During the password change process you will probably already prompt the user for their existing password as well as their new password, which provides you with the chance to compare those two in plaintext. That addresses the immediate evaluation and probably is effective enough against password similarities in the long term for most users. However, you may have some users that figure out that they can rotate between two different password variations every other password: Muffins10 --> 11Cupcakes --> Muffins12 --> 13Cupcakes

If you are really worried about that threat you unfortunately don't have a lot of options. You can use a string permutation approach to convert the new password with each rule, then hash it, and look for hash matches in that user's history. Neither of the other two approaches are compatible with hashed passwords. EDIT: Actually, I realized a character mask/topology approach would still work if you stored the historic mask (ideally encrypted) either alongside the historic password hash or instead of it.

But if you are using one of the recommended 'expensive' hashing algorithms then running through your rules and hashing several hundred results is going to use a lot of processing time. Will users tolerate a 5 second, 10 second, or longer delay before finding out whether their password was accepted? That is quite a change from the norm and may not be acceptable for some organizations.

The alternative to this is not hashing password histories but instead encrypting them. You can maintain only a hash for the current password, but during the password change process you would store the expired password as an encrypted data blob. This would allow you to decrypt historic passwords during the password change process and use any of the approaches to look for password similarities.

In theory it isn't terribly risky to store previous passwords using encryption. Both because encryption does work pretty well when properly implemented, and because the old password is no longer valid so knowledge of it shouldn't provide attackers with much advantage. This is especially true after you've implemented measures to prevent similarities between current and past passwords.

I fully recognize some people may not see this as an acceptable alternative since it would place the password history at a slightly greater risk of disclosure. However, I am not alone in seeing the benefits of using encryption in this situation, as this paper explains.

Answer 3

If you store previous password hashes you could potentially check to see if the current password is a variation like you suggested. Say your users previous password was:

password = 5f4dcc3b5aa765d61d8327deb882cf99

If you store previous version of password hashes, you can compare variations of the new password to determine if it is different enough. So you would take their new password: password1 and create hashes of the different variations:

password = 5f4dcc3b5aa765d61d8327deb882cf99
password0 = 305e4f55ce823e111a46a9d500bcb86c
password2 = 6cb75f652a9b52798eb6cf2201057c73
etc.

and if any of these match one of the previous hashes you could reject the new password.

I'm not sure what the security implications of storing a bunch of old password hashes for users would be. I would suggest investigating that before implementing something like this.

Answer 4

Short answer:

Nothing can stop the users from changing the passwords in some predictable sequence.

Detailed answer:

You can try various ways of detecting sequential password changes, but users will always find a simple sequence pattern that you haven't foreseen. If not number suffix - then number prefix, if not numbers - then letters. If not suffixes and prefixes - than additional character put in the sequential position of password, like this:

xpassword
pxassword
paxssword
pasxsword
etc.

You simply cannot foresee every possible idea.

Far better idea for improve password security is to force good length of the password. The password like:

twinkletwinklelittlestarhowiwonderwhatyouare

Is extremely easy to remember, easy to type for someone who can type, and far more difficult to crack, than such hard to remember password like:

aD@79]s^

Look at this famous xkcd comic strip - it is fun, but still truly points the whole idea.

Answer 5

There are a number of different possibilities that you can implement to try and curtail password permutations. One of the best ones that I could find was actually on stackoverflow: https://stackoverflow.com/questions/21031661/how-do-you-test-if-two-hashes-passwords-are-similar

The only problem is, you have to store a ton of password hashes. You can also try and implement limitations on common iterative password types, like banning Q/q# at the end, years as yyyy, and forcing numbers to not be at the beginning or end of a password. (That doesn't stop them from incrementing with letters, but it's a start.)

Otherwise, without storing the password with reversible encryption, there's no easy way to do it for sure.

Answer 6

A fairly simple method would be to check if the last value is a number, subtract one, use the old function to check wether it matches the old pass:

// We start with 'example1', md5 -> c1285a470f0fc8f14f54851c5d8eb32f
$pass = 'example2';
$lastChar = substr($pass,-1);
if( ctype_digit( $lastChar ) ){
    // the last character is digit, substract one:
    $pass2check = substr($pass,0, -1).($lastChar-1); // example2 -> example1
    // Now perform the check check:
    if( md5($pass2check)==$oldValue ){
        echo "User just added +1 to their pass";
    }
    else{
        Echo "new password, now drop md5 and use something real";
    }
}

You can expand this to a more complex system. I.e. in PHP you could take ord() to get the ASCII value, add 1 and use chr() to translate back to a character. This would do exampleA vs exampleB.

Answer 7

Is the benefit to changing passwords invalidated because users have the opportunity to change them to almost-but-not-quite the same password?

Yes, I would say it is. If you do want to have sequential password updates, I would try to prevent users from choosing similar passwords.

Is there something I can do to improve that flaw (if it's a flaw)?

Have the user enter the current as well as the new password (this is not strictly necessary as you could just hash variants of the new password and compare them to the old hash, but it will make comparison a lot easier, and it will also allow you to analyze how your users reuse passwords).

Then, you can just compare the passwords and check where they differ (I would use the hamming distance (for example you could require a minimum distance of 2 or 3, additional characters would add a distance of one).

I doubt that a lot of users would use sequential passwords for every second password update, but if this is a concern you can use a simple approach in addition to the approach above: if the new password contains a number at the end, increase it by one, hash it, and compare it to the list of previous hashes. You can test the passwords habits of your users to determine more rules for hashing and comparing.

Users can still find ways around this, for example, they could use qetuo, and then adgjl, and then zcbm.1 and so on (you can analyze password changes for these behaviors and forbid them).

But you can never completely prevent password recycling on a technical level. If this is really important to you, you have to do it on a policy level.

Answer 8

Some tools (hashcat) can perform password permutation attack based on a dictionary or initial password, it opposes a possible password hash against the current password hash (that was captured somehow) : You cannot use this tool to prevent your user from following this pattern. In the same fashion, you cannot use hashes to recognizes password patterns, this would defeat the initial purpose or definition of a hash. (Wikipedia : A hash can be used to map digital data of arbitrary size to digital data of fixed size, with slight differences in input data producing very big differences in output data)