Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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