2
$\begingroup$

If I had a hash function outputting a 256 bit hash, would there be any discernible difference comparing the last 50 bits of 2 hashes versus comparing the first 50 bits?

I guess what I am trying to say is can you have 2 hashes that finish with the same 50 bits yet have the first 206 bits different? (Assuming we are using Merkle-Damgård setup)

My gut says it shouldn't be any different because theoretically a hash should use all possibilities of hash values with equal randomness.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ If you only check 50 bits, a collision attack takes about $2^{25}$ hash calls. The choice of these bits doesn't matter as long as it's constant (e.g. you always look at the top or bottom or middle or whatever ones). $\endgroup$
    – SEJPM
    Oct 1, 2016 at 20:08

1 Answer 1

Reset to default
4
$\begingroup$

If I had a hash function outputting a 256 bit hash, would there be any discernible difference comparing the last 50 bits of 2 hashes versus comparing the first 50 bits?

No, not for a correctly constructed cryptographic hash function.

My gut says it shouldn't be any different because theoretically a hash should use all possibilities of hash values with equal randomness.

That is correct.

I guess what I am trying to say is can you have 2 hashes that finish with the same 50 bits yet have the first 206 bits different? (Assuming we are using Merkle-Damgård setup)

Yes, absolutely. There is always a possibility of two hashes matching by pure chance, but by checking only 50 bits instead of the full hash, you are increasing that probability significantly.

Checking only 50 bits of a 256-bit hash is essentially the same as checking all of a 50-bit hash (whichever 50 bits you choose). And as SEJPM is stating in their comment, the probability of two hashes of this size matching by chance is about one in $2^{25}$ (i.e. much higher than one in $2^{50}$) because of the birthday paradox. As user Meir Maor rightly pointed out, the birthday paradox does not apply here.

This answer to the similar question "Should I use the first or last bits from a SHA-256 hash?" might be of interest to you.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ If the first 50 bits of a hash function were better or worse than the last 50 bits, that would mean that some of the bits weren't as good as they could be, which would lead us to reject that hash function. $\endgroup$
    – David Schwartz
    Feb 27, 2017 at 12:20
  • 3
    $\begingroup$ "the probability of two hashes of this size matching by chance is about one in 2^25" This statement is incorrect. The chance of two randomly chosen hashes colliding is 2^-50. Birthday paradox only comes into affect when hashing many values making finding a collision easier. $\endgroup$
    – Meir Maor
    May 15, 2017 at 4:00
  • $\begingroup$ The $2^{n/2}$ number for $n$-bit hashes is a rough estimate of the point at which it becomes more likely than not that you will see at least one collision. The probability of a collision between two distinct messages is $2^{-50}$. The probability of a collision between $2^{50}+1$ distinct messages is one. For less than two distinct messages there is zero chance of collisions. For $2^{25}$ distinct messages the probability is (actually) about 39%. $\endgroup$
    – Future Security
    Aug 3, 2019 at 3:47
  • $\begingroup$ The point is that you can't figure out the probability of collision based only on the number of output bits. The probability depends also on the number of messages you want to try. The relevance of $2^{n/2}$ (to keep things simple) has more to do with the expected amount of work needed to find the first collision for a secure $n$-bit hash function. (Ignoring memory limitations) Using bruteforce search it might take you a lot more time or a lot less. But 99% of the time one would succeed in finding the 1st collision within $2^{n/2}$ tries give or take a factor of some small power of two. $\endgroup$
    – Future Security
    Aug 3, 2019 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.