7

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:

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
Ethan Heilman
  • 16,347
  • 11
  • 61
  • 88

2 Answers2

2

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.

zacheusz
  • 8,750
  • 3
  • 36
  • 60
  • 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? – JamesTheAwesomeDude May 10 '21 at 17:01
  • 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: https://eprint.iacr.org/2019/459.pdf – zacheusz Jul 06 '21 at 08:16
0

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.

Don Johe
  • 989
  • 2
  • 12
  • 24
  • +1, thanks, the chapter on hash functions for the Handbook of Applied Cryptography is available online here http://www.cacr.math.uwaterloo.ca/hac/ – Ethan Heilman Aug 04 '09 at 18:55