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 confirmation of new 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.
• And this answers your second question: security.stackexchange.com/questions/4024/… You can already find a lot about password storage and policies using the search function. :) – Arminius Apr 22 '17 at 4:10
• @Arminius, it's not a duplicate of that one. This is a very specific scenario, and there's obviously no "Enter your current password" in a password reset feature. Thanks for the second link though! That's definitely helped me think about it. – Obversity Apr 22 '17 at 4:22

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.

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.

• Homomorphic encryption is such an interesting field, with fairly broad application in health care and financial industries. It is an interesting concept to use it when trying to determine if the characters in the password are already used, without revealing the full password. – Nik Roby Apr 22 '17 at 17:05
• Very interesting. It's good to know that it's at least theoretically possible. But yes, I agree that it's very unlikely they're using anything like this. Side note: does anyone know what the protocol on this kind of thing is? Should it be reported to someone so that it can be investigated, given that it's an official service with lots of potentially very exploitable / sensitive data? – Obversity Apr 24 '17 at 5:06
• I don't see how private set intersection is applicable, since no party has the old password in plain. And the bloom filter sounds almost as bad as storing the password as plaintext. – CodesInChaos Apr 26 '17 at 8:12
• Good point, @CodesInChaos. But I think that some of the technologies involved would enable something that would allow for the password to not be stored as plain text. You are also correct that for small data sets (as substrings of four characters of a password would be) that a Bloom filter doesn't have the security property we need. A small number of queries to it, could narrow down the password dramatically. But I wanted to point out that in principle things like this don't need plaintext. – Jeffrey Goldberg Apr 27 '17 at 5:02

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.
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.

• Yup, there was no email/sms confirmation or anything. You literally just input your username and it takes you to a page with these fields. I don't want to get too specific on which site, because I can see this being exploited, but I suppose I can tell you that it was American! – Obversity Apr 22 '17 at 4:09
• to be fair, "first pet" is less likely to be public info, unless you're very young... – dandavis Apr 22 '17 at 16:53

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.