Can a “pattern” in a series of passwords be detected from their hashes (and maybe a single raw password)?

Question

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!&D4grz
Week 2: 645h9yEQ8k37t!VW53d7g6263!&D4grz
Week 3: 745h9yEQ8k37t!VW53d7g6263!&D4grz
Week 4: 845h9yEQ8k37t!VW53d7g6263!&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?

Answer 1

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 trough decryption or exhaustive lookup tables (for inputs under a certain length). So 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.

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 can all be used for that.

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.

If you suppose that one of your plaintext passwords is known, 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. Almost all attacks on 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 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.

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, a known algorith and salt values, and just one other hash result, your example pattern could be detected in just 32 attempts - increment a character - compute the hash - not a match? next character If you complicate the pattern, the amount of attempts required increasing. 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. But for most attacks (e.g. drain your bank account, hijack your facebook) only one successful match. This is essentially defining a search space for the number of permutations. So assuming a plaintext is known, and they predict that only one character has change, 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 less than the 2^20 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.

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.

Answer 2

Summary: If it matters, you have bigger problems to deal with.

---

The first question is approximately How resistant is the hash to differential cryptanalysis?

Hashes are primarily designed to be collision/preimage-resistant, but it is often assumed that the hashes also behave as pseudorandom functions (e.g. the proof-of-security of HMAC relies on this).

The most relevant paper I am aware of is On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1 which discusses "distinguishers" of hash functions (i.e. an algorithm that can distinguish the output of a hash function from random). It turns out that MD{4,5} and SHA-{0,1} are not quite pseudorandom functions; the best attack they give figures for is the one on MD4 (used in the NTLM hash). If my interpretation is correct (most of the paper goes over my head), it is applicable to around one in 2⁻⁵⁶ passwords — not quite negligible, but pretty small.

However, the only thing the attacker learns is "the first few bits of the password change". Recovering a password from the hash means finding a short "first preimage". The best first preimage attack I'm aware of is in MD4 is Not One-Way, takes 2¹⁰² work, and produces preimages of about 1 KB in size. This might be a working password, but is unlikely to be your password.

However, if your passwords are being hashed with MD4, you have bigger problems to worry about: MD4 is not salted or iterated.

All good password hashes are salted and iterated. Salting with a reasonable amount of entropy (at least 64 bits, ideally closer to 128 bits) should be sufficient to foil differential attacks. Iterating will "spread out" the differences over the output bits. Additionally, both crypt_md5() and PBKDF2 use the password in subsequent iterations, which strengthens the output somewhat.

---

If you assume that the attacker has "at least one cleartext password", the question is then Can I reuse the same password on different systems provided I change the prefix?

No.

If an attacker knows you have used "Password1" on http://evil.example.com/, the attacker can simply try logging in with "Password2" on http://bank.example.com/. The passwords do not need to be on the same system. The attacker does not need the hashes to mount this attack.

Yes, the attacker can find a pattern. But you have a bigger problem to deal with: The attacker has successfully logged in. The fact that the pattern was discovered is irrelevant.