Checking password complexity: different from last X passwords

Most services, programs, etc. have various password complexity checks. Without delving into the efficacy of such checks, I thought of one that might be interesting, but also potentially problematic check:

"The new password must be Y characters different from the last X passwords."

This would prevent people from using passwords like Password1!, Password2!, and so on. But if that's done, one cannot hash the previously used password - they would be at best encrypted... Right?

For a small Y and a fairly short password, you could probably sti开发者_JAVA百科ll store the hash and bruteforce all Y letter variations of the new password, but this gets unfeasible as Y and the password length grows.

My original idea is this: since when you change the password you must provide your original password, hash the new password and store and the old one in encrypted form. Now it's reversible.

So assuming an active password is always hashed, is there a better way to do this? And also does having this in place increase or decrease the security of the application?

I tried to put this in a comment, but I think this is important enough to put in an answer.

The scheme proposed by OP is not necessarily a violation of CWE-257. The proposal does not allow a system administrator (say) to recover the old passwords.

The proposal is to use the new password as the encryption key for all of the old passwords. If you can live with the "new password verification" living on the client and not the server, then this is no less secure than encrypting anything else using the password.

So the "change password" gadget would be client-side code. The server would send the encrypted list of N earlier passwords, which the client could decrypt with the user's current password and then re-encrypt with the user's new password. At no time does the server have enough information to determine any of the passwords, whether old or new. Only the client has this information, but it has that in any case... The difference being that an attacker who learned your current password could also learn your old passwords. Since learning your current password is already a disaster, this does not strike me as all that much worse.

True, this does not guard against the "attack" of an employee writing their own password change utility to get around the password restrictions, since the validation is not done on the server side. But in no way is this a violation of CWE-257, in my opinion.

It is actually a reasonably clever idea.

The Oracle requirement you reference says that password n must differ sufficiently from password n-1, not that password n must differ from all previous passwords. Usually to change a password you make the user enter the current password as part of that. So you have everything you need to implement the requirement, and you don't need to store passwords in a reversable fashion (encryption, brute forcing, whatever).

I understand that this doesn't directly address the requirement as originally posed (differ from last X passwords), but my feeling is that it's a bogus requirement. Your requirement would require reversable passwords (the mechanism doesn't matter) and most experts will agree that that's incorrect. I believe you've simply misinterpreted the Oracle requirement, if that's indeed what's driving the question.

EDIT:

OK, I just thought of a way to implement what you're asking for without reversable passwords. I still think you're misinterpreting the Oracle requirement, and I wouldn't actually do what I'm about to describe myself, but it will meet the requirement without reversable passwords.

1. Pick a reserved character that's not allowed to appear in a real password. For the sake of discussion, suppose it's a backslash.
2. Enumerate all possible ways of substituting at most Y backslashes into the password, hashing the result each time.
3. Maintain only the most recent X sets of hashes thus generated.
4. When the user picks a new password, repeat the procedure on the tendered password and compare its individual hashes against the individual recent hashes.

Goofy, but that should meet the requirement.

Encrypting passwords is a clear violation of CWE-257 and there for should never be done. However in the case of an expired password, the user has just logged in, there for keep the plain text of this password. Then force the user to change the password and calcualte the hamming distance between the two. Once the user provides a password that is different enough, hash this new password and throw away the plain text.

EDIT: You could keep the salt+hash's of all of the old passwords to make sure the user doesn't pick a password he has in the past. But enforcing that the password is N letters different from all passwords weakens the system as a whole and is expensive as it would require o(n) comparisons.