Odds of two messages sharing the same hash prefix

Question

If only the first h bits of a certain SHA256 hash H of a certain message M are known, and one had managed to successfully guess an input message M' whereby SHA256( M' ) yielded an H' whose first h bits match the known h bits of H, is there any way to formalize what the likelihood is that the guessed M' is identical to M?

ie.:

• Pick any M, set H = SHA256( M )
• Pick any M', set H' = SHA256( M' ), such that:
• H[0..h] == H'[0..h]
• What are the odds that M == M'?

Given that SHA256 is expected to be cryptographically unbiased, is it fair to assume that the likelihood is h / 256?

Bonus question: What about HMAC-SHA256, where the message is also a given but the key is being guessed?

Barring an immediate answer, how would I approach this problem?

Edit:

• My original question did not bound for the size of M. Let's assume a known fixed-length M of size m. Bonus points if you can describe a way to loosen these bounds and still formalize an approach to calculating collision odds.
• If any additional bounds are required in order to formalize a response, feel free to introduce and justify them.
• The best answers are supported by a rational that can be checked, followed and validated, not merely statements of fact.
• I assume the overall odds of a hash collision in SHA256 will play into the final solution.
• Bonus points if you can generalize your answer beyond SHA256.

Answer 1

My set theory is a bit rusty, but here's my shot at a proof sketch (corrections or objections welcome):

Assumptions and definitions

• Hash is a one-way function producing an output which is a binary string of length h satisfying the avalanche effect. (note that I don't care if h is the full output size of some underlying hash function, or if it's been truncated to h; as long as the underlying hash function is a well-behaved cryptographic hash, then we're ok to abstract this away to a hash function of length h.)
• M is a finite set of possible messages. Binary strings of length l (let's call that M_l) would be an example message space.
• Size(M) is the number of possible messages. For binary strings of length l, Size(M_l) = 2^l.
• I assume that any given hash value h has at least two messages that hash to it. In particular I assume that the message space is much larger than the hash space (ex.: h << l) such that this is true. If there are fewer possible messages than hash values, then you aren't guaranteed that any given hash value actually has a corresponding message, let alone two, and all this math blows up.

Formula and proof sketch

So for m1, m2 \in M, we want to know the probability that m1 = m2 given that H = Hash(m1) = Hash(m2).

Let's partition the set of messages m \in M into classes according to their hash value Hash(m). There will be 2^h classes. Given the avalanche effect of Hash, we expect M to partition uniformly over these classes (ie each class will have an equal number of members), which will be Size(M) / 2^h members per class. Or stated differently, a given hash value H will have Size(M) / 2^h messages which hash to it.

Assuming the messages m1, m2 were pulled independently and uniformly randomly (aka uniformly IID) from M, then given that we know they are in the same class, there is a 1 / class_size = 1 / (Size(M) / 2^h) = 2^h / Size(M) chance that they are the same element.

For messages of length l that will be 2^h / 2^l = 2^{h - l} chance that they are the same element.

Playing with some numbers:

• Messages of length l = 256 bits (say, AES keys) and h = 32 bits, you have 2^{32 - 256} = 2^-224 chance that they are the same message.
• Messages of length l = 600,000 bits (size of an average email) and h = 32 bits, you have 2^{32 - 600,000} = 2^-599,968 chance that they are the same message. (see footnote 1)
• Messages of length l = 1,120,000 bits (size of an average bitcoin block) and h = 19 bits (the current number of leading zeros), you have 2^{19 - 1,120,000} = 2^-1,119,981 chance that they are the same message. (see footnote 1)

Footnotes

1. The assumption that m1, m2 \in M are chosen uniformly randomly is very much not true for most real-world examples of things we hash (passwords, TLS messages, emails, bitcoin blocks, etc) which all have structure, and therefore it is very much not the case that any bit string {0,1}^l is equally likely. So this math may or may not have anything to do with the real world in which cryptography is used. Modifying this to accommodate messages that are not uniformly-distributed is well beyond my stats and set theory skills.

Answer 2

In the problem description the length of the original message is not known or in any way restricted^*. With this condition there is an unlimited number of messages which result in a specific hash. The odds that a single message is the correct one from a possible unlimited number of message with the same property (i.e. same hash prefix) is practically zero.

---

^* This was true for the original problem description. The OP did change the question many hours after it was asked and answered, to add a restriction about the message length. For this see the other answer.