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?

$\endgroup$
  • 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 Apr 2 '15 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 Apr 2 '15 at 14:51
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

$\endgroup$
  • $\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 Apr 2 '15 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 Apr 2 '15 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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