[Cryptography] How does the size of a set of target results influence the complexity of a preimage attack?

Zooko Wilcox-OHearn zooko at leastauthority.com
Mon Oct 26 13:42:05 EDT 2015


Sorry, Bear, I think you got a couple of things wrong:

On Wed, Oct 21, 2015 at 10:27 PM, Ray Dillinger <bear at sonic.net> wrote:
>
> Clarification:  MD5 now lacks strong collision resistance.  It
> is feasible to generate a pair of files, or a pair of sets of
> 100 files, that have the same hash.

Right!

> MD5 still has weak collision resistance. Meaning, given a file
> or set of files whose creation you don't get to control, it is
> still difficult to generate a different file or set of files
> that has a matching hash.

This isn't called "weak collision resistance", this is called "second
pre-image resistance". You're right that MD5 is still thought to have
this.

> There is a third category of collision resistance that we
> don't usually talk about, but when we do the name "multicollision
> resistance" is often used.
>
> A hash algorithm has multicollision resistance for as long as
> it is hard to generate sets of MORE than two files (or sets of
> files) that have the same hash.  As it happens MD5 lacks strong
> collision resistance but still has multicollision resistance,
> meaning it's not feasible to generate a set of three files (or
> 100) that all have the same hash.

No, MD5 doesn't have resistance against this. The basic Joux
multicollision attack works against MD5:
https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf
here's a student research paper saying that the author implemented
this and benchmarked it:
http://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/knopf-sa.pdf

> Multicollision resistance, like weak collision
> resistance, is automatically satisfied when functions have
> strong collision resistance, and we don't really usually care
> whether "weak" collision resistance includes multicollision
> resistance or not.

Yes!

And I'd like to say unequivocally that trying to figure out how to use
MD5 safely is a fool's errand, and we've seen it blow up in people's
faces time and time again (e.g. ¹). Now that we have BLAKE2
(https://blake2.net), which is secure *and* is faster than MD5 (at
least in most uses), there is absolutely no reason to use MD5 for
anything, and anybody who voluntarily does so should be regarded as
either ignorant, or as the sort of engineer who takes unnecessary
risks.

Regards,

Zooko

¹ http://www.win.tue.nl/hashclash/rogue-ca/


More information about the cryptography mailing list