168 votes

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

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. Comme S3 ne peut pas avoir de sous-répertoires, je dois stocker toutes ces images dans un seul dossier plat.

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

Bonus : combien de fichiers puis-je avoir avant de commencer à voir des collisions dans la valeur de hachage que MD5 produit ?

317voto

porneL Points 42805

La probabilité que deux hachages entrent accidentellement en collision est de 1/2 128 qui est 1 sur 340 undecillion 282 decillion 366 nonillion 920 octillion 938 septillion 463 sextillion 463 quintillion 374 quadrillion 607 trillion 431 billion 768 million 211 thousand 456.

Cependant, si vous gardez tous les hashs, alors grâce à paradoxe de l'anniversaire La probabilité est un peu plus élevée. Pour avoir 50% de chance qu'un dièse entre en collision, il faut 2 64 hachages. Cela signifie que pour obtenir une collision, il faut en moyenne hacher 6 milliards d'euros fichiers par seconde depuis 100 ans .

28voto

davr Points 9556

S3 peut avoir des sous-répertoires, vous savez. Il suffit de mettre un / dans le nom de la clé, et vous pouvez accéder aux fichiers comme s'ils étaient dans des répertoires séparés. Je l'utilise pour stocker les fichiers des utilisateurs dans des dossiers distincts en fonction de leur ID d'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 de S3 possède certaines fonctionnalités qui permettent un fonctionnement presque identique. Je peux lui demander de lister tous les fichiers qui commencent par "users/1234/" et il me montrera tous les fichiers de ce "répertoire".

19voto

Ryan Points 7035

Alors attends, c'est ça :

md5(nom du fichier) + horodatage

ou :

md5(nom du fichier + horodatage)

Si c'est le cas, vous avez déjà fait la majeure partie du chemin vers un GUID et je ne m'en préoccuperais pas. Dans le second cas, consultez le post de Karg qui explique que vous finirez par rencontrer des collisions.

10voto

Will Dean Points 25866

Une règle empirique approximative pour les collisions est la racine carrée de la plage de valeurs. Votre sig MD5 est vraisemblablement long de 128 bits, donc vous allez probablement voir des collisions au-dessus et au-delà de 2^64 images.

7voto

bdonlan Points 90068

Bien que les collisions MD5 aléatoires soient extrêmement rares, si vos utilisateurs peuvent fournir des fichiers (qui seront stockés mot pour mot), ils peuvent provoquer des collisions. Autrement dit, ils peuvent délibérément créer deux fichiers ayant la même somme MD5 mais des données différentes. Assurez-vous que votre application peut gérer ce cas de manière sensée, ou peut-être utiliser un hachage plus fort comme SHA-256.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X