1

One common issue with secure passwords is that users tend to "cheat", one common cheating pattern we meet recently is the "password swap" antipattern where the user basically keeps using the same two passwords forever. e.g.:

  • Password1!
  • Secret2$
  • Password3!
  • Secret4$

This antipattern works because:

  • any new passwords is completely different from the previous one
  • the history of hashes does not contain any exact match

is there any algorithm which is "similar" to an hash but allows to extract a distance metric from the current plain text password in order to avoid those risks?

Here is my analysis so far

  • Hashing explicitly requires that "similiar" passwords turn to very different hashes: otherwise it would be very easy to converge from a generic password toward the one that generated the hash. Any "hash"-like algorithm which allows to calculate a metric of distance from the current password would be a security threat.
  • I can't think of any workaround to come up with an hash which allows to measure "similarity" without giving away some kind of "distance" metric: which as stated above would render it insecure
  • Another approach would be storing hashes of subsets of the password. E.g. we store the hash of the previous 10 passwords + the hash of the previous passwords minus the last two chars: this one would block the above example. However in order to work we might have to collect too many hashes of too small substrings (eg. every group of 6 chars) and this would give away the plain text password!
Improve this question
7
  • 2
    The problem is forcing the user to change passwords.
    – Caleth
    Apr 29, 2020 at 11:38
  • 1
    Or at least, forcing your users to change their password too often.
    – Robin Bennett
    Apr 29, 2020 at 11:40
  • 1
    Or requiring them to come up with these byzantine combinations of characters in the first place, combinations that do nothing to improve security and probably actually compromise it. xkcd.com/936
    – Robert Harvey
    Apr 29, 2020 at 13:22
  • 1
    Thank god that answerers realise that the password treadmill was a bad idea. God help us that some questioners still think it is a good idea.
    – Steve
    Apr 29, 2020 at 14:32
  • You seem to want locality-sensitive hashing. These are not cryptographically secure hashes, as they will make collisions between similar inputs more likely instead of less likely. Plus supplementing a cryptographically secure hash with a locality-sensitive hash is giving information to the people trying to do a preimage attack.
    – Theraot
    Apr 30, 2020 at 5:54

3 Answers 3

Reset to default
3

My understanding is that the typical solution for this is to keep a history of the old password hashes and associated salts.

Then when a new password is being set, apply a number of simple variations to the new string (including none) and generate the hash for it. This is similar to what cracking engines do but on a more limited scale. If any of these variations match one of the historical hashes, you reject the password.

It's worth nothing, however, that forcing the user to change passwords regularly is not necessarily a good practice

No more expiration without reason. This is my favourite piece of advice: If we want users to comply and choose long, hard-to-guess passwords, we shouldn’t make them change those passwords unnecessarily.

https://pages.nist.gov/800-63-FAQ/#q-b05

Improve this answer
3
  • "No more expiration without reason" is something I strongly encourage but there are essentially two reasons for this: 1. passwords get compromised without users knowing, 2. laws and customer's policies imposing that. So password must be changed periodically. The trick here is not forcing it to often. This variation-attack approach so far seems the best one!
    – Simone Avogadro
    Apr 29, 2020 at 16:50
  • @SimoneAvogadro If you go this route you should probably learn more about how crackers come up with variations and/or find pre-built solutions for this. Essentially you want to mimic what an attacker would attempt given knowledge of a previous password.
    – JimmyJames
    Apr 29, 2020 at 17:27
  • I agree: the point is understanding if it exists any literature/common knowledge of how to deal with that issue. I'll mark your reply as a solution as it's the closes one, even if I get that we don't really know which are those "variations" which we must apply (see my example of 4 passwords and it's not trivial to overcome that)
    – Simone Avogadro
    Oct 21, 2020 at 14:10
6

Similarity hashing and all such related techniques are highly insecure when applied to passwords. Currently, it seems that best practices are:

  • DO apply password strength metrics
    • minimum length
    • check against databases of known compromised passwords
  • DO NOT keep data about historical passwords
  • MAYBE ensure that a new password is substantially different from the previous password

Whether the new password should be different depends on the reason why the password was changed.

  • “I forgot my password” → no substantial changes required
  • scheduled password rotation → such policies encourage insecure passwords and should be replaced in favour of strong passwords and/or 2FA
  • password is known compromised → ensuring a different password makes sense

When updating a not-forgotten password, the update form will require the old password for confirmation. At that point you can compare the old password against the new password, and perform similarity checks on the plaintext. Afterwards, the plaintext can be discarded.

Improve this answer
5
  • Do you have a reference about not storing the old hashes/salts?
    – JimmyJames
    Apr 29, 2020 at 14:32
  • 1
    @JimmyJames I don't have a reference, but deleting unnecessary data and reducing the impact of a data breach is general best practice.
    – amon
    Apr 29, 2020 at 15:00
  • I don't disagree but there is a tradeoff. If all you check against is the previous password, a 'smart' user can just keep flipping back and forth between the same 2 forever. I think the main risks of keeping the old hashes would be if they reused it somewhere else or if your similarity checks weren't good enough. I didn't see that anywhere in the skimming the NIST FAQ but if you've seen this recommendation, it would be interesting to know the source, at the very least.
    – JimmyJames
    Apr 29, 2020 at 15:08
  • 1
    @JimmyJames a user shouldn't flip between two passwords because they should never be required to change their strong password, unless it is considered compromised. This is extremely rare, and whether the old compromised password is kept arguably doesn't matter. Password reuse and credential stuffing is a core problem of password-based authentication. If you keep old hashes of non-compromised passwords, this provides extra ammunition to a successful attacker.
    – amon
    Apr 29, 2020 at 15:41
  • I understand the risks, I'm just not 100% sure they are significant enough to rule this out in general. Additionally, the risk is really the user's and not (directly) related to the system you are protecting. A lot of this comes down to your threat model, I suppose. The idea that you shouldn't force changes is based on relative risk. An attacker with a hashes and unbounded time has a better chance of gaining access than if those hashes expire. If we ignore user behavior then clearly expiry is a better solution.
    – JimmyJames
    Apr 29, 2020 at 17:22
0

I don't think this is possible. You need information about the previous passwords in order to compare them, but you don't want to store the same information. The two are mutually exclusive.

Improve this answer
4
  • 1
    Facebook saves a history of the old hashes. This alone already allows you to detect password re-use. When you change your password, Facebook also doesn't compute just one hash, instead it computes the hash of the password you entered, plus some hashes of popular permutation patterns, e.g. prepending or appending month names, prepending or appending numbers, flipping the case of upper-/lowercase characters, and it compares those hashes against its history.
    – Jörg W Mittag
    Apr 29, 2020 at 15:14
  • 1
    E.g. when you change your password and enter password123, Facebook will not only generate h("password123"), but also h("password122"), h("password121"), h("password124"), h("password125"), h("Password123"), h("pAssword123"), h("passw0rd123"), h("p4ssword123"), and so on and so forth.
    – Jörg W Mittag
    Apr 29, 2020 at 15:16
  • @JörgWMittag - that sounds like it should be an answer
    – Robin Bennett
    Apr 29, 2020 at 15:26
  • That's very similar to @JimmyJames and his one is more general
    – Simone Avogadro
    Oct 21, 2020 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.