[cryptography] philosophical question about strengths and attacks at impossible levels

Zooko O'Whielacronx zooko at zooko.com
Thu Oct 14 22:36:44 EDT 2010

Oh, and now I need to follow-up to my follow-up to correct an

On Thu, Oct 14, 2010 at 8:33 PM, Zooko O'Whielacronx <zooko at zooko.com> wrote:
> I know that collision resistance
> is approximately as difficult to achieve as the square of pre-image
> resistance is.

Actually the above is true only for an *ideal* hash function. All real
hash functions that have been widely deployed so far have been
revealed as very different from the ideal hash function, and in fact
every one has shown that collision resistance is much harder to
achieve than pre-image resistance:

MD5: collisions: seconds on your laptop; pre-images: perhaps in a
hundred years if we make more progress [1]

SHA-1: collisions: a year or two of great expense and effort;
pre-images: perhaps never unless we have a breakthrough

an ideal hash function with a 256-bit output: collisions: 2¹²⁸; pre-images: 2²⁵⁶


Zooko Wilcox-O'Hearn

[1] http://www.springerlink.com/content/d7pm142n58853467/

More information about the cryptography mailing list