For a hashing function like MD5, how similar can two plaintext strings be and still generate the same hash?

Question

When I say similar, I'm referring to the Hamming distance, the Levenshtein distance, or a similar string distance metric that measures how similar or dissimilar two strings are.

For instance, are there two plaintext strings with a Levenshtein distance of 1 which share the same MD5 hash? If not, do we know the smallest Levenshtein distance possible for a pair of strings which share the same MD5 hash? Is it even possible to determine this with certainty?

I'm asking about MD5 since it's a well-known and simplistic hash. But I'd love to know how this applies to SHA-2, bcrypt, or other common hash functions.

There's a similar question which is looking for the shortest length strings that can generate a collision, but I'm looking for the smallest string distance to generate a collision. The actual length of the source strings isn't important.

(Asking purely out of curiosity; I don't have a real-world use for this)

Answer 1

This answer is based on the work by AleksanderRas, although my conclusion is different.

First, to lay out a definition, a hash is a function that takes an arbitrary length input to a fixed length output. For example, MD5 takes any input and produces a 128 bit output.

A cryptographic hash is a hash function which has certain additional security properties.

Because a hash function takes an arbitrary length input and produces a fixed length output, it is guaranteed that there are some inputs which produce the same outputs. These are collisions.

Finally, the Hamming distance is the number of bits by which two inputs of the same length differ.

---

For any hash function, whether or not it is a cryptographic hash function, there are inputs with a Hamming distance of 2 which collide. This can also be shown by the pigeonhole principle:

• Suppose that the hash function returns an n bit output.
• There are 2ⁿ possible outputs.
• Consider a string B which is 2ⁿ + 1 bits long.
• Consider then the set of all strings which differ from B in exactly one bit. There are 2ⁿ + 1 such strings.
• The Hamming distance between any two different strings in this set is 2: a 1 bit change to get back to B and a second 1 bit change to get to the other string in the set.
• Because there are more strings in this set than there are possible output hashes, at least two strings must share a hash.
• Therefore the hash function has a 2 bit difference collision.

---

It is possible to construct a hash function which does not have any collisions between strings with Hamming distance of 1. This can be shown as follows:

• Consider a string B
• Consider a string C which has Hamming distance of 1 from B.
• The parity of B must be different from the parity of C. That is, if there are an odd number of bits set in B, there must be an even number in C and vice versa.
• Therefore any hash function which directly encodes the parity of the input, such as regular MD5 with the parity bit appended, will have a minimum Hamming distance of 2.

There are less trivial hash functions than the parity one which have a minimum collision hamming distance of 2. For example, CBC-MAC is a family of algorithms which encrypts a bitstring with a fixed key under CBC mode, and returns the last block. This meets the definition of a hash function: it takes an arbitrary length input and returns an output fixed at the size of the block. Although (like all hash functions) CBC-MAC is vulnerable to collisions, it cannot have a collision if all changes occur within a single block. (This property comes from the fact that it is an encryption function and therefore a permutation, but further elaboration would be off topic) Since a hamming distance of 1 corresponds to a single bit change, and that single bit change is necessarily in just one block, it cannot cause a collision.

---

This should not be taken to mean that the smallest Hamming distance between collision inputs for every hash function is 2. There are functions with a minimum Hamming distance of 1: for example, the trivial hash function truncate. That is, given an n bit hash function which simply drops all but the first n bits, varying bit n+1 will (because it is ignored by the algorithm) give a collision.

So, when it comes to particular hash functions, the answer could be 1 or 2.

Others have argued that for MD5 and other standard cryptographic hash functions it will probably be 1. This is a purely probabilistic argument, but in the absence of evidence to the contrary it is a reasonable to use probability with hash functions which are designed to behave randomly.

Answer 2

The answer is 1 bit (Hamming-distance = 1) for any cryptographic hash algorithm.

There are definitely collisions, since the digest of the MD5 algorithm is always 128 bits long but there are more than 2¹²⁸ possible inputs.

We can explain this due to the Pigeonhole principle.

---

Mathematical explanation

Let's say we take an input message of 3 bits:

There are 8 possibilities in total, because 2³ = 8:

• 000
• 001
• 010
• 011
• 100
• 101
• 110
• 111

So for an input length of n bits we have 2ⁿ possible values.

If you take the first bit-string as an example (000) you can easily see that there are three possibilities that have a Hamming-distance of 1 (001, 010, 100)

In theory you could just take a bit-string of length 2¹²⁹ where all bits are zeros (000...000). We hash this bit-string and call it A. Then replace the first zero with 1 (000...001) and look for a collision with A, if not replace the second zero with 1 (000...010), and so on. This will definitely give you a hash collision since 2¹²⁹ > 2¹²⁸ (you have 2¹²⁹ possible inputs but only 2¹²⁸ possible outputs). This is the simplest example I can think of (although it would take far too long to achieve this).

Note that this is the case if the assumption holds up that MD5 is a perfect hash function (and it definitely isn't). In practice we could perform this experiment with far less than 2¹²⁹ bits and expect a collision.

Note also that you can't be sure to get every possible hash output with the procedure explained above. The pigeon principle only says that there are at least some collisions. There could be a hash value that doesn't correspond with any input, i.e. there is no input that can generate the hash value of 128 bits of zeros (000...000). We have the assumption that every hash value is possible but we can't prove it.

The same experiment could in theory also be performed with other hash functions (MD5, SHA1, SHA2, etc.) if we accept that there really is no limit of inputs (apparently there is an input-size limit). You would just have to change the length of the possible hashes for the experiment. It would even apply to a perfect hash function.

Answer 3

There are two answers to this: one practical, and one theoretical.

First, the practical one: MD5 is a broken hash function, and we know of collisions for it, and a quick web search turned up a collision with a hamming distance of 6.

Second, the theoretical one: Most cryptographic hash functions are designed to be a reasonable approximation of a random function (this isn't usually the definition you see in textbooks, but it's an important design goal, due to how hashes are used in practice). MD5 turns out to be a poor approximation of a random function (because it's known to be broken), but let's assume it's not.

If you take some random binary data, and a random neighbour (hamming distance 1), there's a one in 2^128 chance that there'll be a collision. Simply because there's a one in 2^128 chance of any other piece of data being a collision. That's very unlikely, but you can try again with a different piece of data and its neighbour. Every time you try, you've got a 1 in 2^128 chance of finding a collision, so if you keep trying forever (which is a very long time), you're almost certain to find a collision with a neighbour.

So the theoretical minimum collision distance is 1, and we suspect such a collision exists.

But in practice, the time you'd need to take to find this collision is prohibitively large (larger than the age of the universe). Indeed, in a well-designed cryptographic hash function, the time taken to find a collision at all (i.e, not limited to a neighbour) should be prohibitively large.

We shouldn't be able to find any collisions in MD5 at all, in a reasonable amount of time. The fact that we can, is why we say it is broken.

Answer 4

An important aspect of cryptographic hash functions is that even the smallest difference in input usually results in different output. But given the unlimited input space compared to the limited output space of the cryptographic hash it is likely that sequences with only small differences (like a single bit) but the same hash value exist.

But for a more reliable statement and maybe some math behind it I recommend to ask at crypto.stackexchange.com.

Answer 5

We can prove an upper bound of 2 bits (Hamming distance = 2) for any algorithm

Upper bound

This upper bound is for hashing algorithms whose output is a bit string of length 128 (like MD5). It can be generalised by replacing 128 with n

Let A be any bit-string of length 2¹²⁸.

Let S be the set of A and all its neighbors. Here a neighbor is a String that differs from A in exactly one place.

Since there are 2¹²⁸ bits in the string, |S| = 2¹²⁸+1

The Pigeonhole principle tells us that any hashing algorithm whose output is a 128 bits long string, must have at least one collision on the set S (the number of different strings is 2¹²⁸).

Since the Hamming distance between any two elements in S is at most 2, we have proven an upper bound.

Lower bound

We can prove a lower bound of 2 for a hash function that optimizes the minimum Hamming distance between collisions.

Intuition

Consider a hashing function that outputs the parity of an input string. This hashing function will not have any collisions on neighboring input strings. A hashing algorithm that optimizes the minimal distance between collisions will be at least as good.

Graph theory

With a bit of knowledge about graph coloring and bipartite graphs, we can create a slightly more formal proof.

Consider an undirected graph G . Its nodes are the binary input strings of some length n , and there is an edge between two nodes if and only if the input strings have a Hamming distance of 1. The color of the node will correspond to its hash.

Since the parity of a binary string is always different from its neighbors, this graph must be bipartite.

A bipartite graph can be colored with two colors such that no neighbors share a color. What this means is that a hashing function with at least one bit of output (two options), can avoid a collision between any neighboring input strings.

Conclusion

We have proven that for MD5, and any other hashing algorithm, there exist two input strings with a Hamming distance of at most 2, that will cause a collision.

For a hashing algorithm that maximizes this distance, we can prove a lower bound of 2.

Answer 6

MD5 and SHA-1 are badly broken functions. But you can think about an abstract good cryptographic hash function, and pretend it generates a different random number of some length for each different input, and model the collisions you'd expect that way.

The XOR of two random hashes is another random number of the same length. So you can generate a random number, the length of your hash function's output, by picking a string s and XORing hash(s followed by byte 0x00) with hash(s followed by byte 0x01).

When the number you get from that XOR is 0, you have a collision. Now, try all 2^128 16-byte strings as s, and do the XOR of two hashes as above. One of the 2^128 128-bit random numbers you get will be zero, more likely than not--I think the probability is (very close to) 1-1/e.

If you get unlucky and don't get a collision, you try a few more times with 0x00 and 0x01 replaced by a different pair of suffixes that differ in one bit (e.g. 0x02 and 0x03, or multiple bytes when you run out of one-byte pairs). As you try more times, the chance you still don't get any collisions from a random-ish hash drops exponentially.

You can model it more precisely than that, and fill more details in. But I hope that's enough to intuitively suggest that a good hash will probably have a colliding pair of inputs that only differ by one bit and aren't much longer than the hash's output.

There isn't much you can do with that since you can't try 2^128 inputs to a hash; we set output lengths specifically to make those searches impossible. Fun to see that examples like that ought to exist out there, though.

Answer 7

Simple answer: MD5 is a finite set, meaning that since an MD5 is 32 characters long, made up of HEX characters, you could literally write out or calculate every combination. The input set however is infinite, there is no limit to the things that could be put into an MD5 hash. With an infinite input set and a finite output set, there must be overlap from different inputs.