2
$\begingroup$

By my math, if you are inputting all possible 17 byte values, and the output is 16 bytes long, then there must always be 256 possible inputs that will result in each output hashsum. However, looking at some rainbow tables, it seems that either this isn't the case, or (more likely) the rainbow tables were incomplete. But, some of the other research I've done says that the smallest known MD5 collision happens well beyond 17 bytes in length.

How can this be possible?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Your assumptions seem to be wrong. There are $256$ preimages of length $17$ (bytes) for each hash value on average. Of course, this implies that there are lots of collisions of length $17$, it is just that none have been found so far due to lack of computing power: The cryptanalytic, efficient attacks on MD5 can only be used to obtain full-block collisions. $\endgroup$
    – yyyyyyy
    Commented Apr 2, 2015 at 14:21
  • $\begingroup$ Concerning rainbow tables 1) they're much smaller than all 17 byte inputs. 2) Probably below to 8 bytes or 13 lowercase letters. 3) Even for the target range, they typically only contain most but not all values. $\endgroup$
    – CodesInChaos
    Commented Apr 2, 2015 at 14:51

1 Answer 1

Reset to default
5
$\begingroup$

Your math is wrong — not the numerical calculation, but your interpretation of it. There are $256^{17}$ possible inputs and $256^{16}$ possible outputs. On average, there are $256$ inputs for each output. But there are no guarantees that this is the case for all outputs: it's in fact overwhelmingly likely that some outputs have more and others have fewer. For example, we don't even know whether every possible output is in fact the MD5 of a message of any length.

What you can state for sure is that there exists at least one 256-bit string $H$ such that there are at least 256 17-byte messages $M_{1}, \ldots, M_{256}$ such that for all $i$, $\mathrm{MD5}(M_i) = H$. Since we don't know any MD5 collision with a 17-byte output, we are unable to come up with an actual value for $M_i$ or $H$, we just know that it exists by the pigeonhole principle.

See also

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think this answered my question. I guess I had just thought that someone would have found two 17-byte strings that collided by now, even though the input space is very large. $\endgroup$
    – coder543
    Commented Apr 2, 2015 at 15:25
  • 1
    $\begingroup$ @coder543 The whole bitcoin miner network computes around $2^{80}$ SHA256d hashes per year (burning several hundred million USD on hardware and electricity). While MD5 is a slightly cheaper than that, it'd still take it several trillion years to compute $2^{128}$ MD5 hashes. $\endgroup$
    – CodesInChaos
    Commented Apr 2, 2015 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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