Est-il possible de créer un fichier falsifié qui a les mêmes sommes de contrôle en utilisant deux algorithmes différents?

Question

J'étais un peu inspiré par cette entrée de blog http://blogs.technet.com/dmelanchthon/archive/2009/07/23/windows-7-rtm.aspx (allemand)

La notion actuelle est que md5 et sha1 sont tous deux quelque peu cassés. Pas facilement et rapidement, mais au moins pour MD5 dans la gamme d'une possibilité pratique. (Je ne suis pas du tout un expert en cryptographie, alors peut-être que je me trompe dans ce genre de choses).

Alors je me suis demandé s'il serait possible de créer un fichier A » qui a comme fichier d'origine même taille, la même somme md5 et la même somme SHA1 A.

D'abord, serait-ce possible? Deuxièmement, serait-il possible dans la réalité, avec le matériel/logiciel actuel? Si ce n'est pas le cas, ne serait-ce pas le moyen le plus simple de garantir l'intégrité d'un fichier en utilisant toujours deux algorithmes différents, même s'ils présentent une sorte de faiblesse?

Mise à jour:

Juste pour clarifier: l'idée est d'avoir un fichier A et un fichier A » qui fullfills les conditions:

size(A) == size(A') && md5sum(A) == md5sum(A') && sha1sum(A) == sha1sum(A')

Answer 1

"Serait-ce possible?" - oui, si la taille totale des sommes de contrôle est inférieure à la taille totale du fichier, il est impossible d'éviter les collisions.

"serait-il possible dans la réalité, avec le matériel/logiciel actuel?" - s'il est possible de construire un texte correspondant à une somme de contrôle donnée pour chacune des sommes de contrôle utilisées, alors oui.

Voir wikipedia on concatenation of cryptographic hash functions, qui est également un terme utile pour google pour.

À partir de cette page:.

« Cependant, pour les fonctions de hachage Merkle-Damgard , la fonction concaténée est aussi forte que le meilleur élément , pas plus fort de Joux a noté que 2-collisions plomb à n-collisions: s'il est possible de trouver deux messages avec le même hachage MD5 , il est effectivement plus difficile de trouver autant de messages que l'attaquant désire avec identiques hashes md5 Parmi les. n messages avec le même hachage MD5, il est probable que soit une collision dans SHA-1. Le travail supplémentaire nécessaire pour trouver la collision SHA-1 (au-delà de la recherche d'anniversaire exponentielle ) est polynomiale. Cet argument est résumé par Finney."

Answer 2

En théorie, vous pouvez le faire. En pratique, si vous avez démarré à partir des deux checksums fournis par MD5 et SHA1 et que vous avez essayé de créer un fichier produisant les mêmes deux checksums, cela serait très difficile (beaucoup plus difficile que de créer un fichier MD5 SHA1 somme de contrôle isolée).

Answer 3

Alors je me suis demandé si ce serait possible de créer un fichier A » qui a la même taille, la même somme md5, et la même somme SHA1 que le fichier original A.

Oui, faites une copie du fichier.

Autre que cela, non sans de grandes quantités de ressources informatiques pour vérifier des tonnes de permutations (en supposant que la taille du fichier est non trivial).

Vous pouvez penser comme ceci:

Si la taille du fichier augmente de n, la probabilité d'un faux possibles augmente, mais les coûts informatiques nécessaires pour tester les combinaisons augmente de façon exponentielle par 2^n.

Plus votre fichier est gros, plus il y a de chances qu'il y ait un dupe, mais moins vous êtes susceptible de le trouver.

Answer 4

En théorie oui vous pouvez l'avoir, en pratique c'est une sacrée connivence. En pratique, personne n'est capable de créer une collusion SHA1 et encore moins MD5 + SHA1 + Size en même temps. Cette combinaison est tout simplement impossible en ce moment sans avoir toute la puissance de l'ordinateur dans le monde et l'exécuter pendant un certain temps.

Bien que dans un proche avenir, nous pourrions voir plus de vulnérabilités dans SHA1 et MD5. Et avec le support d'un meilleur matériel (surtout GPU) pourquoi pas.

Answer 5

Pour une réponse naïve, nous aurions faire quelques hypothèses (incorrectes):

• Les deux SHA1 et les algorithmes de hachage MD5 résultat dans une répartition uniforme des valeurs de hachage pour un ensemble d'entrées aléatoires
• algorithme détails de côté - une chaîne de caractères d'entrée a une chance aléatoire également susceptible de produire une valeur de hachage

(fondamentalement, aucune agglutination et des domaines bien distribué.)

Si la probabilité de découvrir une chaîne qui entre en collision avec le hachage SHA1 d'un autre est p1, et de même p2 pour MD5, la réponse naïve est la probabilité de trouver un qui entre en collision avec les deux est p1 * p2.

Cependant, les hachages sont tous deux cassés, donc nous savons que nos hypothèses sont fausses.

Les hachages ont des agglutinations, sont plus sensibles aux changements avec certaines données que d'autres et, en d'autres termes, ne sont pas parfaits. D'autre part, un algorithme de hachage parfait et non brisé aura les propriétés ci-dessus, et c'est exactement ce qui rend difficile la recherche de collisions. Ils sont aléatoires.

La probabilité dépend intrinsèquement des propriétés de l'algorithme - fondamentalement, puisque nos suppositions ne sont pas valides, nous ne pouvons pas déterminer «facilement» à quel point il est difficile. En fait, la difficulté de trouver une entrée qui entre en collision dépend probablement très fortement des caractéristiques de la chaîne d'entrée elle-même. Certains peuvent être relativement faciles (mais encore probablement peu pratiques sur le matériel d'aujourd'hui), et en raison de la nature différente des deux algorithmes, certains peuvent en fait être impossible.