Does an increase of message size increase the number of guesses to find a collision?

alpominth

3/17/24, 11:57 PM

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?

148

1 + 0

collision-resistance

Score:3

Crypto

SAI Peregrinus

3/18/24, 1:51 AM

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).

+ 1

Maeher

3/18/24, 9:46 PM

Collision resistance implies preimage resistance as long as the function is compressing.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Does an increase of message size increase the number of guesses to find a collision?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.