Comment puis-je évaluer la probabilité de collision?
je développe une application back-end pour un système de recherche. Le système de recherche copie les fichiers dans un répertoire temporaire et leur donne des noms aléatoires. Puis il passe les noms des fichiers temporaires à mon application. Ma demande doit traiter chaque dossier dans un délai limité, sinon il est fermé - c'est une mesure de sécurité de chien de garde. Le traitement des fichiers est susceptible de prendre du temps, donc je dois concevoir l'application capable de gérer ce scénario. Si ma demande est arrêté la prochaine fois que le système de recherche veut indexer le même fichier, il lui donnera probablement un nom temporaire différent.
la solution évidente est de fournir une couche intermédiaire entre le système de recherche et le support. Il mettra la requête en file d'attente et attendra l'arrivée du résultat. Si la requête tourne dans la couche intermédiaire - pas de problème, le backend va continuer à fonctionner, seule la couche intermédiaire est redémarrée et elle peut récupérer le résultat de la backend lorsque la requête est répétée par la suite par le système de recherche.
Le problème est de savoir comment identifier les fichiers. Leurs noms changent au hasard. J'ai l'intention d'utiliser une fonction de hachage comme MD5 pour hacher le contenu du fichier. Je suis bien conscient du paradoxe d'anniversaire et utilisé une estimation de l'article lié pour calculer la probabilité. Si je suppose que je n'ai pas plus de 100 000 fichiers la probabilité de deux fichiers ayant le même MD5 (128 bits) est d'environ 1, 47x10 -29 .
dois-je m'occuper de cette probabilité de collision ou simplement supposer que des valeurs de hachage égales signifient des contenus de fichier égaux?
5 réponses
hachage égal signifie fichier égal, à moins que quelqu'un de malveillant ne s'amuse avec vos fichiers et injecte des collisions. (ce pourrait être le cas s'ils téléchargent des trucs à partir de l'internet) si c'est le cas aller pour une fonction basée SHA2.
il n'y a pas de collisions accidentelles MD5, 1,47x10 -29 est vraiment un nombre vraiment très petit.
pour surmonter la question de reformuler de gros fichiers, j'aurais un 3 phasé l'identité régime.
- Taille du fichier seul
- Taille du fichier + une table de hachage de 64 KO * 4 dans différentes positions dans le fichier
- hash
donc si vous voyez un fichier avec une nouvelle taille, vous savez avec certitude que vous n'avez pas de duplicata. Et ainsi de suite.
je pense que vous ne devriez pas.
cependant, vous devriez Si vous avez la notion de deux fichiers égaux ayant différents (noms réels, pas basé sur md5). Par exemple, dans le système de recherche, deux documents peuvent avoir exactement le même contenu, mais être distincts parce qu'ils sont situés à des endroits différents.
ce N'est pas parce que la probabilité est de 1/X que cela signifie que cela ne vous arrivera pas tant que vous n'aurez pas les enregistrements X. C'est comme la loterie, vous n'êtes pas susceptible de gagner, mais quelqu'un là-bas gagnera .
avec la vitesse et la capacité des ordinateurs de nos jours (sans même parler de sécurité, juste de fiabilité) il n'y a vraiment aucune raison de ne pas utiliser une fonction de hachage plus grande/meilleure que MD5 pour quelque chose de critique. Stepping jusqu'à SHA-1 devrait vous aider à mieux dormir la nuit, mais si vous voulez être très prudent ensuite, allez à SHA-265 et de ne jamais penser.
si la performance est vraiment un problème, alors utilisez BLAKE2 qui est en fait plus rapide que MD5 mais prend en charge 256+ bits pour rendre les collisions moins probables tout en ayant la même ou de meilleures performances. Cependant, bien que BLAKE2 ait été bien adopté, il faudrait probablement ajouter une nouvelle dépendance à votre projet.
j'ai inventé une approche Monte Carlo pour pouvoir dormir en toute sécurité tout en utilisant UUID pour les systèmes distribués qui doivent sérialiser sans collisions.
from random import randint
from math import log
from collections import Counter
def colltest(exp):
uniques = []
while True:
r = randint(0,2**exp)
if r in uniques:
return log(len(uniques) + 1, 2)
uniques.append(r)
for k,v in Counter([colltest(20) for i in xrange(1000)]):
print k, "hash orders of magnitude events before collission:",v
imprimerait quelque chose comme:
5 hash orders of magnitude events before collission: 1
6 hash orders of magnitude events before collission: 5
7 hash orders of magnitude events before collission: 21
8 hash orders of magnitude events before collission: 91
9 hash orders of magnitude events before collission: 274
10 hash orders of magnitude events before collission: 469
11 hash orders of magnitude events before collission: 138
12 hash orders of magnitude events before collission: 1
j'avais déjà entendu la formule avant: si vous avez besoin de stocker les clés log(x/2), Utilisez une fonction de hachage qui a au moins l'espace E**(x).
des expériences répétées montrent que pour une population de 1000 log-20 espaces, vous obtenez parfois une collision dès log(x/4).
pour uuid4 qui est de 122 bits qui signifie que je dors en toute sécurité tandis que plusieurs ordinateurs de choisir au hasard uuid's jusqu'à ce que j'ai environ 2**31 articles. Les transactions de pointe dans le système que je pense est d'environ 10-20 événements par seconde, je suppose une moyenne de 7. Cela me donne une fenêtre opératoire d'environ 10 ans, étant donné cette paranoïa extrême.
voici une calculatrice interactive qui vous permet d'estimer la probabilité de collision pour n'importe quelle taille de hachage et le nombre d'objets - http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/