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

164

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 pourrais-je avoir avant de commencer à voir des collisions dans la valeur de hachage produite par MD5?

random md5 hash Ben Throop
la source
1
Connexes: existe-t-il deux chaînes connues qui ont la même valeur de hachage MD5?
kenorb
2
La réponse littérale est que le deuxième fichier pourrait avoir le même MD5 que le premier. Cependant, les chances sont extrêmement faibles.
Rick James

Réponses:

309

La probabilité que seulement deux hachages entrent en collision accidentellement est de 1/2 128, soit 1 sur 340 undecillion 282 decillion 366 nonillion 920 octillion 938 septillion 463 sextillion 463 quintillion 374 quadrillion 607 billion 431 milliards 768 millions 211 mille 456.

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

Kornel
la source
20
"la probabilité de collision est 1/2 ^ 64" - quoi? La probabilité de collision dépend du nombre d'éléments déjà hachés, ce n'est pas un nombre fixe. En fait, il est égal à exactement 1 - sPn/s^n, où sest la taille de l'espace de recherche ( 2^128dans ce cas) et nest le nombre d'éléments hachés. Ce à quoi vous pensez probablement 2^64, c'est le nombre approximatif d'éléments dont vous auriez besoin pour le hachage MD5 pour avoir 50% de chances de collision.
BlueRaja - Danny Pflughoeft
19
+1 parce que j'ai toujours voulu savoir comment compter au-delà de 999 billions de lol (et oh ouais votre réponse était informative)
Kmeixner
7
Malheureusement, vous n’avez toujours pas raison. Vous supposez que la fonction de hachage est vraiment aléatoire. Ce n'est pas. Cela signifie que la probabilité de collision est plus élevée.
Jørgen Fogh
22
JørgenFogh: Et toutes les lois de la physique ne sont "pas correctes" non plus. Un tel niveau de pédantisme n'est pas nécessaire car il ne change pas la réponse de manière significative.
Kornel
21
Alors vous dites qu'il y a une chance!
vargonian
27

S3 peut avoir des sous-répertoires. Mettez simplement un "/" dans le nom de la clé, et vous pouvez accéder aux fichiers comme s'ils se trouvaient dans des répertoires séparés. J'utilise ceci pour stocker les fichiers utilisateur dans des dossiers séparés 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 lister tous les fichiers qui commencent par "users / 1234 /" et il me montrera tous les fichiers de ce "répertoire".

Davr
la source
7
Cela devrait être un contenu que je pense, car il ne répond pas réellement à la question sur la probabilité d'une collision
Ian Clark
18

Alors attendez, est-ce:

md5(filename) + timestamp

ou:

md5(filename + timestamp)

Si c'est le premier, vous êtes presque entièrement sur le chemin d'un GUID, et je ne m'en soucierais pas. Si c'est le cas, consultez l'article de Karg sur la façon dont vous allez éventuellement rencontrer des collisions.

Ryan
la source
1
Veuillez expliquer en quoi l'inclusion de l'horodatage augmente le risque de collision
Brad Thomas
14
@BradThomas: Ce n'est pas le cas. Le risque de collision MD5 est le même que ce soit sur le nom de fichier ou sur la combinaison nom de fichier + horodatage. Mais dans le premier scénario, vous auriez besoin à la fois d'une collision MD5 et d'une collision d'horodatage.
Vincent Hubert
2
Cela laisse toujours 2 ^ (128 ^ 60) chances de collision avec deux utilisateurs par minute. Littéralement inutilisable.
Berry M.
2
@BradThomas Pour être plus clair: md5(filename) + timestampréduit massivement le risque de collision car vous auriez besoin d'une collision md5 pour exactement le même horodatage pour avoir une collision globale. md5(filename + timestamp)est le même que md5(filename), en supposant que le nom de fichier est aléatoire pour commencer (car l'ajout de plus d'aléatoire à quelque chose d'aléatoire ne change que le résultat individuel de md5 et le problème d'anniversaire existe toujours dans tous les hachages md5).
robocat
10

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

Will Dean
la source
1
Vous voulez probablement dire 128 bits, pas 2 ^ 128. :-)
JesperE
5
en.wikipedia.org/wiki/Birthday_Problem Quelques informations supplémentaires sur le problème.
Georg Schölly
7

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

bdonlan
la source
l'utilisation d'un sel réglerait le problème d'ingénierie de l'utilisateur, non?
StackOverflowed
Cela dépend de la façon dont le sel est appliqué. Il faudrait qu'il s'agisse d'un préfixe des données fournies par l'utilisateur, ou mieux encore de la clé d'un HMAC. C'est probablement toujours une bonne idée de pratiquer la défense en profondeur.
bdonlan
Notez que bien que SHA256 ait une longueur de 256 bits, vous pouvez échanger le risque de collision avec la longueur de la clé que vous stockez en tronquant le SHA256 à moins de bits, par exemple utilisez SHA256 mais tronquez-le à 128 bits (ce qui est plus sûr que l'utilisation de MD5 même bien qu'ils aient le même nombre de bits).
robocat
5

Bien qu'il y ait eu des problèmes bien connus avec MD5 en raison de collisions, les collisions non intentionnelles entre des données aléatoires sont extrêmement rares . D'un autre côté, si vous hachez le nom du fichier, ce ne sont pas des données aléatoires, et je m'attendrais à des collisions rapidement.

acrosman
la source
Le seul problème que j'ai avec l'exemple de taylors est que si quelqu'un obtient une copie de votre base de données, il pourrait probablement trouver les numéros de carte de crédit en utilisant une table arc-en-ciel ...
Sam Saffron
1
Bien que je ne choisisse pas d'utiliser MD5 pour les cartes de crédit, un tableau Rainbow de tous les numéros de carte de crédit valides entre 10000000 (8 chiffres étant la carte de crédit la plus petite que j'ai vue) et 9,999,999,999,999,999 (le plus grand nombre à 16 chiffres) est toujours un grand table à générer. Il existe probablement des moyens plus faciles de voler ces chiffres.
acrosman
1

Peu importe sa probabilité; c'est possible. Cela pourrait arriver sur les deux premières choses que vous hachez (très peu probable, mais possible), vous devrez donc prendre en charge les collisions depuis le début.

Karg
la source
37
Il peut bien sûr y avoir beaucoup d'autres mauvaises choses qui peuvent arriver avec une probabilité de 1/2 ^ 128. Vous ne voudrez peut-être pas isoler celui-ci dont vous avez besoin.
Will Dean
2
La pire chose qui puisse arriver ici est que vous puissiez prendre une photo. Pour un nombre relativement petit, je ne m'inquiéterais pas. Maintenant, si votre logiciel contrôle un pilote automatique à l'atterrissage d'un avion, c'est une autre histoire.
Jim C
9
Tu ne peux pas être sérieux. Vous aurez besoin de hacher 6 milliards de fichiers par seconde, chaque seconde pendant 100 ans pour avoir de bonnes chances de collision. Même si vous êtes très malchanceux, cela prendrait probablement plus que la capacité totale de S3 utilisée plus longtemps qu'une vie humaine.
Kornel
13
Il est des milliards de fois plus probable que votre base de données et ses sauvegardes échouent toutes. Les collisions ne valent pas la peine de s'inquiéter.
Artelius
6
Utilisez le temps de prévention des collisions pour construire un bunker pour mettre votre serveur! Ces météores embêtants peuvent vous frapper (très peu probable, mais possible), vous devrez donc soutenir un abri contre les météores de la mendicité.
polvoazul
1

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

Rick James
la source
1
De nombreuses autres réponses parlent de la probabilité d'une collision lors de l'ajout d' un élément supplémentaire. Je pense que ma réponse est plus utile car elle parle de la probabilité que toute la table ait un dup.
Rick James
1
Cela n'a rien à voir avec MD5 et n'est pas correct. C'est comme dire que si vous avez 9 trillions de chats, il y a 1 chance sur 9 trillions que quelqu'un d'autre ait un chat identique. Le principal problème ici est que vous pouvez obtenir le même hachage avec plus d'une valeur.
Joonas Alhonen
@JoonasAlhonen - Oui, c'est vrai. Et beaucoup de pauvres utilisent cela comme une excuse pour acheter un autre billet de loterie qu'ils ne peuvent pas se permettre.
Rick James
Merci, c'est en fait une statistique très utile. Les chances d'avoir eu une collision lors de l'insertion de 9 trillions d'articles. Merci.
Tom P.