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](https://en.wikipedia.org/wiki/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](https://link.springer.com/chapter/10.1007/11599371_1)

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](https://www.rambus.com/security/)
* [Cryptographic Hashes](https://web.archive.org/web/20150901084550/http://www.vpnc.org/hash.html)
* [The eHash Main Page](https://ehash.iaik.tugraz.at/wiki/The_eHash_Main_Page)