Dans quelle mesure les sommes de contrôle sont-elles uniques?

10

J'ai beaucoup de fichiers à trier; et malheureusement, il y a beaucoup de fichiers avec le même nom mais un contenu différent, et il y a le même contenu avec des noms de fichiers différents.

Je pense à utiliser md5sumpour générer des sommes de contrôle pour les fichiers, mais je dois savoir - est-il possible que deux fichiers différents (c'est-à-dire un contenu différent) génèrent la même somme de contrôle?

Si tel est le cas, quelle est la probabilité que cela se produise?

Serait-il possible d'utiliser deux programmes de somme de contrôle non liés (c.-à-d. Ne faisant pas partie de la même "famille") pour générer deux sommes de contrôle - en supposant que, bien que deux fichiers différents puissent générer la même somme de contrôle pour l'un ou l'autre des programmes de somme de contrôle, cela n'arriverait jamais aux deux à la fois?

files checksum Baard Kopperud
la source
2
Rappelez-vous que md5 / sha2 / etc est un HASH de données mappant ainsi beaucoup d'informations sur un espace binaire plus petit, il est donc possible qu'il y ait des collisions. Un HASH n'est pas une clé unique et si tel est votre objectif ... je vous recommande fortement de faire autre chose.
mdpc
Pour trier les fichiers, MD5 est très bien. À partir de crypto.stackexchange.com/a/18337/49945 , la probabilité de collision de sommes de contrôle de deux contenus différents est de 1 sur 2 ^ 128, soit environ 1 sur 10 ^ 43. C'est vraiment, vraiment rare. Si vous effectuez une comparaison par microseconde, vous obtiendrez en moyenne une collision une fois tous les 10 ^ 20 ans. Cela ne fait que ~ 10 ^ 9 ans depuis le Big Bang, donc les chances d'une collision se produisant MÊME UNE FOIS, à une comparaison par microseconde du Big Bang jusqu'à présent, ne sont toujours que de 1 sur 10 ^ 11. Étant donné une centaine de milliards d'ordinateurs simultanés, un seul seulement aurait déjà vu une collision.
ToolmakerSteve
... bien qu'il ne soit pas clair pourquoi vous utiliseriez un algorithme de hachage lors du tri des fichiers. S'il existe des fichiers du même nom, ils doivent être identifiables par d'autres critères; par exemple, il doit y avoir un chemin unique vers le fichier, ou peut-être un décalage d'octet dans un périphérique de stockage? L'un ou l'autre serait un moyen plus utile de se référer uniquement au fichier.
ToolmakerSteve

Réponses:

10

Deux fichiers avec le même contenu mais des noms de fichiers différents: ( fichier1 et fichier2 ):

cat file1
this is a simple file

cat file2
this is a simple file

md5sum file1
7de45bf879db49de7e2eacea23e6c165  file1
md5sum file2
7de45bf879db49de7e2eacea23e6c165  file2

Deux fichiers avec des contenus différents mais les mêmes noms de fichiers: ( fichier1 et fichier1 )

cat file1
this is a simple file
cat file1
this is a simple file with extra contents
md5sum file1 #first file1
7de45bf879db49de7e2eacea23e6c165  file1
md5sum file1 #second file1
c7c8f3fd9ddd7a926c31416a69063e4e  file1

Depuis l' entrée wiki ,

Cependant, il est très peu probable que deux fichiers non identiques dans le monde réel aient le même hachage MD5, sauf s'ils ont été spécifiquement créés pour avoir le même hachage.

Mais, l' algorithme MD5 a ses propres défauts.

Cependant, maintenant qu'il est facile de générer des collisions MD5, il est possible pour la personne qui a créé le fichier de créer un deuxième fichier avec la même somme de contrôle, donc cette technique ne peut pas protéger contre certaines formes de falsification malveillante. De plus, dans certains cas, la somme de contrôle ne peut pas être approuvée (par exemple, si elle a été obtenue sur le même canal que le fichier téléchargé), auquel cas MD5 ne peut fournir qu'une fonctionnalité de vérification des erreurs: il reconnaîtra un téléchargement corrompu ou incomplet, ce qui devient plus probable lors du téléchargement de fichiers plus volumineux.

Je recommanderais d'utiliser sha1 pour calculer la somme de contrôle, car la production de collisions n'est pas si simple lors de l'utilisation d' algorithmes sha1 . La production de la somme de contrôle sha1 est assez facile comme vous pouvez le voir ici .

Ramesh
la source
REMARQUE: la question concerne le tri des fichiers; la recommandation à utiliser sha1n'est pas pertinente pour cette tâche; cela n'a d'importance que pour la sécurité .
ToolmakerSteve