# Can passwords be stored securely so that a similarity comparison can be made?

On the Pro Webmasters StackExchange site, someone asked a question about a webapp (in this case cPanel) that refused to allow a password change because it was too similar to a previous password. I suggested that the app might be storing hashes of portions of the password.

I was going to ask whether, assuming that an app is storing hashes of portions of a password (i.e. substrings of the full password string), would doing so be less secure than just storing a single hash, but after typing out the question, I realize that it definitely would be less secure. In the most extreme case, i.e. storing a 'hash' of ever character in the full password string, an attacker could trivially recover the original password.

Is there a way to store a password securely that still allows similarity comparisons to be made?

-
Well: if the password change form asks for your previous password, it can use it to check similarity between the new password and the old (after checking it against the stored digest in the DB for security, of course). –  Reid Feb 3 at 17:37
@Reid – sure, that's one way, i.e. not store password history but rely on the user to provide it (in the form of the previous password). –  Kenny Evitt Feb 3 at 17:42
That's essentially the only (secure) way, as far as I can see. Suppose you had some password storage algorithm that allowed you to compute a "similarity metric" between two digests (or one digest and one input; the scenario doesn't change). Then couldn't one use the similarity metric to optimize a brute-force search? (That is: follow a path that maximizes the similarity metric.) This isn't a proof, but it does intuitively explain the problem here. –  Reid Feb 3 at 17:55
Remembering the password entered when session started and/or requesting the old password as a part of password change is the obvious way, and easy to implement and secure. Theoretically, it would be possible to try to use new password + one/two character change to try to brute-force old password, but this is very expensive way, especially if proper password hash was used. –  user4982 Feb 3 at 17:57
One answer would be that the entered passwords are always passed through a function $f$ such that $f(PW_0) = f(PW_1)$ iff the passwords are "similar". One trivial example would be converting all entered passwords to all lower case before further processing. –  Henrick Hellström Feb 3 at 17:58

Storing passwords in such a way as to allow comparison against portions of the hashed password is by definition less secure than traditional cryptographic hashing. As a rule, this is simply never done.

On the other hand, you could safely make comparisons of portions of your new password (for which you necessarily have the plain text) against the entirety of an old hash, and such comparisons are done today by some existing software.

To address your original point, to the best of my knowledge, cPanel does not do what you suggest. It has the option of storing certain kinds of passwords reversably encrypted for use with digest authentication, but this is not the default. All other password storage is done through the underlying product's default hashing mechanism (be it MySQL's hashing, shadow file, etc).

The discussion may have confused cPanel with Plesk, which until very recently stored all passwords in plain text in a MySQL database. Yes, really.

-
I imagine that the cPanel question might have involved a setup using reversible encryption. –  Kenny Evitt Feb 3 at 19:10
With what hash functions could a comparison between portions of a plaint-text password be made to hashes of other passwords? I wouldn't think any such functions would be secure, or at least as secure, if any kind of similarity comparison could be made (beyond strict equality). –  Kenny Evitt Feb 3 at 19:12
@KennyEvitt all of them. You hash the portion of the password you want to compare, and then see if the generated hash of the password portion matches the saved hash. Strict equality is the only thing you can test. Attributes like "is this a noun" clearly are not an option. –  tylerl Feb 3 at 20:27
Ahhh; I thought you might be referring to functions used for "locality sensitive hashing". –  Kenny Evitt Feb 3 at 20:46
@KennyEvitt oh, no. Those aren't used right now in the real world. At least, not for storing passwords. –  tylerl Feb 3 at 22:02