Combien d'éléments aléatoires avant que MD5 produise des collisions?

Question

J'ai une bibliothèque d'images sur Amazon S3. Pour chaque image, je md5 l'URL source sur mon serveur plus un horodatage pour obtenir un nom de fichier unique. Étant donné que S3 ne peut pas avoir de sous-répertoires, je dois stocker toutes ces images dans un seul dossier.

Dois-je m'inquiéter des collisions dans la valeur de hachage MD5 produite?

Bonus: combien de fichiers puis-je avoir avant de commencer à voir des collisions dans la valeur de hachage générée par MD5?

Answer 1

La probabilité d'une collision accidentelle de deux hachages est 1/2 ¹²⁸ qui correspond à 1 sur 340 undecillion 282 décillions 366 milliards en 920 octillions 938 septillions 463 sextillions 463 milliards de 374 quadrillions 607 milliards de milliards 431 milliards 761 millions 768 millions 211 000 456.

Cependant, si vous conservez tous les hachages, la probabilité est un peu plus élevée grâce au paradoxe de l'anniversaire . . Pour que 50% des chances qu'un hachage entre en collision avec un autre, vous avez besoin des 2 ⁶⁴ hachages. Cela signifie que pour obtenir une collision, vous devez en moyenne hacher 6 milliards de fichiers par seconde sur 100 ans .

Answer 2

S3 peut avoir des sous-répertoires. Il suffit de mettre un " / " dans le nom de la clé, et vous pouvez accéder aux fichiers comme s’ils se trouvaient dans des répertoires distincts. J'utilise cela pour stocker les fichiers utilisateur dans des dossiers distincts en fonction de leur ID utilisateur dans S3.

Par exemple: "mybucket / users / 1234 / somefile.jpg". Ce n'est pas exactement la même chose qu'un répertoire dans un système de fichiers, mais l'API S3 possède certaines fonctionnalités qui lui permettent de fonctionner presque de la même manière. Je peux lui demander de répertorier tous les fichiers commençant par "utilisateurs" / 1234 / " et il me montrera tous les fichiers de ce "répertoire".

Answer 3

Alors attendez, est-ce:

md5(filename) + timestamp

ou:

md5(filename + timestamp)

Si l'ancien, vous êtes en grande partie à un GUID, et je ne m'inquiéterais pas à ce sujet. Dans ce dernier cas, consultez le message de Karg sur la manière dont vous allez éventuellement tomber dans une collision.

Answer 4

Une règle approximative pour les collisions est la racine carrée de la plage de valeurs. Votre signature MD5 a vraisemblablement une longueur de 128 bits. Il est donc probable que des collisions se produisent au-dessus et au-delà de 2 ^ 64 images.

Answer 5

Bien que les collisions MD5 aléatoires soient extrêmement rares, si vos utilisateurs peuvent fournir des fichiers (qui seront stockés in extenso), ils peuvent en assurer l’organisation. C'est-à-dire qu'ils peuvent créer délibérément deux fichiers avec le même MD5sum mais des données différentes. Assurez-vous que votre application peut gérer ce cas de manière judicieuse, ou utilisez peut-être un hachage plus fort tel que SHA-256.

Answer 6

Bien qu'il y ait eu des problèmes bien connus avec MD5 en raison de collisions, les collisions NON INTENTIONNELLES entre données aléatoires sont extrêmement rare . Par contre, si vous faites un hachage sur le nom du fichier, il ne s’agit pas de données aléatoires, et j’attendrais des collisions rapidement.

Answer 7

Une collision MD5 est extrêmement improbable. Si vous disposez de 9 trillions de MD5, il n'y a qu'une chance sur 9 trillions qu'il y ait une collision.

Answer 8

Peu importe sa probabilité; c'est possible. Cela peut se produire sur les deux premières choses que vous hachurez (très peu probable, mais possible), vous devrez donc supporter les collisions dès le début.