In Cryptographic hash functions; the hashes of any two distinct messages should appear statistically independent.$
I realize that the hash is a one way function and that the changes in hash are suppose to tell us that the original data has changed (that the entire hash changes on even the slightest changes to data).
Avalanche Criteria, apart from being one-way, is also what we want from good Cryptographic hash functions;
a single bit change in the input results in changes in each of the output bits with a 50% probability.
multiple bits changes: this is a bit tricky, If we consider the hash functions archives to model a pseudorandom function according to the random oracle model then we can consider each input bit change, on average, with 50%, and that doesn't matter how much bit is changed.
One can see this by considering one bit, and flipping a coin if Head comes flip and if Tail comes don't flip 50% of flipping. Now, toss another coin and do the same. The result is the same (simple math).
Of course, we cannot achieve the random oracle model. Therefore, the output bits are not independent of each other. They seem to be as long as one can find a distinguisher and that would constitute a cryptanalytic attack against the hash function. Once one found for a good cryptographic hash function, you will see it in the news.
Proving that a hash function has Avalanche Criteria is a statistical process that you need to test many random input values. Not all inputs and bit complements result in half of the bit changed and this is not the expected behavior. You also need to show that the output bits are changed randomly.
If not satisfied this hash function can fail to satisfy pre-image resistance, 2nd-preimage resistance, and collision resistance *.
- preimage-resistance — for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output, i.e., to find any preimage
x' such that
h(x') = y when given any y for which a corresponding input is not known.
- 2nd-preimage resistance, weak-collision — it is computationally infeasible to find any second input which has the same output as any specified input, i.e., given
x, to find a 2nd-preimage
x' != x such that
h(x) = h(x').
- collision resistance, strong-collision — it is computationally infeasible to find any two distinct inputs
x' which hash to the same output, i.e., such that
h(x) = h(x').
Failure of each can cause attacks, and if it is successful then this can be devastating. An example; consider someone finds a second message to your original message that has the same has value (or the hash of the Linux CD ISO's);
This is a signed message representing the payment is $1.00, have a nice day
I will pay you $1,000,000.00 have a nice day
Hopefully, even SHA-1 and MD5 are resisting this attack. Therefore you can assume that there is a change in the data if the hash value changes. The probability that a random text will have the same hash with your value will be negligible.
But is there a way to find out to what degree has the original data changed when two hashes are different?
Hopefully, not. If there is a single bias that gives information about the changes that can be used by clever attackers.
* This are formal definitions and taken from rom Rogaway and Shrimpton seminal paper Cryptographic Hash-Function Basics:...
$ Thanks to FutureSecurity for the simplification