Pourquoi une détection de collision dans une fonction de hachage cryptographique facilite-t-elle la recherche d'autres collisions?

Un article de Wikipédia, je lis:Pourquoi une détection de collision dans une fonction de hachage cryptographique facilite-t-elle la recherche d'autres collisions?

Joux [3] a noté que le 2-collisions conduisent à n-collisions: s'il est possible de trouver deux messages avec le même hachage MD5, il est effectivement plus difficile pour trouver autant de messages que l'attaquant désire avec des hachages MD5 identiques.

Mais pourquoi est-ce ainsi? Je ne peux pas imaginer pourquoi? Les algorithmes sont ouverts à droite, les gens peuvent lire les maths qui génèrent les hachages, qui sont les machines de digestion. Donc, si nous connaissons une collision, pourquoi aide-t-elle à en trouver de nouvelles?

Effectue-t-il simplement de petites itérations sur les deux premiers messages de collision, puis surveille leurs modifications pour les réorganiser?

Source

2010-10-25 Vass

Bonne question, mais malheureusement pas de programmation liée. –

trouver les autres collisions nécessitera une programmation ... – Vass

Cela n'est pas une propriété de toutes les fonctions de hachage, mais une faiblesse du Merkle–Damgård construction (qui MD5 et SHA-1 sont basées sur), connu sous le nom extension de longueur. La faiblesse implique le fait que vous pouvez "reprendre" le calcul de hachage avec des données ajoutées spécialement sélectionnées. Pour plus de détails sur la façon dont il est utilisé pour générer de façon arbitraire de collisions, voir:

Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions (Antoine Joux)

Pour une attaque liée basée sur cette idée, voir:

Source

2010-10-25 17:23:16

Alors que les extensions de longueur sont liées, il s'agit d'une faiblesse distincte. En particulier, une fonction de hachage peut avoir cette propriété sans être vulnérable aux extensions de longueur. Par exemple, lorsque vous trouvez une collision de même longueur dans Skein-512-512, cela implique une collision d'état et permet ainsi des collisions multiples. Pour les autres fonctions de hachage, une collision en sortie n'implique pas une collision d'état, mais une collision d'état implique toujours des collisions multiples. – CodesInChaos

Je pense que la clé ici est le mot "faisable". En crypto-land, cela signifie «temps raisonnable comparé à la valeur de ce que j'essaie de briser», ou peut-être «moins de temps qu'il faudrait pour utiliser la force brute» selon la façon dont vous regardez les choses. Donc, si je peux trouver 1 collision faisable, alors je peux trouver n collisions possible parce que n*small est encore petit.

Il y aura toujours certains n où n*small > value of breakage.

Est-ce que cela s'appliquerait à d'autres fonctions de hachage? Je le crois, mais je peux me tromper.

Laisser la flamme commencer.

Source

2010-10-25 17:13:27

Si vous connaissez une collision MD5 (de messages de même longueur), trouver plus de collisions connexes est extrêmement bon marché/beaucoup moins cher que de trouver cette première collision. Ajoutez simplement la même chaîne à tous les deux, et c'est toujours une collision. – CodesInChaos

Pourquoi une détection de collision dans une fonction de hachage cryptographique facilite-t-elle la recherche d'autres collisions?

Répondre

Questions connexes