Is it possible that two different messages have same hash code?

new-to-crypto

12/8/23, 5:12 PM

As I know a very common hash code has 256 bits.

From a message, it outputs a hash code that's 256 bits. That hash code should be unique to that message. That message can be something like email.

But a message can be very long, far longer than 256 bits.

Theoretically there can be 2^256 different hash codes, and that's insanely large number.

But if a message contains 1000 letters, each letter being 8 bits, that's 8000 bits. Also 2^8000 different messages possible. Even if we just talk about 2^1000 possible messages that's still huge. So we put a long string of bits, and produce a 256 bits named "hash code".

If we divide 2^1000 messages by 2^256 hash codes, there are 2^744 messages for each hash code.

How is it possible that a hash code is unique to a message? Shouldn't there be some collusions, like two different messages having same hash code?

307

1 + 1

collision-resistance

fgrieu

12/8/23, 5:22 PM

TL;DR: It's mathematically certain there are distinct messages with the same hash; yet by design a good hash makes it practically impossible to exhibit any concrete example of such collision. There is one (not $2^{744}$) hash codes for each message, because a hash function is a function. With the question's hypothesis, there is _at least_ one hash code with at least $2^{744}$ messages; and for a hash that behaves like a pseudo-random function, there is _about_ $2^{744}$ messages with a given hash code.

Score:0

Crypto

Pegasus

12/8/23, 5:17 PM

The number of possible hash codes is much larger than the number of possible messages, but it is not true that there are 2^744 hash codes for each message. In fact, the number of possible hash codes for a given message is much smaller than 2^256, because a good hash function will distribute the possible messages evenly across the space of all possible hash codes. This means that, while it is theoretically possible for two different messages to have the same hash code (known as a "collision"), the likelihood of this happening is extremely small for a well-designed hash function. Therefore, we can say that a hash code is "unique" to a message in the sense that it is highly unlikely for two different messages to have the same hash code.

+ 0

Elon Musk

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

EN: Is it possible that two different messages have same hash code?

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.