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: