Has it become easier to pre-compute tables after MD5 collisions?

Question

Apparently it is not possible to compute all MD5 values from 0x00000000000000000000000000000000 to 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF.

As far as I understand this operation is hard because cryptographic hash functions make it difficult to calculate a message for a given digest (Pre-image resistance).

Storing all MD5 hashes requires $16 * 2^{128}$ Bytes, or $5.44 * 10^{39}$ Bytes, or billions of Yottabytes (1 Yottabyte = $10^{24}$ Bytes). This doesn't yet count the message(s) for each digest. To put this in context: 2011 it was estimated that the world wide storage capacity is "only" 295 Exabytes, ca. 0.0003 Yottabytes.

But MD5's collision resistance is broken. It doesn't take much time to create two different messages with the same hash.

Has the capability to provoke collision attacks in MD5 made it easier to create tables of pre-computed hashvalues?

Answer 1

Not really.

Finding distinct $m_1, m_2$ such that $H(m_1) = H(m_2)$ is a different problem than finding $m_1, d$ such that $H(m_1) = d$. If the first problem is hard it's called collision resistance, if the second problem is hard it's called preimage resistance.

MD5's collision resistance is practically broken - it's quite easy to generate a pair of $m_1, m_2$ that produce the same digest in a few seconds on a consumer CPU. However this result is not useful for creating pre-computed lookup tables at all, the contrary is true - you want as many different digests in such table, rather than collisions.

MD5's preimage resistance is theoretically broken (with a computational complexity $2^{123.4}$ according to Wikipedia), but that's not a practical result. So for example if I know that I still need a digest with value 0xFFFFA3BFFFFFFFFFFFFFFFFFFFFFFFFF in the table there is still no easy way to find an input for that digest.