Would increasing the “target space” of MD5 collisions make it significantly easier to find a collision?

This is tangential to this question, which asks about generating a file to match an exact MD5 hash.

My question is if it would be significantly easier to generate a file that is "within X digits of" an existing MD5 hash.

For example, if this is the MD5 hash I am trying to copy:

5f4dcc3b5aa765d61d8327deb882cf99

I would find these results acceptable as a 'copy' (differences are bolded):

5f4dcc3b5aa765d61d8327d5b882cf99

5f4dccab5aa765d61d8397deb882cf99

5f4dcc3b5aa765d61d8345debe82cf99

They are different, but without the bolded text would be difficult to detect with the human eye.

Does this significantly reduce the amount of time it would take to create an MD5 collision, given a hash, or is it on the same order? To say it another way, the fastest I was able to find was 2^24.1 (page 5), would having a larger "target space" significantly decrease this?

• Very interesting question. From a brute-force perspective, the answer is definitely yes, but the attack you mention is not a brute-force attack, so I'm not sure what the answer is. – mikeazo Jun 19 '20 at 18:52

Note: The attacks you refer to in that thesis are structural attacks, I will consider the complexity of a brute force attack, which would be applicable to any hash function $$H$$ which is well designed, approximating a pseudorandom function. There are some good answers here on the complexity of the birthday attack on a hash function, which is $$O(2^{n/2})$$ for an $$n$$-bit hash output.

Let $$b$$ be the number of bytes and $$n=8b$$ be the number of bits in the output of $$H.$$ It seems to me that you are happy for the hex output to be "almost correct". So we should consider the $$2b$$ output nibbles in $$\{0,1\}^4$$ and say that the output is almost $$f-$$correct if there are up to $$f$$ nibbles that are different than the output you are trying to get near to. For your examples, $$f=2.$$

The crucial thing is to identify the size of your 'target space', which is $$T:=2^{4}\sum_{j=0}^f\binom{2b}{j},\quad\quad\quad\quad(1)$$ since there are $$2^4$$ nibbles. Now, $$T=2^4(1+2b+2b(2b-1)/2)$$ or $$T=2^4(1+b(2b+1))|_{b=16}=8464\approx 2^{13.05},$$ which gives attack complexity (via the birthday paradox) of $$2^{(128-13.05)/2}\approx 2^{62.5}$$ for the pairwise XOR of any two outputs of the hash function to be in $$T.$$

However, this is not quite enough, if what you want is to be near a given fixed hash output as opposed to be near any of the outputs so far (so you want a near preimage as opposed to a near collision). If it is the latter, then proceed as below.

The probability that you miss the fixed target for $$k$$ randomly chosen inputs is $$p(f,k)\geq \left(1-\frac{T}{2^n}\right)^k =\left[\left(1-\frac{1}{2^n /T}\right)^{2^n/T}\right]^{Tk/2^n} \sim \exp[-Tk/2^n]$$ which is only a lower bound but accurate for small $$f.$$ The reason we can't proceed as in the birthday paradox writing $$\left(1-\frac{T}{2^n}\right)\left(1-\frac{T+1}{2^n}\right)\cdots\left(1-\frac{T+k-1}{2^n}\right)$$ for the probability is that we may be colliding with a previous hash output but this output may not be in the target set.

If we make the product $$Tk=2^n,$$ then we can have a probability of success of $$1-e^{-1}\approx 0.63$$. Since $$T=2^{13.05},$$ we need to perform no more than (and probably somewhat less than) $$2^{128-13.05}=2^{114.95}$$ hash computations.

If you are happy with larger $$f,$$ then use the dominant term in (1) to obtain $$T\geq 2^4 b(2b-1)\cdots(2b-f+1)$$ for a good approximation to $$T$$ but the direct computation of exact $$T$$ is not hard either.