How to implement a safe password history

Question

Passwords shouldn't be stored in plain text for obvious security reasons: you have to store hashes, and you should also generate the hash carefully to avoid rainbow table attacks.

However, usually you have the requirement to store the last n passwords and to enforce minimal complexity and minimal change between the different passwords (to prevent the user from using a sequence like Password_1, Password_2, ..., Password_n). This would be trivial with plain text passwords, but how can you do that by storing only hashes?

In other words: how it is possible to implement a safe password history mechanism?

Answer 1

When the user changes their password, require them to enter their previous password. You now have access to two plain text passwords, even though you are not storing plain text passwords in your database.

Perform whatever verifications you want on these two passwords. This won't prevent the user from alternating between two passwords (with a suffix - you can prevent direct alternation per the suggestions in other answers), but it will prevent the more blatant cases.

Answer 2

Store the hashes and verify an entered password against those stored hashes, the same way you verify a password when logging in. You would have to generate 'alternative' passwords from the one given based on numerical patterns to detect your 'minimal' changes.

On login, you verify the entered password against a hash already, there is no need to store the password in plaintext. The same trick works when it comes to changing a password, simply check the entered and 'minimal change' generated passwords against the historical hashes. If the new password is satisfactory, move the current password hash over to the historical set, and replace it with a new hash for the new password.

Answer 3

to add onto @martijnPieter's answer the minimal change can be implemented by doing a short brute force based on the new and previous passwords (which you both have available)

for example you can iterate over all passwords with a hamming distance of 1 or 2 from the new password and see if it matches an old pass

but you might want to note that this can reduce the confidence of users that you are hashing passwords (as you are essentially saying you can get a previous password back to reject a new password)

Answer 4

This is really more of an addendum to @Brian's clever answer. Hats off also to @Martijn Pieters for adding details about how to brute force the old passwords based on the current one and to @ratchet freak for "hamming distance." I'm not deleting my answer because I think it provides interesting background to back them up.

State of the art password storage requires using multiple rounds of a strong one-way cryptographic hash (SHA-512+) with unique salt (128-bits+) for each user. But do not be tempted to store additional information about each password. The more information you will store about each password, the more you undermine the security of your hashing algorithm.

Example

Consider how easy it becomes to brute-force a password if you know that:

• It's 7 characters long
• Characters 3-5 are upper-case (4 is lower)
• 1 and 7 are numbers
• 6 is a symbol

A US keyboard has 95 printable characters, so knowing that the password is 7 characters long yields 95^7 = 69,833,729,610,000 = 7x10^13 permutations. If it were truly random, it might take a year to crack this on a single 3Ghz processor. But:

• There are only 26 upper-case and 26 lower-case characters
• There are only 10 digits yielding 100 possiblities for those two numbers
• There are only 32 symbols

So (corrected thanks to @Hellion):

         26^4 (charcters 2-5 are known upper or lower-case)
        x 100 (characters 1 & 7 are digits)
        x  32 (character 6 is a symbol)
         ====
1,462,323,200 possible passwords.

That's 50,000 times easier to crack! Storing good information to prevent similar passwords in this case has taken your crack time for a 7-character password from a year down to a couple hours. Decoding all your passwords with on a powerful multi-processor desktop with a good video card and a little patience is now very feasible. I hope this simple example demonstrates that the more meaningfully you can compare similar passwords, the less secure your hashing will be.

Importance of Strong Hashing

Databases with passwords are stolen regularly, with gargantuan break-ins in the news every month. Heck, just last month the state of SC lost everyone's social security numbers - oops! How many more of these breaches are covered up?

Closing Thought

The most frightening thing for me is when people choose the same or similar password for multiple sites so that breaking into one gives the attacker access to them all. I'd love to see a proven method of preventing that situation, though I think preventing the most common bad passwords would help more than preventing an individual user from reusing their bad password within the same site. The best I can suggest is a company-wide policy to use a secure password manager that generates highly random passwords for each of your users and stores them securely.

Answer 5

First, you could store the hashes for the last "n" previous passwords, so you can check if their new password duplicates a previous password. You also have the plain text of their current password (because they have logged in or provided it to you to authenticate their password change request), and their new password, so you can check for minimal changes between these two passwords.

If (for you) it is very important to directly compare these two passwords against "n" previous passwords, then you have to store these passwords (encrypted) to be able to retrieve them later.

While it could be seen as a security flaw to do this, encryption methods could be implemented to provide sufficient security.

1. Store each password (encrypted), for the last "n" passwords.
2. Store the date and time that the most recent password was created.
3. Store the hash of the most recent password.
4. Encrypt all the passwords using the hash (salted) of the current password, and the password creation timestamp, and perhaps something like an account number or email address.
5. Un-encrypt and re-encrypt all the passwords each time a new password is created.

Then, anytime the password is changed, you can un-encrypt all the old passwords, and do all your minimal-change tests.

Now, if someone had this person's password, and knew all the other necessary details they could un-encrypt this information for this one person. But if they already have this person's password, they can already login as this person and access this person's account.

Also, for the old passwords, they may not have to be stored in strictly plain text. They could be stored in some obfuscated way. Or stored as an alphabetical list of the characters in the password.

I'm not saying this is a recommended thing to do in the general case, but assuming the task you have described is required in your case, then this is one way to accomplish it with some security measures.