Créer vos propres collisions MD5
je fais 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 hachent à la même chose, et d'expliquer combien de combinaisons de [A-zA-Z ] étaient nécessaires avant que je frappe une collision.
la réponse évidente est hachez chaque combinaison possible jusqu'à ce que deux coups de hache la même. Alors, comment vous y prendriez-vous que ce codage. Comme une expérience rapide j'ai essayé de hashing chaque combinaison de 5 colonnes de [A-Z], stockant ceci dans un hashtable.net et capturant l'exception de collision. Deux problèmes avec cela - le hashtable finalement times out, et je suis assez sûr que je vais avoir besoin de beaucoup plus de personnages.
évidemment, cette structure de données est trop grande pour être gérée en mémoire, donc maintenant je vais devoir faire intervenir une base de donné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 comment faire cela?
5 réponses
ces deux séquences de 128 octets sont identiques:
MD5 Hash: 79054025255fb1a26e4bc422aef54eb4
les différences ci-dessous sont indiquées en caractères gras. Désolé c'est un peu difficile à voir.
d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89 55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0 e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70
et
d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70
La visualisation de la collision/bloc1 (Source: Links.Org)
La visualisation de la collision/bloc2 (Source: Links.Org)
si vous parlez de la probabilité d'une collision simple - une collision où il n'y a pas de tentative délibérée d'en causer une - alors vous allez être déçu: vous aurez besoin de générer en moyenne 2^64 textes clairs avant de pouvoir vous attendre à voir une collision, et c'est beaucoup plus que ce que vous allez pouvoir faire dans un temps raisonnable (ou vraiment, même un _un_reasonable).
si vous cherchez à démontrer la difficulté de créer délibérément une collision, d'autres des réponses ont déjà démontré. La contrainte supplémentaire d'exiger que les chaînes soient entièrement textuelles rend même ces approches largement impraticables.
je voudrais prendre un coup d'oeil à Hashcash. Avec un algorithme de hachage, comme md5, le temps de calcul de collision exponentielle avec le nombre de bits. Ce que Hashcash fait, c'est calculer les collisions partielles. C'est-à-dire, une correspondance de dire les 16 bits inférieurs du hachage. Pour obtenir les 16 bits inférieurs pour correspondre, on devrait essayer le 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 nombre plus élevé de bits.
Il est difficile de le faire avec juste les fichiers de texte, autant que je sache. Vous pouvez obtenir de l' collisions, mais aussi de tout [a-zA-Z] n'est pas facile (encore).
d'un autre côté, si vous voulez juste deux fichiers "significatifs"avec le même hachage, vous pouvez le faire avec quelque chose comme, disons, PostScript: avoir des blobs binaires différents causant la collision, et utiliser une expression conditionnelle pour afficher une sortie différente en conséquence.
voir par exemple ce problème (la partie H2) et solution. Par exemple, ce fichier PS et celui-ci ont le même MD5sum mais ils sont tous les deux des fichiers PostScript bien formés qui ont un texte complètement différent quand vous les ouvrez.
le but de tels coups est que les collisions sont extrêmement peu probables. Vous n'allez pas à générer un par hasard--votre machine sera presque certainement mourir de vieillesse avant de réussir. Le point entier de l'utilisation d'un hachage disparaîtrait si vous pouviez raisonnablement générer des collisions!