Créez vos propres collisions MD5

Question

Je suis en train de faire une présentation sur les collisions MD5 et j'aimerais donner aux gens une idée de la probabilité d'une collision.

Il serait bon d'avoir deux blocs de texte, qui de hachage à la même chose, et d'expliquer comment de nombreuses combinaisons de [a-zA-Z ] ont été nécessaires avant que j'ai touché une collision.

La réponse évidente est de hachage toutes les combinaisons possibles jusqu'à frapper deux hachages de même. Alors, comment vous y prendriez-vous que ce codage. Comme une expérience rapide, j'ai essayé de hachage chaque combinaison de 5 colonnes de [A-Z], le stockage de ce dans une .filet de table de hachage et d'attraper la collision d'exception. Deux problèmes avec cette - la table de hachage finalement son temps, et je suis sûr que je vais avoir besoin de BEAUCOUP plus de caractères.

Évidemment, cette structure de données est trop grand pour tenir dans la mémoire, donc maintenant je vais avoir à obtenir une base de données concernées. Sonne comme un bon projet pour tester azur - un peu comme ces gars-là.

Quelqu'un peut me pointer dans la direction d'un efficace moyen de faire cela?

Answer 1

Ces deux différentes 128 séquences d'octets de hachage pour la même:

Hachage MD5: 79054025255fb1a26e4bc422aef54eb4

Les différences ci-dessous sont mises en évidence (en gras). Désolé c'est un peu difficile à voir.

d131dd02c5e6eec4693d9a0698aff95c 2fcab5

et

8

La visualisation de la collision/bloc1 (Source: Links.Org)

La visualisation de la collision/bloc2 (Source: Links.Org)

Answer 2

Il est difficile de le faire avec juste les fichiers de texte, autant que je sache. Vous pouvez obtenir quelques collisions, mais aussi de tout [a-zA-Z] n'est pas facile (encore).

D'autre part, si vous voulez juste deux "utile"-à la recherche des fichiers avec le même hash, vous pouvez le faire avec quelque chose comme, disons, PostScript: ont binaires différents gouttes provoquant la collision, et l'utilisation d'une expression conditionnelle pour afficher les différents sortie en conséquence.

Voir, par exemple, ce problème (H2) et de la solution. Par exemple, ce fichier PS et ce un ont le même MD5sum mais ils sont tous les deux bien formé des fichiers PostScript totalement différents de texte en eux lorsque vous les ouvrez.

Answer 3

Si vous parlez de la probabilité qu'une simple collision est un où il n'y a pas de tentative délibérée de causer un - alors vous allez être déçus: Vous avez besoin de générer en moyenne 2^64 plaintexts avant que vous pouvez vous attendre à voir une collision, et c'est beaucoup plus que vous allez être en mesure de le faire dans un délai raisonnable (ou vraiment, même un _un_reasonable) de temps.

Si vous êtes à la recherche pour démontrer la difficulté d'avoir délibérément l'élaboration d'une collision, d'autres réponses ont déjà démontré. La contrainte supplémentaire d'obliger les chaînes à être entièrement textuelle fait même de ces approches, en grande partie impossible, cependant.

Answer 4

Je voudrais prendre un coup d'oeil à Pénalités. Avec un algorithme de hachage, comme md5, le temps de calcul de collision exponentielle avec le nombre de bits. Ce Pénalités n'est calcule partielle des collisions. C'est un match de dire que les 16 bits de poids faible de la valeur de hachage. Pour obtenir les 16 bits de poids faible de match, on aurait du essayer de hachage 2^15 combinaisons différentes en moyenne. Si vous savez combien de temps il faut pour venir avec un 16, 24 ou 32 bits collision, alors vous pouvez facilement calculer le temps pour un plus grand nombre de bits.

Answer 5

L'intérêt de tels hash est que les collisions sont extrêmement improbables. Vous n'allez pas en créer un par hasard: votre machine mourra presque certainement avant d'atteindre votre objectif. L'utilisation d'un hachage disparaîtrait si vous pouviez raisonnablement générer des collisions!