Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
2  
Related: security.stackexchange.com/questions/4704/… (and BTW that site might be a better location for this question). As far as 'minimal change', I can't think of any alternative to generating all the options which would qualify as 'minimal change' (Which could be a LOT depending on your definition!) and comparing the hashes. What is the definition of 'minimal change'? –  Kevin Vermeer Nov 27 '12 at 15:25
6  
Storing the latest n passwords only means that the user will choose a sequence that runs from 1 to n+1. –  Joachim Sauer Nov 27 '12 at 15:38
11  
I'm very skeptical that such a password policy improves security; IMHO, it increases the chances that people will resort to keeping their password on a sticky note. Kevin's link is a good discussion. @KevinVermeer - you actually can measure the amount of change as Levenshtein distance (en.wikipedia.org/wiki/Levenshtein_distance), also known as "edit distance". –  Nathan Long Nov 27 '12 at 17:03
5  
If your security is this strict, then you might as well generate a random password for the user, force them to use it, and changing it on a regular interval. That way you have total control over their password. –  Mathew Foscarini Nov 27 '12 at 17:59
2  
@nathan: Storing passwords on a sticky note is actually secure. It is not possible to attack the password unless you have physical access to the sticky note - eliminating about 99% of threats. Put that note inside a wallet or purse, and you basically need to mug the person to get it - meaning a security breach is identified and can be mitigated. –  mattnz Nov 27 '12 at 20:34

5 Answers 5

up vote 22 down vote accepted

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.

share|improve this answer
    
So, if the user enters Password6 I should detect the numerical part, and try for example Password4, Password5, Password7, and so on. Is that correct? –  Lorenzo Nov 27 '12 at 15:47
4  
@Lorenzo: Correct. Generating alternatives can be as complex as you want it, just make sure you find the right tradeoff between complexity and risk (don't let your users wait 5 minutes while you check all possibilities with vanishing likelyhood of being a risk). –  Martijn Pieters Nov 27 '12 at 15:49
    
I'm not sure suggesting incrimenting the number on the end is a good suggestion to make to users -- that is just a little bit predictable. And gets exponentially more so if you are telling users to do so. –  Wyatt Barnett Nov 27 '12 at 16:01
2  
@WyattBarnett: Noone is telling the users to do so. The point is to detect users doing so and preventing the 'incremented' password from being used. –  Martijn Pieters Nov 27 '12 at 16:11
    
Ah, completely misread something here. Sorry. –  Wyatt Barnett Nov 27 '12 at 16:28

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.

share|improve this answer
    
Well this is certainly a clever workaround if you don't have a requirement of testing against n previous passwords, however the suggestion of generating the alternatives just in time is better. But generating alternatives of both passwords is even better! –  Lorenzo Nov 27 '12 at 16:03
2  
@Lorenzo: The idea is that you do a direct test against the n previous passwords and a stronger test against the last password. It's a compromise. –  Brian Nov 27 '12 at 16:06
    
Yes. If their current password is potatoSalad1 and they want to update to potatoSalad2, you tell the change is too small because you have both plain text passwords at that moment. But further back than that, you have only hashes, and the nature of hashes is that you can't tell whether two hashes had similar or completely different plain text as input. –  Nathan Long Nov 27 '12 at 16:56

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)

share|improve this answer
    
But there are many sequences with larger Hamming distances such as February2012 -> March2012 or Fri-09-28-12 -> Tue-11-27-12 (dates), Password_Alpha -> Password_Beta, Pass_1111 -> Pass_2222, Pass_qwer, Pass_tyui, Pass,_op[], or Eleven -> Twelve (alternate counting systems), or FrankSmith -> FredJones -> FriarTuck or anger -> animal -> apple (names in a company directory or words in a dictionary) that an attacker with the previous password(s) could easily guess but that your algorithm would have an extremely hard time of generating. –  Kevin Vermeer Nov 27 '12 at 16:00
    
@KevinVermeer then account for those in you variation generator, and accept that you will never get everything –  ratchet freak Nov 27 '12 at 16:07
    
+1 to reducing confidence. When I see something telling me that my password is too much like the one I used three months ago, I instantly wonder if they are storing them reversibly ... or if they have an awesome programmer. Skepticism usually wins. –  Tim Post Nov 28 '12 at 1:58

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.

share|improve this answer
1  
minor nit: the password possibilities are still multiplicative, so it's (26^4) * 100 * 32 = 1,462,323,200. If we assume that cracking (95^7) possibilities takes a year, then cracking this smaller number of possibilities will take about 11 minutes. –  Hellion Nov 27 '12 at 22:01
    
@Hellion - Oops! Thanks for pointing that out. I've corrected it. –  GlenPeterson Nov 28 '12 at 19:40

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.

share|improve this answer

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.