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)

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 2n possible outputs. 
Consider a string B which is 2n + 1 bits long.
Consider then the set of all strings which differ from B in exactly one bit. There are 2n + 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. 
