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.

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?

share|improve this question
1  
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
1  
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
3  
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. –  D.W. Mar 21 at 7:07
show 4 more comments

2 Answers 2

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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. –  Kenny Evitt Feb 3 at 19:04
add comment

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.