0

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.
5
  • If M' == M, then the entire hash would match. May 19, 2021 at 3:28
  • @user10216038 correct. The question makes no statement about the remaining hash bits, but if the guess of M' happens to match M, then H would also match H'. Note however from the question that only the first h bits of H are known, so there is no direct way of telling whether M == M', only the odds can be known.
    – lhunath
    May 19, 2021 at 3:37
  • Assuming a random distribution, the odds of generating a h-bit prefix collision can be approximated with 2**h. This is regardless of the total length of the hash. May 19, 2021 at 4:11
  • @fuzzydrawings The approximation of the probability of a collision is 1-(2^h-1)/(2^h). The approximation of the number of tries to have 50% chances of a collision (the birthday bound) is 2^(h/2) tries.
    – A. Hersean
    May 19, 2021 at 16:14
  • @A.Hersean 2^(h/2) - you're right. I was thinking of a chosen prefix collision May 26, 2021 at 15:54

2 Answers 2

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 Ml) would be an example message space.
  • Size(M) is the number of possible messages. For binary strings of length l, Size(Ml) = 2l.
  • 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 2h 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) / 2h members per class. Or stated differently, a given hash value H will have Size(M) / 2h 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) / 2h) = 2h / Size(M) chance that they are the same element.

For messages of length l that will be 2h / 2l = 2h - 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 232 - 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 232 - 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 219 - 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.
6
  • From your analysis and with the givens as you stipulated them, it seems to follow that if you have made a guess in which 255 bits of a 256 bit hash are known to be identical to a hidden source message, you still only have about a 50% chance to have guessed the source message, which seems a bit counter-intuitive on the face of it (given how rare of an event this must be), but I suspect the origin of this finding is in the assumption that the original message M is uniformly random.
    – lhunath
    May 21, 2021 at 15:15
  • @lhunath How are you getting that from my analysis? I think that's completely wrong. The only thing that matters is how many messages share that hash value (my formula uses the number of colliding bit, but only as a way to count how many messages share a given hash value). May 21, 2021 at 17:14
  • You would have a 50% chance to have guessed the source message if there are only 2 possible messages that hash to that value. May 21, 2021 at 17:15
  • My bad, In your "For messages of length l that will be 2h / 2l = 2h - l chance that they are the same element." I set l to 256 and h to 255, but that does not reflect the statement I made since l is referencing the original message and h the length of the compared hashes. 50% would be the result of an original message whose length is 256bit and the 255bits in your guess' hash are known to match the message's 255bits hash.
    – lhunath
    May 22, 2021 at 0:35
  • @lhunath Yes, sortof, but not really. Yes, you are correct that if l = 256, h = 255 you have 2^256 input messages and 2^255 output hashes; ie twice as many inputs and outputs, so if two messages have the same hash value and you know that there are only two possible messages that have that hash, then yes, there is a 50% chance that they are the same message. HOWEVER... May 23, 2021 at 20:09
1

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.

3
  • Technically correct is the best kind of correct.
    – A. Hersean
    May 19, 2021 at 16:15
  • Good point. Care to amend your answer to account for a fixed-size M where the size is known?
    – lhunath
    May 19, 2021 at 21:12
  • 1
    @lhunath: I don't consider it a good idea to significantly change the question after it was already answered and answers where upvoted already. Please refrain from doing this in the future but instead ask a new question. I will not address the significant changes in this answer since they are already addressed in a different answer. May 20, 2021 at 5:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .