4

While discussing maximum password lengths, a poster made this comment:

The longer the allowed input, the easier to supply an input that could cause a hash collision

To explain (since the lack of context might make the statement unclear), the poster is stating that it is easier to find a hash collision for a longer password than for a shorter one. I had not heard this before, and now I'm curious. My own (admittedly naive) expectation is that the collision probability should be fairly independent of message size since collisions happen in digest space, and the digest is fixed length.

What pieces of the puzzle am I missing? Does the ease of finding a collision depend on input length?

Improve this question
4
  • I wrote the comment in question. I did not mean to say that longer passwords have a higher collision chance, but rather that allowing long inputs increase the chance a collision is found/exists, for a hash of a password, irrespective of the length of the original password. I may be wrong though.
    – Jacco
    Sep 18, 2017 at 18:38
  • It sounds like you have the same thing in mind that Steffen did in his comment. Thanks for helping to clarify!
    – Conor Mancone
    Sep 18, 2017 at 19:27
  • 3
    In theory, due to pigeonhole principle, the larger the input domain, there will be more collisions. In practice, larger input domain does not make it easier for an attacker to find collisions.
    – Lie Ryan
    Sep 20, 2017 at 3:45
  • Just another in practice note: in modern recommended cryptographic hashing algorithms (SHA-2, SHA-3), there have never been any collisions found, and in recent cryptographic hashing algorithms (MD5, SHA-1), there have never been any collisions found through straight brute-force or mere chance. So I wouldn't worry much about issues slightly affecting the chance of a random collision because the chance is already ridiculously low.
    – Macil
    Sep 21, 2017 at 0:44

2 Answers 2

Reset to default
7

What pieces of the puzzle am I missing? Does the ease of finding a collision depend on input length?

For finding a collision it is not relevant how long a string is (apart from the time needed to compute the hash - which is actually longer for long strings) but how many different strings you try. Because the more different inputs you have the higher is the chance that any of these result in the same (fixed length) hash value, i.e. a collision. And there are simply more different long strings than short strings.

For example: there are 10^3 = 1000 strings with 3 digits but already 10^6 = 1000000 strings with 6 digits. If you imagine a hash which consists of 4 digits then there might be a collision with the 3 digit strings but there will be definitely many collisions within the 6 digit strings because there are way more string values than hash values.

The longer the allowed input, the easier to supply an input that could cause a hash collision

The statement you cite is wrong in the current form. It is true that the chance is higher that the strings you'll find will be long. But since there are many more long than short strings this does not make finding a collision any easier. Again, what counts is the number of different inputs you have and not the length.

Improve this answer
4
  • 1
    tldr: No, longer messages do not have higher chance of collision
    – CaffeineAddiction
    Sep 18, 2017 at 18:08
  • So: if the input string is shorter than the digest length, then it's likely that no collision exists, so it's impossible to find. The longer the input is relative to the digest, the greater the chance that a collision exists. However, given a fixed amount of resources spent trying to find a collision, the probability of finding a collision is (mostly) constant in terms of the input length (if hashing longer strings takes longer, longer strings would actually have a lower chance). Correct?
    – Acccumulation
    Sep 18, 2017 at 20:11
  • 1
    @Acccumulation: mostly correct. If the hash is 20 byte (like SHA-1) and you try all strings with less than 20 bytes (i.e. with 1,2,3,...19 bytes) you exhaust about 0.4% of the space the hash has with its 20 bytes. I would not call getting a collision based on this not impossible and not even very unlikely, but just unlikely.
    – Steffen Ullrich
    Sep 18, 2017 at 20:22
  • @Acccumulation The exact length of inputs needed to find the first collision is not known. But it's extremely likely to be half the length of the hash output ±1 bit. So 79, 80, or 81 bits in the case of SHA-1. So saying that the probability of a SHA-1 collision with two random strings shorter than 60 bits is exactly 0 is probably a true statement. But once you cross the 80 bit boundary the probability will quickly converge towards a constant which is independent of the input lengths.
    – kasperd
    Mar 2, 2019 at 14:46
0

I think the poster of the comment was referring to the following:

As the size of the input space (all possible input strings) increases, the probability to find a collision when exhausting the space increases and eventually reaches 100% when input space size is larger than size of all possible hash values.

Example:

Assuming a 32 bit well behaved hash function. If you only allow the strings "0" and "1" as input, the probability of hash collision is low since the amount of input values (2) is much, much smaller than the amount of hash values (2^32 = 4,294,967,296). The chance of collision is actually 1 / 2^32.

However if you allow all possible strings of exactly 8 lower case alphabet characters, you are guaranteed to eventually find a hash collision since there are now 26^8 = 208,827,064,576 input values, which is much larger than 2^32.

Edit: I meant to post this as a comment, but can't comment yet...

Improve this answer

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.