Quelle est la différence entre une multi-collision et une première ou une deuxième attaque pré-image sur une fonction de hachage?

StackOverflow https://stackoverflow.com/questions/1198900

Question

Quelle est la différence entre un multi-collision dans une fonction de hachage et une première ou une deuxième préimage.

  • Premières attaques de préimage: Étant donné un hachage h, trouvez un message tel que

    hash (m) = h.

  • Deuxième attaques de préimage: Étant donné un message fixe M1, trouvez un message différent m2 tel que

    hash (M2) = hachage (M1).

  • Attaques multi-collisions: générer une série de messages m1, m2, ... mn, tels que

    hash (m1) = hash (m2) = ... = hachage (mn).

Wikipedia nous dit qu'un attaque préimage diffère d'une attaque de collision en ce qu'il y a un hachage ou un message fixe qui est attaqué.

Je suis confus par les articles avec lesquels faire des déclarations comme:

Les techniques sont non seulement efficaces pour rechercher des collisions, mais également applicables pour explorer le second - préimation de MD4. À propos de l'attaque de deuxième-préimation, ils ont montré qu'un message aléatoire était un message faible avec une probabilité 2 ^ –122 et il n'avait besoin qu'un calcul MD4 unique pour trouver la seconde-préimation correspondant au message faible.

L'attaque de deuxième-préimation sur MD4

Si je comprends ce que les auteurs semblent dire, c'est qu'ils ont développé une attaque multi-collision qui englobe un ensemble suffisamment important de messages qui compte tenu d'un message aléatoire, il y a une chance significative mais extrêmement petite, il se chevauche avec l'un de leurs multiples collisions.

J'ai vu des arguments similaires dans de nombreux articles. Ma question quand une attaque cesse d'une attaque multi-collision et de devenir une deuxième attaque préimage.

  • Si une multi-collision entre en collision avec 2 ^ 300 autres messages, cela compte-t-il comme une deuxième préimation, car la multi-collision pourrait être utilisée pour calculer la "pré-image" de l'un des messages avec lesquels il entre en collision? Où est la ligne de division, 2 ^ 60, 2 ^ 100, 2 ^ 1000?

  • Et si vous pouvez générer une préimation de tous les digestions de hachage qui commencent par 23? Certes, il ne répond pas à la définition stricte d'un préimage, mais c'est aussi certainement un défaut sérieux dans la fonction de hachage cryptographique.

  • Si quelqu'un a une grande multi-collision, il pourrait toujours récupérer l'image de n'importe quel message qui est entré en collision avec la multi-collision. Par exemple,

    hash (m1) = hachage (m2) = hachage (m3) = h

    Quelqu'un demande le préimage de H et il répond par M2. Quand cela cesse-t-il d'être idiot et devient une véritable attaque?

Règles de base? Vous connaissez de bonnes ressources sur l'évaluation des attaques de la fonction de hachage?

Liens connexes:

Était-ce utile?

La solution

Il s'agit d'un scénario d'attaque. La différence réside dans le choix de l'entrée. En multi-collision il y a libre choix des deux entrées. Le 2e préimage consiste à trouver une seconde entrée qui a la même sortie que Toute entrée spécifiée.
Lorsqu'une fonction n'a pas de résistance multi-collision, il peut être possible de trouver une collision pour une sorte de messages - pas tous. Cela n'implique donc pas la 2e faiblesse de préimage.

Autres conseils

Vous avez fait beaucoup de recherches avant de poster la question. Je ne peux pas répondre beaucoup de côté la question des ressources. Ce qui est: j'utilise la cryptographie appliquée Be Menezes / Oorschot pour presque tout ce que j'ai jamais voulu savoir sur des sujets de cryptographie, y compris les hachages.

Vous trouverez peut-être une copie dans la bibliothèque de vos universités. Bonne chance.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top