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

[Ray Dillinger]

On 10/26/2015 10:42 AM, Zooko Wilcox-OHearn wrote:

>> 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

Oh damn!  I hadn't seen that!  That's important!

And that pretty much wraps it up for ANY USE AT ALL of MD5!  It
is time for it to go to the great bit bucket in the sky.

Thank you, Zooko!

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151026/a34446a9/attachment.sig>