34

Assume the following very basic hashing algorithm.

h(k) = k mod 17

Let's say we create a password 12345 for a website that uses this very basic hashing algorithm. That would yield the hash of 3.

Say a brute force attacker comes by and starts guessing numbers starting at 1 they would only have to get to 3 before they got a hash collision and obviously 3 is not the original password.

Is the problem that the password hashing space (0-16) is much smaller than the space of the allowed password, or is there something else I'm overlooking?

  • 1
    I've updated your title in an attempt to better reflect your question at the end. If you don't like my change you can revert it or just edit it again. – Conor Mancone Mar 12 at 21:13
  • 8
    As a note: Yes, the reason for collisions is that the hashing space is smaller than the input space. This is true for all hash algorithms, and is called the Pigeonhole_principle. – sleske Mar 13 at 9:45
49

Steffen's answer covers this perfectly, but I just wanted to add a few more details.

Anything that gives a match is usually fine

As he says, you generally don't care about finding the actual password, because many applications will be happy to authenticate you with any string that happens to hash to the hash value stored in the database. This is most often true for web applications, but may be less often the case in other contexts. This means that if you perform a brute force search and find something with the same hash, you can login to the account even if it isn't actually the same password. This, as implied in the question, is the nature of hashing and is a direct result of the pigeonhole principle.

Until you need the actual password

However, there may be some cases where you do want to find the original password. This would be the case if for instance a hacker stole a username/password from a valueless service and wanted to try to login as the user on a more valuable service (Facebook, banks, etc...). Since people often use the same password everywhere, then in this case you really do want the original password - not just something that hashes to the same value for a given hashing algorithm (after all, different services may use different hashing methods, and most also use cryptographic salts - h/t @Taemyr).

But the difference doesn't matter

Fortunately (for our attacker), this doesn't really matter. The reason is because an exhaustive brute force is effectively impossible. Instead a hacker will try things that are likely to be passwords (word lists, common passwords, etc...). As a counter example imagine that despite the impossibility of it you have a hash from a web service and manage to perform a brute force search on all possible 256 bit ASCII strings. You find three inputs that hash to the same value as the user's password hash:

  1. BD3EDF42F6D3AF2DAAE93313EB534
  2. 7AF7B8B8F84443872C48EC372DBD1
  3. password

Which would you guess is the actual password? The answer is clearly #3. I mean, there is technically a chance that the user just happened to pick an extremely strong password (i.e. BD3EDF42F6D3AF2DAAE93313EB534) that just happened to hash to the same value as password, but the odds of that are effectively zero.

In this sense the attacker has a nice advantage. They would prefer to find the actual password, and it turns out that because people are bad at picking random passwords, the best way to do that isn't by checking everything anyway - it's by checking things that look like passwords. This makes brute forcing searching much, much, much, much more effective, and also gives the attacker a much more useful result (the actual password, rather than some random string that happens to have the same hash).

| improve this answer | |
  • 6
    Even the other side using the same algorithm is insufficient. They have to use the same algorithm and have the same salt. – Taemyr Mar 13 at 9:26
  • 5
    @Taemyr: Exactly. As a matter of fact, that is the whole point of using a salt - to make sure that identical passwords do not result in the same hash, because that would be bad, as shown here. I edited to mention that. – sleske Mar 13 at 9:41
  • 11
    In some circumstances, having the hash only seems to help you. For example, zip encryption and MS Office documents encryption encrypt the password to a hash, check the hash when you're trying to decrypt, and if the hash matches, use the original password to do the actual decryption. There's zero chance of password decrypting your file correctly if your password was BD3EDF42F6D3AF2DAAE93313EB534, even if both have the same hash. – Guntram Blohm Mar 13 at 10:27
  • I disagree with the “an exhaustive brute force is effectively impossible”, while for the lay person maybe; but for something with the resources and time, it’s not. That’s what helps give supercomputer and botnet farms viability. In many ways it’s similar to how crytomining works. – vol7ron Mar 13 at 16:50
  • 1
    For my chosen example (a 256 bit string) it is in fact impossible to perform an exhaustive brute force search: en.m.wikipedia.org/wiki/Brute-force_attack#Theoretical_limits – Conor Mancone Mar 13 at 17:23
18

The main goal of brute forcing is not to get the original password but to get a password that works. Thus it does not matter much if the found password was not the original one as long as it works.

It is very likely though that with efficient and intelligent brute forcing based on a dictionary of common passwords and typical modifications the resulting password will actually be the real one. This is simply because most users don't use long random passwords but common passwords with typical modifications and thus the real passwords will be found first when doing intelligent brute forcing.

| improve this answer | |
2

Does it matter if a brute force search for a password returns a collision and not the password?

There are other answers addressing this question quite well, so I'll explore a different angle: It doesn't matter, because brute-force searches are unlikely to ever find a collision instead of the original password.

Assumptions:

  • The password is shorter than the maximum length by some number of characters.
  • The brute-force search tries every character, starting with the shortest possible password.
  • The implementation has a very low probability of collisions. This is true even for deprecated algorithms like MD5, but not for the algorithm you provided.
  • Collisions are uniformly distributed.

Let's say our password is "password", which has eight characters. The number of alphanumeric passwords between one and eight characters is around 2.219e+14.

Let's also say the maximum password length is ten. Between nine and ten characters, there are 8.528e+17 passwords, or about 3800 times as many as between one and eight. Even if we assume five collisions, the likelihood that all five are longer than our "password" is around 99.9%.

The number I've used for max password length is (hopefully) much smaller than what is typically used, and the number of collisions is greatly overestimated. In practice, finding a collision that is shorter than the actual password just doesn't happen.

| improve this answer | |
1

Any hashing algorithm that is used in practice should have a key space that is impossible to brute force. On the other hand, the set of actual passwords is much more limited, so attackers will not search all possible passwords, but only those that are used by real users.

Now if you have a good password, and an attacker does a brute force attack, it is not impossible that a different password would have the same hash. If the key space of the hash was only 64 bits, then among a few billion passwords you could expect that two have the same hash code. So it is not impossible that an attacker would find a different password with the same hash (after checking 2^64 passwords on average). Both would work for the attacker to get to the service. In reality, the hash algorithm should have a much larger key space and nobody will ever find a different password with the same hash.

Finding that alternative password lets you log into a service. But most attackers explicitely want the password because they are not interested in some unimportant service but hope that you will use the same password with other services. So the alternative password will be completely useless to them unless another service uses the exact same hashing algorithm and the exact same salt.

| improve this answer | |
-1

Does it matter if a brute force search for a password returns a collision and not the password?

If a password is the only mechanism for accessing a resource, it often does not matter if it is exact or a collision. If you enter "dog" or "cat" and your hashing algorithm was string.length, then either will grant you access.

While this is often the case, it is also a matter of the program/service's implementation details. For instance, a site/service may perform authenticity and runtime validity checks, which assess the password and where the password is coming from. So even if "dog" and "cat" could grant access, if the middleman has a rule that passwords can't begin with "d" then that collision is out.

Additionally, some more secure services sometimes collect metadata (also hashed) on the supplied password (e.g., length, number of bytes, etc.) and inconsistencies in that metadata is sometimes used to flag, deny access, or reset password to accounts.


OP Example

h(3) = 3 mod 17 = 3

Is the problem that the password hashing space (0-16) is much smaller than the space of the allowed password, or is there something else I'm overlooking?

To address your question of the problem; there are many problems with the example; including, simplicity and too many potential collisions. Without any rules of enforcement, the issue isn't about the entry window size. The problem is the hashing algorithm leads to too many collisions; 3 plus multiples of 17 ({3,20,37,54...}) all result in 3.

The collisions are what’s important because it’s the hash that is used for authentication and verification; if the brute force can enter the 20 or 37 or 54... and still access the account or resource, the original password doesn’t matter.

To circle back to the original question, it is often the case that all that is required is the collision. In fact, this is often how WiFi intrusion works. The hash is found, which allows connection to the password-protected gateway.

| improve this answer | |
  • 4
    First, the hashing algorithm was intentionally used to make it easy for to show a collision. Second, I don't think salts are really relevant. Salts are a unique per user nounce. They typically help to avoid precomputed attacks. So it's both out of the scope because this is only considering one user and because we're talking about brute force, not a precomputed attach. – MikeSchem Mar 13 at 16:48
  • @MikeSchem thank you. I consider salts relative. In fact, now that I view the other two answers for what’s been accepted by the community, one talks about a dictionary (a form of pre-computation) and the other mentions salts. By your standard, are we all in violation? The question also wasn’t clear what was being attacked, it was about brute forcing. You can brute force your way into an email account, which your input would go through a hashing algorithm, or you might brute force your way into the underlying database – vol7ron Mar 13 at 17:01
  • 8
    I believe OP is asking if there's a practical difference between finding the real password and finding a collision, which the other answers do speak to. This answer is mostly about the probability of finding a collision in the first place, which, as I understand the question, is besides the point. – Josh Eller Mar 13 at 18:08
  • @JoshEller ah, thank you. I don't consider it beside the point. I think the crux of what was mentioned was if the brute force can enter the 20 or 37 or 54... and still access the account or resource, the original password doesn’t matter the practical difference is none. Perhaps I can make that clearer – vol7ron Mar 14 at 5:17
  • @JoshEller I removed most of the commentary and delved more into what you mention as the heart of the question. Does that seem more suitable? – vol7ron Mar 14 at 5:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.