11

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

Michael
  • 2,391
  • 2
  • 19
  • 36
  • 3
    I fully agree with Tom. Such policies are pointless. Where do you draw the line? Are you going to mandate that passwords must contain at least a symbol and must not be similar to dictionary words like p@ssw0rd, XKCD passphrase like "battery horse staple", etc? – Question Overflow Oct 28 '14 at 02:36
  • You could store old passwords. When the user changes their password, require that they re-enter their current password, store the plaintext and then you can check against this in the future. This doesn't seem like it would decrease the security of your website, but so many people use the same password on multiple sites that it could potentially affect users' security on other sites. – FreeAsInBeer Oct 28 '14 at 12:53
  • Allow "pass phrases" of arbitrary length and users will be less inclined to play games with the sequentially modified passwords. – Hot Licks Oct 28 '14 at 16:32
  • Please read http://security.stackexchange.com/q/4704/971. Forcing your users to change their passwords periodically is usually a bad practice, one that harms security more than it helps. – D.W. Oct 28 '14 at 18:13
  • The accepted answer to your first "Further reading" link gives you the solution employed by Facebook: When the user generates a new password, generate several similar passwords and compare all of their hashes, warning the user if there's a match. This is essentially spending a few seconds to start a brute force of the new password with a "known" starting point of the previous password. – Brian S Oct 28 '14 at 19:48
  • When changing passwords you usually have to type in the old password as well as the new one. They both have to be present in a decrypted form for a short time. If you do a similarity checkup after the user presses change password (where you have both of them in memory), you can tell the user to choose something different. The whole thing needs to be bulletproof and it won't work when the user forgets his/her password, but then the passwords aren't similar anyway. Disclaimer: No security expert, read something similar somewhere once, I guess I'm overseeing something. – WalyKu Nov 17 '16 at 09:44

8 Answers8

19

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.

Tom Leek
  • 168,808
  • 28
  • 337
  • 475
  • 4
    Yes, I read that question. Let's say, then, that I'm _required_ to enforce said password changes, and we can have a brief moment of silence to reflect on policies outside of our control. `;)` – Michael Oct 27 '14 at 21:08
9

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.

PwdRsch
  • 8,341
  • 1
  • 28
  • 35
  • 5
    The problem with storing the previous passwords encrypted is that you don't always know the previous password. What if the user initiates a "forgot password" protocol and doesn't enter their old password? Or what if your database gets compromised and you force them to change their password from a mail link? – Nzall Oct 28 '14 at 09:04
  • "Lovedog90" thanks now I have to change my facebook password =) The Character Map/Topology though, something new (to me) and interesting. – CLo Oct 28 '14 at 13:13
  • @NateKerkhofs Good point. Use of account recovery mechanisms wouldn't work to preserve the old password in encrypted format. In those situations it is less likely that the user's new password will be similar to their old one because they forgot their old one (or at least can't remember it precisely). If you really want to enforce comparison in all cases you would have to consider encrypting the current password at the time of change. – PwdRsch Oct 28 '14 at 14:37
2

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.

Abe Miessler
  • 8,155
  • 10
  • 44
  • 72
  • 1
    You're right to worry about the security implications of storing a bunch of old password hashes. Now an attacker has multiple targets; even if he can't crack the current password hash, he might still get lucky and crack the old password hash, which might help the attacker attack the user's other accounts on other systems -- or might even help the attacker attack the user's current password on this site, if the user is following some kind of pattern in selecting his password. The risk gain/loss equation is non-trivial; it's not clear whether the modest gain is worth the modest additional risk. – D.W. Oct 28 '14 at 18:16
2

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.

  • While it is true that you cannot see every foreseeable pattern, it is more true that humans do not choose from every foreseeable pattern. The research has shown that we choose from an extremely small set of patterns the vast majority of the time, and those are the patterns worth protecting against. – Xander Oct 28 '14 at 18:17
  • @Xander I don't agree. It is true, that humans will use easy patterns first, but when the most obvious patterns are locked, then humans will quickly develop another pattern that is not forbidden. There are countless possible patterns to use. –  Oct 28 '14 at 18:20
  • 1
    `twinkletwinklelittlestarhowiwonderwhatyouare` is good in that it's long, but bad in that it's an actual English phrase (and a well-known one, at that). The XKCD comic is recommending **random** words, not sentences. – Brian S Oct 28 '14 at 19:53
  • @BrianS right, right, I put it only as example of easy remembering idea. –  Oct 28 '14 at 19:56
1

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.

Desthro
  • 1,007
  • 5
  • 5
1

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.

Martijn
  • 359
  • 1
  • 2
  • 9
0

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.

tim
  • 29,018
  • 7
  • 95
  • 119
-2

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)

Florian Bidabé
  • 703
  • 4
  • 10
  • I gotta say that security.stackexchange is a place where it is very easy to get a vote down without explanation/comment. This poor behaviours amongst members are non-constructive and are leading IMO to a platform where the heuristic approach is clearly missing (it is hard to learn from its own mistakes). – Florian Bidabé Oct 30 '14 at 00:42
  • I agree. Though your answer is flawed. A good password policy cannot know what the original password is because you only store the hash of the password. That being said, I suppose you could "check" if the user is changing their own password to a new one, because they typically have to enter both. But if the user has forgotten it and needs it reset, there is no way to tell if they are iterating their passwords or not. (at least with sound hashing policies.) – Desthro Oct 30 '14 at 15:02
  • Thank for your explanation, I edited my comment to correct this – Florian Bidabé Oct 30 '14 at 22:07