Can a "pattern" in a series of passwords be detected from their hashes (and maybe a single raw password)? Let's say I'm a lazy user of a system with annoyingly frequent password change policies. I may have a "good" password I used initially that is only used for this system but since I have to change it every week I'm just going to increment or decrement a number. E.g.

Week 1: 545h9yEQ8k37t!VW53d7g6263!&amp;D4grz
Week 2: 645h9yEQ8k37t!VW53d7g6263!&amp;D4grz
Week 3: 745h9yEQ8k37t!VW53d7g6263!&amp;D4grz
Week 4: 845h9yEQ8k37t!VW53d7g6263!&amp;D4grz
...


And so forth...

Suppose a hacker obtains the hashed password history (i.e. the hash of each password). Are there any statistical approaches they could use to detect the (very simple) pattern being used?

I would assume the hashing algorithm used will have a lot to do with it, as well as other factors like the use of a salt, possibly the length of the password and if maybe the attacker also has access to at least one cleartext password. So I guess another way to phrase the question would be: In what sort of circumstances would an attacker potentially be able to detect a pattern from a series of hashed passwords?
In what sort of circumstances would an attacker potentially be able to detect a pattern from a series of hashed passwords?


I think the most direct answer is: When the hashing algorithm is not cryptographically secure. The main four points of cryptographic hash function evaluation are as follows (quoting wikipedia):


it is easy to compute the hash value for any given message
it is infeasible to generate a message that has a given hash
it is infeasible to modify a message without changing the hash
it is infeasible to find two different messages with the same hash


As Gumbo pointed out, strong hash functions result in wide variation of output for narrow variations of input. This is true for nearly every hash function ever considered secure, even the now discredited MD5 and Sha-1 algorithms. With most hash algorithms, the main attack vector is a collision and a close second is a decryption. I expect in my lifetime that MD5 and Sha-1 will be broken, either through a thorough decryption effort or exhaustive lookup tables (for inputs under a certain length). Pattern detection in hashes may receive some further analysis. I expect that the capability to detect the presence of a pattern will arise, but the ability to definitively state what the pattern is will hinge on the ability to retrieve the plain text.

Consider the hash values of your provided example passwords:

Password                            Hash
545h9yEQ8k37t!VW53d7g6263!&amp;D4grz    466f4dff9339bd8837a8fa960f41fc44
645h9yEQ8k37t!VW53d7g6263!&amp;D4grz    16731f2026d9d600e7dbf66b46db7dde


I only see 5 characters that match up between the two hashes. If you took the comparison down to the bit level, maybe half of the remaining bits are equal. This is a reasonably high degree of difference between the output, considering the similarity of the inputs.

In other words, this is likely:


  We can say with 90% confidence that the plaintext of these hashes are a maximum of x-degree difference from each other.


This is extremely unlikely:


  Clearly, the user is following a pattern of incrementing the highest bits of their password every week.


Especially considering that all of the attacks on hash functions are actually interested in this:


  Oh, the hash is x? y, z, a, b and c plaintexts all map to that hash for this algorithm.


This is the rainbow table approach to password cracking, and it is very common. Most large security breaches that make headlines come from the store of passwords being leaked (most commonly through a web-based SQL injection attack).

Since you phrase it from the perspective of a hacker obtaining hashes of your password, let me put it to you another way. How much do you trust the security of the entity storing your hashes? Supposing that said entity is storing your previous hashes (which given the requirement to change it every week, I also find it likely that they will enforce a difference or minimum degree of difference which pretty much requires them to store a history), if they are breached such that the complete list of your previous password hashes are taken, it's not that much more unlikely the attacker can compromise the systems in an ongoing way and simply start recording password plaintexts as they come in.

There is a particular situation where you may be at risk in the way you imagine. If you are ever told that your new password is too similar to a previous password, then the authority almost certainly storing a list of information about your previous passwords which is less cryptographically secure. If this list is taken along with the hashes, then you're much more likely in danger of your pattern being found out. Read up on string metrics if you're interested in this - most of those metrics (as solutions for enforce password differences) would certainly require your password to be stored in plaintext.

Update: The previous two paragraphs are not necessarily true. It is possible to calculate similarity between old and new passwords, if the change password procedure requires you to provide the old password(s). See this security question for details.

If you suppose that one of your plaintext passwords is known by an attacker (through some other attack vector), that does change the problem by quite a lot. I feel I should emphasize again, however, that this would be really a very outlandish attack on your password - if an attacker can gain one plaintext password, it is almost certainly easier for them to repeat that attack than to use some type of extrapolation for your other passwords. Furthermore, if one of your plain text passwords is known, you had darn well better change your pattern for generating new passwords, preferably starting with new, distinct high-entropy starting point.

Almost all attacks on cryptographic hash algorithms remain theoretical. If there were to be a sudden break through in a pattern/similarity attack on hashes, it would certainly make headlines (in certain circles). If we really are talking about an attack target that justifies major research efforts here, and we suppose that a number of your password hashes are known and a plaintext version from your history is also known, the attacker would probably also need to know what hash algorithm is being used and what salts are used for the given passwords. These are things that may be difficult to discover, but do not provide any additional robustness to your security: once they are known, and an attack is feasible, you need to redo your entire security apparatus.

But, if a plaintext is known, it's far easier attack, in my opinion, to simply compute variations on the plaintext yourself. Given a plaintext password, a known algorithm and salt values, and just one other hash result, your example pattern could be detected in just n attempts (where n is the length of the password, multiplied by some small, constant factor). Such a cracking attempt would follow this procedure:


increment a character
compute the hash
not a match? next character


If you complicate the pattern, the amount of attempts required increases. For example, you have a pattern for choosing which character you increment each time, then for the attack to predict your next password, they must have at least as many hashes for the length of your pattern to repeat. This is essentially defining a search space for the number of permutations. So if the attacker accurately predicts that only one character changes by one bit in each new password, then only n * m possibilities exist. So for your example passwords with 32 character length (n) and call it a-zA-Z0-9!-+ 72 possible values, that's only 32 * 72 = 2304 possibilities to search, far, far less than the 220 possibilities in the theoretical lower bound of MD5 algorithm security.

Changing a second character to an arbitrary value (not an incremental value), squares the search space, which gets you back into the range of cryptographic security (2304^2 ~ 2^22). But if they have a history and know you're only changing one character at a time, then it's only 2304 searches for each step in the history (multiplicative, i.e. linear growth of the search space instead of exponential).

Hope that helps, even if I didn't provide the actual complexity of pattern detection in hash values (because such an attack does not yet exist for any cryptographic hash function).

Edit: I should probably provide a disclaimer. I am not a crypto expert, just a hobbyist/novice applying reasoning and analysis from what little I know.