I realize that a hash function is a one way function, and that changes in the hash are suppose to tell us that the original data has changed (that the entire hash changes on even the slightest changes to data).
But is there a way to find out to what degree has the original data changed when two hashes are different?
You can test this yourself by creating a hash over a specific data set, and then a modified hash over a different data set. You will see that every bit of the resulting hash function has about a 50% chance of flipping.
I'll demonstrate this by creating the SHA-256 hash of the string MechMK1:
$ echo -n "MechMK1" | sha256sum
2c31be311a0deeab37245d9a98219521fb36edd8bcd305e9de8b31da76e1ddd9
When converting this into binary, you get the following result:
00101100 00110001 10111110 00110001 00011010 00001101 11101110 10101011
00110111 00100100 01011101 10011010 10011000 00100001 10010101 00100001
11111011 00110110 11101101 11011000 10111100 11010011 00000101 11101001
11011110 10001011 00110001 11011010 01110110 11100001 11011101 11011001
Now I calculate the SHA-256 hash of the string MechMK3, which changes one bit of the input:
$ echo -n "MechMK3" | sha256sum
3797dec3453ee07e60f8cf343edb7643cecffcf0af847a73ff2a1912535433cd
When converted to binary again, you get the following result:
00110111 10010111 11011110 11000011 01000101 00111110 11100000 01111110
01100000 11111000 11001111 00110100 00111110 11011011 01110110 01000011
11001110 11001111 11111100 11110000 10101111 10000100 01111010 01110011
11111111 00101010 00011001 00010010 01010011 01010100 00110011 11001101
I compared both results and checked how often a bit differed from both hashes, and exactly 128, or 50% of all bits differed. If you would like to play around with this yourself and see what kind of results you get, I created a simple C program that does exactly that.
TL:DR; 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 *.
x' such that h(x') = y when given any y for which a corresponding input is not known.x, to find a 2nd-preimage x' != x such that h(x) = h(x').x, 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
As the other answers have already noted, the answer is "no" for cryptographic hash functions. These are generally designed to behave as much like a perfectly random function as possible, and any detectable similarity in the hash outputs generated for similar inputs would also allow the hash to be distinguished from a random function.*
However, there are other kinds of hash functions, such as locality-sensitive hashes, for which the answer can at least be "yes, sometimes".
In particular, locality-sensitive hashes typically feature properties such as "any two inputs differing by at most δ according to some similarity metric will, with probability p > 0, have hashes that differ by at most ε(δ) by some other (possibly the same) similarity metric." Typically, the distance metric for the hashes may be something like Hamming distance, while the corresponding metric for the inputs might be e.g. edit distance. The choice of a suitable locality-sensitive hash function mainly depends on which particular distance metric you're interested in.
*) Technically, the classical definition of a secure cryptographic hash only requires collision resistance and first and second preimage resistance. I don't see any obvious way to prove that a hash function could not have these properties while also being locality-sensitive in some way, although they do impose some rather significant constraints. In particular, the number of hash outputs within a distance of ε(δ) from any given hash output H(x) would have to grow faster than the number of other inputs within distance δ of the corresponding input x for any reasonable values of δ, as otherwise simply testing a bunch of similar inputs would very likely yield a collision. In any case, I'm not aware of any locality-sensitive hash functions that would meet even this weaker definition of cryptographic security, and I have no idea what such a hash might look like if it existed.
I'm sure there is a hash type where this might be possible, but the point of a cryptographically secure hash is to make sure that doesn't happen. One should not be able to make any guesses or deductions about changes to the message based on changes to the output of the hash.
Cryptographic analysts measure this by the Avalanche Effect. Strong hashes should make big changes to the output even when tiny changes are made to the input.
base64(input).substring(0,10) is technically a hash function.
string did things like "take the first four bytes of the string's byte representation and convert them to int". It's quite fast, at least :P
rot13() is a hash function. I was giving the OP the benefit of the doubt.
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. This is the first line in the wikipedia article for Hash Function. Mapping arbitrarily sized data to fixed-size values will always be one way (pigeonhole principal)
Yes, but only for fuzzy hashes such as ssdeep https://ssdeep-project.github.io/ssdeep/index.html that are specifically designed to measure similarity between files, and hashes that only cover certain portions of the file that don't include changes, such as imphash https://www.fireeye.com/blog/threat-research/2014/01/tracking-malware-import-hashing.html . There are other types of hashes that have been mentioned in the comments to the question, but since I'm not familiar with them, their properties, and usage I won't go into them here. Feel free to add to this answer if you have any other types of hashes I didn't just cover.
Outside of specialized hashes that are either designed to track similarity, or that don't cover the entire input, the answer would be no as per kelalaka's or MechMK1's answers to this post. It is possible that my described functions are not true hash functions, but they are named as hash functions within my community.
A strong hash function should with a small change result in a big difference in output hash, that said if you want to check the difference between two values, you can use a hamming distance algorithm
Error correction codes are a type of hash function which not only allow some changes to a message to be detected, but also allow those changes to be corrected. Changes can only be corrected for some degree of error, of course. Generally the larger the error correction code is relative to the message, the more changes can be detected and corrected.
Error correction codes are optimised for this ability to correct changes. That does mean though that they may not be optimal at detecting changes to a message where the change cannot be corrected. They are primarily intended as a hash for messages where retransmission is not easily possible, and hence recovery of the original message is the priority. They also assume that intentional attacks on the message will not occur.
Cryptographic hashes, or even less secure hashes such as CRC, tend to work differently. Generally these are used either in situations where retransmission of a faulty message can be requested, or where there is a risk of intentional attack and faulty messages must be robustly detected and rejected. These are always one-way functions, and the degree to which they are "one-way" indicates how robust they are. As previous answers have said, a good cryptographic hash will not provide you with any information about the original message.
You could construct a hash function specific to the purpose.
Consider doing a byte-for-byte comparison of the files and incrementing the hash for each difference. Add the difference in lengths. It is a hash function that delivers a one-way computation that directly relates to the degree of difference.
If you want a more intelligent hash function, try "diff file1 file2 | wc -l".
