Forgot your password: "New password must have a minimum of 4 characters different from the previous password"

Question

This was found on a password reset feature of a government website, where you enter your username, then it takes you to a screen where you can

• enter a new password
• enter confirmation of new password
• answer a security question (about your first pet's name)

And then submit the form, which changes your password.

My questions:

1. How do you securely store a password, but still be able to do this kind of validation, checking that a new password is at least 4 characters different from an old password stored in the database. I'm after a technical explanation of this.
2. Am I correct in saying that this flow seems insecure to begin with? The only thing you need to know to change someone's password is their username and a single security question.

Answer 1

It is mathematically possbile do what they are doing securely to store passwords in a manner that would enable that feature but would not have the old password stored in plaintext. But just because it is mathematically possible, does not mean that it is likely.

Homomorphic encryption

At Eurocrypt 2004 Michael Freedman, Kobbi Nissim, and Benny Pinkas presented a paper that explicitly addressed how to efficiently find the intersection of two sets without revealing the contents of either set (other than the intersection) to anyone who didn't have it before. It is also possible to find an estimate of the size of the intersection without even revealing (much about) the intersection itself.

Now that was in 2004 (and was based on previously work). So there have been improvements since then in this and related algorithms. So there are known techniques for finding out how many characters are common to two sets without revealing the contents of either set. (In the case you are asking about, it is only one set, the old password, that needs to be concealed as the system is given the full new password.)

Bloom filters

If we are talking about overlap of sequences of four characters (instead of just characters in both passwords), then a reasonably secure way of doing this is with a Bloom Filter. A Bloom Filter is a special sort of hash table. Each four character substring of the original password could be added to the Bloom filter when that password given to the service and then all four character substrings of the new password can be looked up in the Bloom filter.

Note that Bloom filters are designed for when there are lots of members of the set and are probabilistic. They can give false positives.

The obvious answer is sadly correct

I would be astounded if the site in question is using homomorphic encryption or even Bloom filters. They are almost certainly doing it a manner in which the operators of the site (and anyone who breaches them) have access to the plaintext passwords.

Answer 2

This sounds bad for a number of reasons.

1. The passwords are being stored in a manner where they can be retrieved in cleartext, quickly, so they can be compared with new passwords.
2. The storage of passwords clearly is not using a one-way hash.
3. If the system storing these passwords is compromised the attacker would subsequently have access to all organization members actual passwords.
4. The use of a pet name for a security question is bad because for many people this is public information and not a secret.
5. You didn't specify, but if the password reset process does not use an out-of-band verification method (like e-mail or SMS, both of which have their own issues) to authenticate that a valid user changed their password but directly allows access to any attacker that requests a password change that is really bad.

Note: You didn't specify your location but I will mention that I have seen more government, and military, organizations with amazingly horrible security in places. This happens, it shouldn't, but it occasionally does.

Answer 3

It is a really interesting question on how do you securely store a password, but still be able to do this kind of validation, checking that a new password is at least 4 characters different from an old password stored in the database.

If one were to design a way to securely store the password, but still allow this kind of validation, it could be done like this:

1. Take all of the letters in the password, and sort them alphabetically, and uniquely. Its important to sort them and to remove duplicates, otherwise you saving the full password.
2. Hash the password securly (PBKDF2 or crypt).

3. Store the list of letters, and the hash. Dont store the actual password.

   • original password: thisisareallyaweseompaSSw0rd!!!
   • stored letters: !0Sadehilmoprstwy
   • stored hash: (Sha512 hash)

This is how you could actaully keep track of the letters used, while not storing the actual password. It is still a terrible idea, because if someone had access to the database, it would make cracking the passwords much easier.