0
$\begingroup$

I have an MD5 hash and need to generate a file that matches it.

There are absolutely no constrains on the contents of said file, it can be binary gibberish. The only important thing is that it matches the hash.

Is this possible?

I have the original file that produces the hash, but the new file is not allowed to be "visually identical", so appending bytes isn't allowed.

$\endgroup$
1

2 Answers 2

2
$\begingroup$

In general, no. For MD5, we know a cheap way of finding collisions, i.e. finding two files F1 and F2 such that F1≠F2 MD5(F1) = MD5(F2). Even better, we know how to find collisions with a known prefix: given a prefix P, we know a cheap way of finding M1 and M2 such that M1≠M2 and MD5(P+M1) = MD5(P + M2). More generally, because the collision is in the compression function, i.e. in the part of the calculation that updates the state by incrementally processing the input, MD5(P+M1+S) = MD5(P+M2+S) for any suffix S. However, this attack does not let you choose M1 or M2: they'll be some arbitrary gibberish. In particular, given M1, in general, there's no way (other than brute force) to find M2 such that MD5(P+M1) = MD5(P+M2). That's true even with an empty prefix: given M1, in general, there's no practical way to find M2 such that M1≠M2 and MD5(M1) = MD5(M2).

However, if you've been given this task, it's possible that you've been given a file that was specifically constructed by this collision attack, i.e. you've been given F1 = P+M1+S which was constructed by choosing a known prefix P, constructing a collision (M1,M2) and appending a suffix S. You can detect this by attempting the collision attack at each position in F1 and seeing if you come up with M1. This can be sped up by analyzing the state of the MD5 calculation at each position to see if it has reached a “weak” state which can be reached in multiple ways: that state would be the colliding state where MD5(P+M1) = MD5(P+M2). For SHA-1, this is what Marc Stevens's sha1collisiondetection does. I don't know of a similar tool for MD5.

$\endgroup$
1
  • 2
    $\begingroup$ Even more generally, given $P_1, P_2$, we can find $M_1, M_2$ such that $MD5(P_1+M_1+S) = MD5(P_2+M_2+S)$; that is, the collisions can have different prefixes. $\endgroup$
    – poncho
    Feb 12 at 4:45
0
$\begingroup$

Is this possible?

This is known as the 'second preimage' problem. Alas, there are no known methods to do it against MD5 that are more efficient than brute force (which, at an expected $2^{128}$ MD5 compression function evaluations, is infeasible).

$\endgroup$

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