Comment puis-je évaluer la probabilité de collision de hachage?

Question

Je développe une application back-end pour un système de recherche. Les fichiers système copie de recherche dans un répertoire temporaire et leur donne des noms aléatoires. Ensuite, il passe les noms des fichiers temporaires à ma demande. Mon application doit traiter chaque dossier dans un laps de temps limité, sinon il est arrêté - qui est une mesure de sécurité comme chien de garde. le traitement des dossiers est susceptible de prendre de temps, alors je dois concevoir l'application capable de gérer ce scénario. Si ma demande censureront prochaine fois que le système de recherche veut indexer le même fichier, il sera probablement lui donner un nom temporaire différent.

La solution évidente consiste à fournir une couche intermédiaire entre le système de recherche et l'arrière-plan. Il file d'attente la demande au back-end et attendre le résultat pour arriver. Si les temps de demande dans la couche intermédiaire -. Pas de problème, le serveur continuera à travailler, seule la couche intermédiaire est redémarré et il peut récupérer le résultat à partir du serveur lorsque la demande est répétée plus tard 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 de hachage le contenu du fichier. Je suis bien conscient du paradoxe d'anniversaire et a utilisé une estimation de l'article lié à 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 prendre soin de cette probabilité de collision ou simplement supposer que les valeurs de hachage égales signifie le contenu des fichiers égaux?

Answer 1

hachage égal signifie fichier égal, à moins que quelqu'un malveillant de déconner avec vos fichiers et injectent des collisions. (Cela pourrait être le cas si elles téléchargent des choses de l'Internet) Si tel est le cas pour aller une fonction basée SHA2.

Il n'y a pas de collisions MD5 accidentelle, 1,47x10 ^-29 est un nombre vraiment vraiment vraiment petit.

Pour surmonter le problème de ressasser les grands dossiers que j'aurais un système 3 d'identité progressive.

1. Taille du fichier seul
2. + Taille du fichier un hachage de 64K * 4 dans différentes positions dans le fichier
3. Une pleine hachage

Donc, si vous voyez un fichier avec une nouvelle taille que vous savez pour vous que vous ne disposez pas d'un double. Etc.

Answer 2

Juste parce que la probabilité est de 1 / X ne veut pas dire qu'il ne se produira pas à vous jusqu'à ce que vous avez des documents X. Il est comme la loterie, vous n'êtes pas susceptible de gagner, mais quelqu'un là gagnant.

Avec la vitesse et la capacité des ordinateurs de nos jours (ne parle même pas de la sécurité, la fiabilité juste) il n'y a vraiment aucune raison de ne pas simplement utiliser une plus grande / meilleure fonction de hachage MD5 que pour quoi que ce soit critique. Stepping jusqu'à SHA-1 devrait vous aider à mieux dormir la nuit, mais si vous voulez être prudent supplémentaire puis passez à SHA-265 et ne jamais penser à nouveau.

Si la performance est vraiment un problème utilisez BLAKE2 qui est en fait plus rapide que MD5 mais prend en charge 256+ bits pour produire des collisions moins susceptibles tout en performances égales ou supérieures. Cependant, il serait probablement tout BLAKE2 a été bien adopté, nécessitent l'ajout d'une nouvelle dépendance à votre projet.

Answer 3

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, et non pas en fonction md5-). Comme, dans le système de recherche de deux documents pourrait avoir exactement le même contenu, mais étant distincts parce qu'ils sont situés dans des endroits différents.

Answer 4

Je suis venu avec une approche de 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 entendu la formule avant. Si vous devez stocker log (x / 2) clés, utilisez une fonction de hachage qui a au moins keyspace ** e (x)

Des expériences répétées montrent que pour une population de 1000 log-20 places, 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é alors que plusieurs ordinateurs de Pick UUID aléatoires jusqu'à ce que j'ai environ 2 ** 31 articles. opérations de pointe dans le système que je pense à peu près 10-20 est des événements par seconde, je suppose une moyenne de 7. Cela me donne une fenêtre d'exploitation d'environ 10 ans, étant donné que la paranoïa extrême.

Answer 5

Voici une calculatrice interactive qui vous permet d'estimer la probabilité de collision pour une taille de hachage et le nombre d'objets - http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/