sha – Odds of two messages sharing the same hash prefix

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?


  • 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?