4
$\begingroup$

I know that message collisions are supposed to be hard to calculate for a good cryptographic hash.

Given 1k worth of data, it's hard to find another 1k worth of data that collides with the same hash.

But doesn't it become much easier when the message becomes variable length? I.e. it's easier to find a collision in 0-1G of data to 1k of data than it is to find one that is also exactly 1k of data.

Does knowing the intended size of the message increase the strength of USING the hashing function? I.e. a message has to be between 1k and 4k.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ It is at least as easy to find a collision in variable length than in the same length, that's for sure. $\endgroup$ – Nova Oct 11 '15 at 11:11
3
$\begingroup$

The short answer is that for any secure hash it is impossible to generate collisions or second preimages, regardless of message length.

If you look at theoretical attacks, however, message length can be a factor. When looking for another message that hashes to the same value as a specific message you are talking about second preimage resistance (or target collision resistance) and there the length of the target message may matter. For example, with Merkle-Damgård hash functions there are attacks that find second preimages for messages faster the longer they are.

With a collision attack, where you look for any pair of messages hashing to the same value, I do not know of a case where message length matters. Beyond allowing enough input length to exhibit collisions, of course: finding e.g. 1-byte collisions is impossible.

Improve this answer
$\endgroup$
  • $\begingroup$ Is there anyway to prove (mathematically or not) that changes in message length do not affect TCR? $\endgroup$ – Rahly Oct 11 '15 at 19:21
  • 1
    $\begingroup$ The definition of security does not limit message length in any way. So, this tells you that it should be hard to break in any case. The things that makes a very big difference is the OUTPUT LENGTH of the hash. $\endgroup$ – Yehuda Lindell Oct 11 '15 at 21:09
  • $\begingroup$ @Rahly, like I wrote in the second paragraph, message length can affect TCR, but like Yehuda Lindell wrote above, security definitions assume arbitrary length so any hash that is collision resistant is by definition resistant regardless of message length. $\endgroup$ – otus Oct 12 '15 at 8:32

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.