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

Bondy

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.

Unearthly

So MD5 and SHA-1 are only said to have a collision attack, then, because of the severe constraints on what inputs are currently feasible to find any collisions for? – Terraterrace

Since there are a couple of theoretical and constrained ways of preparing the inputs, the most practical, and dangerous is a so-called 'chosen-prefix collision,' where the attacker can freely choose the prefix for the two colliding messages. Such collisions change everything in terms of threat because you can consider having collisions with meaningful data inside (like names or identities in a digital certificate, etc). You can find details in this article: eprint.iacr.org/2019/459.pdf – Unearthly

Answer 2

You did a lot of research before posting the question. I cannot answer much aside the resources-question. Which is: I use Applied Cryptography be Menezes/Oorschot for almost everything I ever wanted to know on topics of cryptography, including hashes.

Maybe you'll find a copy at your universities library. Good luck.

Skirret

+1, thanks, the chapter on hash functions for the Handbook of Applied Cryptography is available online here cacr.math.uwaterloo.ca/hac – Bondy