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


Solution: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.


Solution: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.


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »