J'ai un client qui distribue de grands fichiers binaires en interne. Ils passent également des checksums MD5 des fichiers et vérifient apparemment les fichiers contre la somme de contrôle avant utilisation dans le cadre de leur flux de travail.
Cependant, ils prétendent que "souvent" ils rencontrent la corruption dans les fichiers où le MD5 disent toujours que le fichier est bon.
Tout ce que j'ai lu suggère que cela devrait être énormément improbable.
Cela sonne-t-il probable? Un autre algorithme de hachage permettrait-il de meilleurs résultats? Devrais-je réellement examiner des problèmes de processus tels que ceux qui prétendent vérifier la somme de contrôle, mais pas vraiment le faire?
NB, je ne sais pas encore ce que "souvent" signifie dans ce contexte. Ils traitent des centaines de fichiers par jour. Je ne sais pas s'il s'agit d'une occurrence quotidienne, mensuelle ou annuelle.
6 Réponses :
MD5 est une fonction de hachage cryptographique 128 bits, de sorte que différents messages doivent être assez bien distribués sur l'espace 128 bits. Cela signifierait que deux fichiers (à l'exclusion des fichiers spécialement conçus pour vaincre MD5) devraient avoir une chance de collision 1 sur 2 ^ 128. En d'autres termes, si une paire de fichiers est comparé à chaque nanoseconde, cela ne serait pas arrivé.
Eh bien, vous savez que cela s'est déjà arrêté, n'est-ce pas? Bien sûr, ces collisions ont été provoquées (on essayait de faire deux fichiers différents qui ont la même somme de contrôle MD5), mais cela ne change pas le fait qu'il y a plusieurs fichiers connus de l'humanité (et ceux-ci sont également à l'état sauvage) que produire exactement la même somme de contrôle MD5, même s'ils contiennent des données totalement différentes.
@Mecki: Avez-vous lu la partie où j'ai dit "(à l'exclusion des fichiers spécialement conçus pour vaincre MD5)"?
Mais vous n'avez jamais de deux fichiers, vous avez un ensemble de fichiers et vous n'en voulez pas deux à un hachage de la même valeur. La probabilité est supposée être sqrt (2 ^ 128) qui est 2 ^ 64. Vous pouvez stocker environ 4,3 milliards de fichiers si vous avez utilisé un hachage de 64 bits, ou 280 trillions de fichiers avec la servage de MD5. Lorsque vous avez atteint 2 ^ 128 fichiers, vous êtes assuré que votre fichier suivant entrera en collision, si vous avez réussi à éviter les collisions à ce point; que vous ne pouvez pas avoir, pratiquement.
C'est vrai à cause du "paradoxe d'anniversaire". Néanmoins, personne n'a suffisamment de documents pour rendre plausible qu'ils avaient accidentellement une collision. Personne n'a 100 billions de documents.
Je pense qu'il ne parle pas de collisions, mais quelque chose qui semble encore plus peu probable. Une corruption dans le contenu du fichier et en même temps une corruption dans le hachage lui-même pour que les deux choses correspondent.
Si un fichier est corrompu, la probabilité que le fichier corrompu a la même somme de contrôle MD5 que le fichier non corrompu est 1: 2 ^ 128. En d'autres termes, cela arrivera presque comme "souvent" comme jamais. Il est d'astronomie plus probable que votre client aime mal ce qui s'est vraiment produit (comme s'ils contrôlent le mauvais hash)
sonne comme un bogue dans leur utilisation de MD5 (peut-être qu'ils sont MD5-ing les mauvais fichiers) ou un bogue dans la bibliothèque qu'ils utilisent. Par exemple, un programme plus ancien MD5 que j'ai utilisé une fois, ne gérait pas de fichiers sur 2 Go.
Cette question suggère que, en moyenne, vous Obtenez une collision en moyenne tous les 100 ans si vous génériez 6 milliards de fichiers par seconde, il est donc assez improbable.
Est-ce que cela sonne probablement?
Non, le risque d'une corruption aléatoire causant la même somme de contrôle est
1 in 2 128 ou 3,40 × 10 38 . Ce numéro met 1 sur un milliard (10 9 ) à honte. Un autre algorithme de hachage offrirait de meilleurs résultats?
Probablement pas. Alors que MD5 a été cassé pour la résistance à la collision contre l'attaque, c'est une bonne contre la corruption aléatoire et une norme populaire à utiliser.
Devrais-je réellement regarder des problèmes de processus tels que ceux qui prétendent vérifier la somme de contrôle, mais pas vraiment le faire?
Probablement, mais considérons tous les points possibles de problèmes:
- fichier corrompu avant la génération MD5
- fichier corrompu après la vérification MD5.
- programme MD5 ou cadre de support a un bug
- Mauvais usage de l'opérateur (non intentionnel, E.G. exécutant le programme MD5 sur le mauvais fichier)
- Abus de l'opérateur (intentionnel, par ex. sauter l'étape de vérification)
Si c'est le dernier, une seule pensée finale consiste à distribuer les fichiers d'un format de wrapper qui oblige l'opérateur à déballer le fichier, mais le débit automatique effectue une vérification pendant l'extraction. Je pense à quelque chose comme Gzip ou 7-Zip qui prend en charge les gros dossiers et éventuellement éteindre la compression (je ne sais pas que celles-ci).
Il y a toutes sortes de raisons pour lesquelles les fichiers binaires ne seront pas distribués ou si elles le font, il existe une corruption (pare-feu, limitation de la taille, insertions de virus, etc.). Vous devez toujours chiffrer des fichiers (même un cryptage de bas niveau est meilleur que rien) lors de l'envoi de fichiers binaires pour protéger l'intégrité des données.
ne pouvait pas résister à un calcul de l'enveloppe:
Il y a 2 ^ 128 Possible MD5 hachage ou c. 3.4 x 10 ^ 38 (c'est-à-dire que 340 milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards d'euros). Permet d'appeler ce numéro 'm'
La probabilité de la match de hachage KTH si les matchs de 1 à (k-1) TH ne sont pas (1- (k-1) / m) car nous avons déjà des hachages uniques de la K-1 de M. < / p>
et p (pas de duplicate dans N hachage de fichier) = Produit [K = 1 ... N] (1- (k-1) / m). Quand n ^ 2 <<< m, alors cela se rapproche de 1 - 1/2 N ^ 2 / m et P (un ou plusieurs doublons) = 1/2 N ^ 2 / m lorsque 1/2 N ^ 2 est une approximation à Le nombre de matches de paires de hachages qui doivent être fabriqués
permet de dire que nous prenons une photo de chacun sur la planète (7,8 milliards, ou un peu moins de 2 ^ 33), il y a 30,4 milliards de milliards de milliards de milliards de comparaisons par paire à faire (un peu moins de 2 ^ 65).
Cela signifie que les chances d'un hachage MD5 correspondant (supposer parfaitement une distribution) sont toujours 2 ^ 65/2 ^ 128 = 2 ^ -63 ou 1 sur 10 000 000 000 000 000 000.
MD5 est une fonction de hachage assez décente pour les environnements non hostiles, ce qui signifie que les chances de vos clients ayant un faux match sont beaucoup moins susceptibles que de dire que leur PDG soit folle et brûle le centre de données, sans parler du truc ils s'inquiètent effectivement.
Demandez-leur de fournir un exemple de fichier "corrompu" et le "bon" original.
Est-il possible que la somme MD5 ait été calculée sur un fichier corrompu ou que la corruption se produise après la calcul de la somme? Savoir bien sûr, prenez la suggestion d'Anon et obtenez un exemple de deux fichiers avec le même checksum.
Donc, depuis lors, avez-vous regardé l'idée de synchronisation BitTorrent? getsync.com]