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?