48

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?

  • 50
    The answers you'll get here apply to cryptographic hash functions. Keep in mind that there are other types of hash functions with different properties, such as perceptual hashing for images. – Mark Feb 19 at 20:55
  • 6
    Defining a “differenceable digest” is non-trivial and application-specific - basically you’re asking for an ultra-lossy compression algorithm. An example is a program that takes a photo or image and essentially downscales it to (for example) 64x64px (giving a “hash size” of 12KiB). Then, a different, but visually similar, image given the same treatment will then have a very similar 64x64px representation and a “difference” measure can then be derived (e.g. comparing pixel histograms). That’s an elementary example though. Also see stackoverflow.com/q/6499491/159145 – The D Feb 20 at 0:47
  • Especially when Salt is used, there is no chance of finding the difference. – Alex Probert Feb 20 at 11:20
  • 4
    w-shingling. MinHash and SimHash being practical applications. – Damon Feb 20 at 11:43
  • 7
    All of the hard negatives here are in the context of a secure hash function; this being an InfoSec Q&A site, it makes sense. However, the type of construction you're asking for exists in several forms and has many useful applications. For example, locality-sensitive hashing can be used to probabilistically determine how similar two inputs are. – Kittoes0124 Feb 20 at 13:57
93

No, at least with a good hash function.

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.

|improve this answer|||||
  • 66
    My thought reading the question was "Gee, I sure hope not" – Cruncher Feb 19 at 20:30
  • 2
    Technically, this only proves half of the question. If flipping one bit causes 50% of all bits to flip, but flipping two bits causes 75% to flip (50% + .5*50%), then you can tell the difference based on the fact that bigger differences cause more change. I know that's not actually the case, but I think it'd be worth a mention in this otherwise excellent answer. – Bobson Feb 20 at 13:54
  • 2
    @Bobson I think that the other answers, that go a bit more into the theory behind it, answer that much better than I can. I just wanted to provide some hands-on demonstration and encourage people to try things for themselves. – MechMK1 Feb 20 at 14:04
  • 8
    @Bobson flawed thinking there - imagine 100 bits all 0s. Flip half the bits at random. We now have half and half, 50 0s and 50 1s. Now flip half of all the bits at random again - half (on average) of what we flip is going to be a 0->1 and the other half have already been flipped so we get 1->0. We still stay at ~50% 0s and 1s, just the distribution of bits with a 1 value changes. – Baldrickk Feb 20 at 15:56
  • 1
    @Bobson I've updated my answer for multiple bit changes. The math is easy under the Random Oracle Model. – kelalaka Feb 20 at 17:41
37

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 *.

  • 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, 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

|improve this answer|||||
  • Is "collision resistance" implied by "2nd-preimage resistance" or am I understanding wrong? – Daniel Feb 19 at 19:43
  • @Daniel These definitions are taken from Rogaway and Shrimpton seminal paper Cryptographic Hash-Function Basics. On page 4, there is a simple graph of relations. Collision resistance implies 2nd-preimage resistance. If not 2nd-preimage resistant then an attacker choose an arbitrary m1 and compute a second preimage m2 to obtain a collision. Note that 2 => 1 requires special care – kelalaka Feb 19 at 19:51
30

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.

|improve this answer|||||
17

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.

|improve this answer|||||
  • 6
    "I'm sure there is a hash type where this might be possible". For sure! This trivially exists. base64(input).substring(0,10) is technically a hash function. – Cruncher Feb 19 at 20:33
  • 1
    @Cruncher Heck, there's been a time where the default hash functions (for things like hash tables) for 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 – Luaan Feb 21 at 7:28
  • 1
    @Cruncher technically rot13() is a hash function. I was giving the OP the benefit of the doubt. – schroeder Feb 21 at 7:30
  • @schroeder Since rot13 is reversible, I'm not sure I would consider it a hash function. We typically think of a hash as being the same size for every input which is why I didn't just say base64 without the substring. But anyway, it's semantics – Cruncher Feb 21 at 16:32
  • 2
    @schroeder 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) – Cruncher Feb 21 at 18:15
10

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.

|improve this answer|||||
4

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

https://en.wikipedia.org/wiki/Hamming_distance

|improve this answer|||||
1

You can, but then it isn't purely a hash function.

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.

|improve this answer|||||
  • "or even less secure hashes such as CRC tend to work differently (from ECC)" -- no. A CRC has the same structure as an error-correcting code. Typically it doesn't identify the error uniquely even under a restriction like "single bit errors", but it lends itself very well to performing a "correction" and finding some message that is consistent with the CRC. – Ben Voigt Feb 21 at 20:19
0

Hash does not always mean Cryptographic Hash

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".

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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