1
$\begingroup$

If I hash a 256-bit message and generate an output digest of the same size with a cryptographic hash function then the number of guesses to find a collision is expected to be 2^128.

Does increasing the message size also increase the expected number of guesses to find a collision?

If yes, can the hash function internal state have any size or does it always have the same size, regardless of the input?

$\endgroup$

1 Answer 1

3
$\begingroup$

No, the collision resistance is dependent on the size of the hash function's output. You also seem to have confused it with second preimage resistance.

Collision resistance asks how hard it is to find two messages that have the same output when hashed. More formally, it should be computationally infeasible to find any two messages $m1$ and $m2$ such that $hash(m1)=hash(m2)$.

Second preimage resistance asks how hard it is to find a second message that shares the same output as a given input message. More formally, given an input $m1$, it should be computationally infeasible to find a different input $m2$ such that $hash(m1)=hash(m2)$.

Preimage resistance asks how hard it is to find an input that hashes to a given output. More formally, given a hash value $h$, it should be computationally infeasible to find any message $m$ such that $h=hash(m)$.

Collision resistance implies second preimage resistance, but does not imply preimage resistance. So the difficulty of finding a second preimage is at least as hard as finding a collision, and does not depend on the input message size (for a secure cryptographic hash function).

$\endgroup$
1
  • 1
    $\begingroup$ Collision resistance implies preimage resistance as long as the function is compressing. $\endgroup$
    – Maeher
    Commented Mar 18, 2023 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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