Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Jul 21 '12 at 23:12

This question came from our site for professional and enthusiast programmers.

    
If you could tell that two hashes had a relationship, then you could possibly start from a unknown hash and work your way to a known hash to determine what the unknown hash is. –  arxanas Jul 20 '12 at 17:25
1  
As you already said, it depends on multiple factors, mainly on the used hash function. If it’s a (strong) cryptographic hash function, any single bit flip should affect more or less half of the bits of the hash value. –  Gumbo Jul 20 '12 at 17:39
add comment

2 Answers 2

up vote 6 down vote accepted

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!&D4grz    466f4dff9339bd8837a8fa960f41fc44
645h9yEQ8k37t!VW53d7g6263!&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.

share|improve this answer
add comment

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−56 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 2102 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.