6
$\begingroup$

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?

$\endgroup$
9
  • 2
    $\begingroup$ 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). $\endgroup$
    – Reid
    Feb 3, 2014 at 17:37
  • $\begingroup$ @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). $\endgroup$ Feb 3, 2014 at 17:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Reid
    Feb 3, 2014 at 17:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – user4982
    Feb 3, 2014 at 17:57
  • 4
    $\begingroup$ There are better answers to this question at security.stackexchange.com/q/3170/971 and security.stackexchange.com/q/36893/971 and security.stackexchange.com/q/53481/971. $\endgroup$
    – D.W.
    Mar 21, 2014 at 7:07

5 Answers 5

5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I imagine that the cPanel question might have involved a setup using reversible encryption. $\endgroup$ Feb 3, 2014 at 19:10
  • $\begingroup$ 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). $\endgroup$ Feb 3, 2014 at 19:12
  • $\begingroup$ @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. $\endgroup$
    – tylerl
    Feb 3, 2014 at 20:27
  • $\begingroup$ Ahhh; I thought you might be referring to functions used for "locality sensitive hashing". $\endgroup$ Feb 3, 2014 at 20:46
  • $\begingroup$ @KennyEvitt oh, no. Those aren't used right now in the real world. At least, not for storing passwords. $\endgroup$
    – tylerl
    Feb 3, 2014 at 22:02
3
$\begingroup$

Your suggestion to split the password, in extreme case into characters, and hash the small chunks is similar to concept of fuzzy hashing.

It is, however, not true that this allows an attacker to trivially reconstruct the password. Salt and Pepper may prevent dictionary attacks.

But you could also save the password as usual, and then if the user types in her password you could calculate variants of it, say of edit distance two, calculate hashes and compare.

Actually, 'heise online', a german computer site implements (or at least tested) this scheme. They granted access if you misspelled your password, but not too badly. You can test this here (in german).

$\endgroup$
1
  • $\begingroup$ I was assuming that an attacker would have access to any salt used to hash passwords. If they didn't, they would certainly be at a much more extreme disadvantage. $\endgroup$ Feb 3, 2014 at 19:04
3
$\begingroup$

When you change your password you are required enter your both old password and new password in clear text, so they can be compared against each other for similarities. Once this test passes, you encrypt the old password and check it against its stored hash etc.

$\endgroup$
5
  • 1
    $\begingroup$ Of course this only works for the immediately prior password and not for comparing with older passwords. $\endgroup$ Jul 3, 2015 at 9:59
  • $\begingroup$ Yes, indeed, but the older passwords would have gone through the same comparison against their previous password when they were changed. $\endgroup$
    – Rudie
    Jul 3, 2015 at 10:02
  • 1
    $\begingroup$ But it doesn't prevent somebody from alternating between two dissimilar passwords. $\endgroup$ Jul 3, 2015 at 10:05
  • $\begingroup$ To prevent alternating between passwords you store the last 12 hashed passwords and compare the hash of the new password to these. $\endgroup$
    – Rudie
    Jul 3, 2015 at 16:37
  • $\begingroup$ This only works for passwords that match exactly, not those that are similar. $\endgroup$ Jul 3, 2015 at 21:44
1
$\begingroup$

Because this pops up in google searches and people freak out when they see similarity comparisons anywhere, I want to provide additional information of how this can actually be done in a secure way, even if it does not cover 100% of all cases.

As several have mentioned here already, the similarity check between the new and last/current password is trivial, as users have to authenticate themselves and also provide a new password, so both passwords are available during the changing process and can easily be compared.

The similarity check with older passwords can be done using fuzzy hashing techniques, it does not really matter which one exactly. Those "fuzzy hashes" can be stored for the old passwords only - so for the passwords the user is not allowed to set again anyway! This is done when a new password is set successfully, using the old password the user had to provide for authentication (as mentioned above). So even if we assume that those "fuzzy hashes" are less secure then "regular hashes", they only lead to an old, no longer valid password.

haveibeenpwned.com provides passwords as SHA-1 hashes. We know this is not secure. But they do so because of course those passwords shall never be used by anyone ever again. So it does not really matter.

This only works for regular password changes, not when users forget their password. This case needs a different recovery process in which the similarity can not be checked.

But in the majority of the cases, people do know their password and need to provide it for the authentication anyway. So this can be better than not being able to check at all.

$\endgroup$
1
  • $\begingroup$ When users forget their password, old passwords may be recovered from public-key encryption ciphertexts, using keys stored in HSM that're only accessed when 2nd factors are applied. $\endgroup$
    – DannyNiu
    Jan 31 at 7:22
0
$\begingroup$

Let's say your rule disallows "only one character changed, or one character added or deleted, or two characters exchanged".

Then given a password, you can calculate all passwords that would be disallowed, and their hashes. For example if you have n = 16 password characters with 256 possible values, there are 16 x 255 "only one character changed", 16 x "one character deleted", 256 x 17 "one character added" and 16 x 15 / 2 "two characters swapped". Then you find hashcodes for every disallowed character. and look their distribution. Then you take all hashcodes for all but one of the next symphony.

$\endgroup$

Your Answer

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

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