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

[Ray Dillinger]

On 10/20/2015 12:36 AM, Tom Mitchell wrote:

> Child pornography raises hackles quickly still the interesting legal issues
> involve
> trafficking and many many files, not the handful of  images in grandmas
> iPhone.
> 
> This simplifies the problem because it is darn hard to generate a hundred
> different files (a set) that have a hash collision with a hundred other
> files.

This is true, but expressed in a way that's ambiguous enough
that someone who doesn't already know what you're saying could
take the wrong impression of it.

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.

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.

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.

Multicollision resistance is not usually interesting because
we're usually only interested in whether or not collision resistance
is strong.  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.

				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/20151021/9a207295/attachment.sig>