What is the difference between a multi-collision and a first or second pre-image attack on a hash function?

Question

What is the difference between a multi-collision in a hash function and a first or second preimage.

• First preimage attacks: given a hash h, find a message m such that

  hash(m) = h.

• Second preimage attacks: given a fixed message m1, find a different message m2 such that

  hash(m2) = hash(m1).

• Multi-collision attacks: generate a series of messages m1, m2, ... mN, such that

  hash(m1) = hash(m2) = ... = hash(mN).

Wikipedia tells us that a preimage attack differs from a collision attack in that there is a fixed hash or message that is being attacked.

I am confused by papers with which make statements like :

The techniques are not only efficient to search for collisions, but also applicable to explore the second- preimage of MD4. About the second-preimage attack, they showed that a random message was a weak message with probability 2^–122 and it only needed a one-time MD4 computation to find the second-preimage corresponding to the weak message.

The Second-Preimage Attack on MD4

If I understand what the authors seem to be saying is that they have developed a multi-collision attack which encompasses a large enough set of messages that given a random message there is a significant though extremely small chance it will overlap with one of their multi-collisions.

I seen similar arguments in many papers. My question when does an attack stop being a multi-collision attack and become a second preimage attack..

• If a multi-collision collides with 2^300 other messages does that count as a second preimage, since the multi-collision could be used to calculate the "pre-image" of one of the messages it collides with? Where is the dividing line, 2^60, 2^100, 2^1000?

• What if you can generate a preimage of all hash digests that begin with 23? Certainly it doesn't meet the strict definition of a preimage, but it is also very certainly a serious flaw in the cryptographic hash function.

• If someone has a large multi-collision, then they could always recover the image of the any message which hash collided with the multi-collision. For instance,

  hash(m1) = hash(m2) = hash(m3) = h

Someone requests the preimage of h, and they respond with m2. When does this stop being silly and becomes a real attack?

Rules of thumb? Know of any good resources on evaluating hash function attacks?

Related Links:

• HASH COLLISION Q&A
• Cryptographic Hashes
• The eHash Main Page

Answer 1

It is about an attack scenario. The difference lies in the choice of input. In multi-collision there is free choice of both inputs. 2nd preimage is about finding any second input which has the same output as any specified input.
When a function doesn't have multi-collision resistance, it may be possible to find collision for some kind of messages - not all of them. So this doesn't imply 2nd preimage weakness.