Как оценить вероятность столкновения хэша?

Равный хэш означает одинаковый файл, если только кто-то злонамеренный не возится с вашими файлами и не создает коллизии. (это может иметь место, если они загружают материал из Интернета). Если это так, используйте функцию на основе SHA2.

Случайных коллизий MD5 не бывает, 1,47x10 ^-29 - действительно очень маленькое число.

Чтобы решить проблему перефразирования больших файлов, я бы использовал трехэтапную схему идентификации.

1. Только размер файла
2. Размер файла + хеш 64К * 4 в разных позициях в файле
3. Полный хеш

Итак, если вы видите файл нового размера, значит, вы точно знаете, что у вас нет дубликата. И так далее.

Тот факт, что вероятность равна 1 / X, не означает, что с вами этого не случится, пока у вас не будет X записей. Это похоже на лотерею: вы вряд ли выиграете, но кто-то где-то там выиграет.

Учитывая скорость и производительность компьютеров в наши дни (даже не говоря о безопасности, просто о надежности), действительно нет причин не использовать более крупную / лучшую хеш-функцию, чем MD5, для чего-либо критически важного. Переход на SHA-1 должен помочь вам лучше спать по ночам, но если вы хотите быть особенно осторожными, перейдите к SHA-265 и никогда больше не думайте об этом.

Если производительность действительно является проблемой, используйте BLAKE2, который на самом деле быстрее, чем MD5, но поддерживает более 256 бит, чтобы уменьшить вероятность коллизий, имея такую ​​же или лучшую производительность. Однако, хотя BLAKE2 был хорошо принят, вероятно, потребуется добавить новую зависимость в ваш проект.

Думаю, не стоит.

Однако вам следует это сделать, если у вас есть представление о двух одинаковых файлах, имеющих разные (настоящие имена, а не на основе md5). Например, в поисковой системе два документа могут иметь совершенно одинаковый контент, но отличаться друг от друга, потому что они расположены в разных местах.

Я придумал подход Монте-Карло, чтобы иметь возможность безопасно спать при использовании UUID для распределенных систем, которые должны сериализоваться без коллизий.

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

напечатал бы что-то вроде:

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

Я слышал эту формулу раньше: если вам нужно хранить ключи журнала (x / 2), используйте функцию хеширования, которая имеет как минимум пространство ключей e ** (x).

Неоднократные эксперименты показывают, что для популяции в 1000 log-20 пространств вы иногда получаете коллизию уже в log (x / 4).

Для uuid4, который составляет 122 бита, это означает, что я спокойно сплю, в то время как несколько компьютеров выбирают случайные uuid, пока у меня не будет около 2 ** 31 элемента. Пик транзакций в системе, о которой я думаю, составляет примерно 10-20 событий в секунду, я предполагаю, что в среднем 7. Это дает мне рабочее окно примерно в 10 лет, учитывая эту крайнюю паранойю.

Вот интерактивный калькулятор, который позволяет оценить вероятность столкновения для любого размера хэша и количества объектов - http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/