5
$\begingroup$

The other day when changing my password on a Solaris 10 system I was surprised that Solaris was able to detect that I hadn't changed enough characters between the new and current passwords.

MINDIFF is the password security configuration parameter that specifies the minimum number of characters that need to be different between the current and new password when the password is being changed.

I'm pretty sure that Solaris is using one-way hashes to protect the secrecy of the plain-text password.

That got me thinking, how can Solaris (or any system) detect which characters have changed between passwords if it is using a one-way hash to validate passwords?

Improve this question
$\endgroup$
5
  • $\begingroup$ Hi @e-sushi, perhaps the wording of my question could be better. My question is trying to answer whether it is possible to tell the number of different characters changed between two passwords when only one-way hashing is being used. $\endgroup$
    – HeatfanJohn
    Jul 8, 2014 at 17:00
  • 2
    $\begingroup$ I reworded the title question to better reflect the cryptography related question that I'm trying to get answered. $\endgroup$
    – HeatfanJohn
    Jul 8, 2014 at 17:04
  • $\begingroup$ I was just writing a comment to say that How does Solaris implement… and MINDIFF… points to cryptographic software (which is off-topic here but on-topic at SuperUser), but not its cryptographic internals (which is on-topic)… and I wanted to ask you to edit your question to tune that a bit – but while I was writing my comment, your edit already popped up. So, you’re definitely quicker than me. ;) Anyway, much better now. Retracted my close-vote accordingly. (Thanks for your edit.) $\endgroup$
    – e-sushi
    Jul 8, 2014 at 17:06
  • $\begingroup$ Short answer: Nope. $\endgroup$
    – Andrew Hoffman
    Jul 8, 2014 at 18:01
  • $\begingroup$ If this were possible (say, if the hash function had the mathematical property that H(a) - H(b) == a - b) it would be considered a catastrophic design flaw in the hash function. Consider how much easier an offline attack would be if the attacker could know how many characters of a given hashed password were different from some word in their dictionary. $\endgroup$
    – zwol
    Jul 8, 2014 at 20:32

2 Answers 2

Reset to default
9
$\begingroup$

When only using one-way hashing, is it possible to tell the number of characters changed between the old and new password?

No. If the hash function is strong, even a single bit change will give a completely different hash.

The only way to tell how many characters differ between a particular unknown hash value and a known password would be an exhaustive search, which might be possible for determining e.g. that more than one character must differ, but not in general.

That got me thinking, how can Solaris (or any system) detect which characters have changed between passwords if it is using a one-way hash to validate passwords?

Most likely answer: it asks for both your old password and the new when changing passwords, and can compare them at will.

Alternatively: it stores something other than just a hash (e.g. an encrypted password) that does allow comparisons. You should suspect this if a system has rules that concern more than one previous password. That is not a secure way to store passwords.

Improve this answer
$\endgroup$
4
  • $\begingroup$ duh on my part, yes you are correct, the OS did just previously ask for the current password. It must temporarily persist the current password in memory before requesting the new password and then performs the difference checks using plain-text. $\endgroup$
    – HeatfanJohn
    Jul 8, 2014 at 19:03
  • 1
    $\begingroup$ If such fingerprint can be obtained, a password can be found within seconds:) $\endgroup$
    – Dmitry Khovratovich
    Jul 8, 2014 at 19:11
  • 1
    $\begingroup$ This property of hashes' is called the "Avalanche effect": en.wikipedia.org/wiki/Avalanche_effect $\endgroup$
    – Matthew
    Jul 8, 2014 at 19:26
  • $\begingroup$ @DmitryKhovratovich, exactly so, which is why such games are definitely not the best practice when storing passwords. Yet companies still store passwords plaintext or merely encrypted. $\endgroup$
    – otus
    Jul 8, 2014 at 19:28
3
$\begingroup$

I'm pretty sure that they store only the hash.

They can detect that you didn't change enough characters in the following way:

When you provide a new password, the system generates several passwords that similar to the new password, by changing some characters. Then it calculates the hash of each similar password and compares it to the last stored hash (or last N stored hashes).

If it finds identical hashes, it means that the new password is similar to the previous password.

See also: Does Facebook store plain-text passwords?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Interesting that FB actually uses this. They can probably only detect passwords that are within one, maybe two characters of the previous, since the complexity is something like $c^n \cdot (l \operatorname{choose} n)$. $\endgroup$
    – otus
    Jul 10, 2014 at 8:31
  • $\begingroup$ Ah, a comment there suggests they only check two cases 1) full case inversion "pass" <-> "PASS", 2) first letter case inversion "bob2014" <-> "Bob2014". $\endgroup$
    – otus
    Jul 10, 2014 at 8:40
  • $\begingroup$ it is the same complexity as checking the passwords themselves. it just adds the factor of hash calculation. $\endgroup$
    – moti
    Jul 13, 2014 at 6:34
  • $\begingroup$ Checking a constant number of alternatives (like they seem to do) only adds a constant factor, but even that shouldn't be a trivial cost with strong password hashing. In the general case calculating the edit distance is polynomial time for known strings, but exponential against an unknown hash. $\endgroup$
    – otus
    Jul 14, 2014 at 9:12
  • $\begingroup$ @otus It's probably not a trivial cost, but, even at Facebook's scale, hashing order of 20 variations on a new password could easily be an acceptable cost for the process of changing an existing password. That happens orders of magnitude less often than the regular login sequence. For Facebook, it might be orders of magnitude less often than new account creations, even. $\endgroup$
    – zwol
    Oct 17, 2019 at 18:17

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.