Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  HeatfanJohn Jul 8 at 17:00
2  
I reworded the title question to better reflect the cryptography related question that I'm trying to get answered. –  HeatfanJohn Jul 8 at 17:04
    
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.) –  e-sushi Jul 8 at 17:06
    
Short answer: Nope. –  Andrew Hoffman Jul 8 at 18:01
    
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. –  Zack Jul 8 at 20:32

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
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. –  HeatfanJohn Jul 8 at 19:03
1  
If such fingerprint can be obtained, a password can be found within seconds:) –  Dmitry Khovratovich Jul 8 at 19:11
1  
This property of hashes' is called the "Avalanche effect": en.wikipedia.org/wiki/Avalanche_effect –  Matthew Jul 8 at 19:26
    
@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. –  otus Jul 8 at 19:28

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?

share|improve this answer
    
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)$. –  otus Jul 10 at 8:31
    
Ah, a comment there suggests they only check two cases 1) full case inversion "pass" <-> "PASS", 2) first letter case inversion "bob2014" <-> "Bob2014". –  otus Jul 10 at 8:40
    
it is the same complexity as checking the passwords themselves. it just adds the factor of hash calculation. –  moti Jul 13 at 6:34
    
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. –  otus Jul 14 at 9:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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