Как мне оценить вероятность коллизии хеша?
Я разрабатываю серверное приложение для поисковой системы. Поисковая система копирует файлы во временный каталог и присваивает им случайные имена. Затем он передает имена временных файлов в мое приложение. Мое приложение должно обрабатывать каждый файл в течение ограниченного периода времени, в противном случае оно будет закрыто - это мера безопасности, похожая на сторожевую. Обработка файлов, вероятно, займет много времени, поэтому мне нужно разработать приложение, способное справиться с этим сценарием. Если мое приложение будет закрыто в следующий раз, когда поисковая система захочет проиндексировать тот же файл, скорее всего, ему будет присвоено другое временное имя.
Очевидное решение состоит в том, чтобы обеспечить промежуточный уровень между поисковой системой и серверной частью. Он поставит запрос в бэкэнд и будет ждать получения результата. Если время ожидания запроса на промежуточном уровне истекло, бэкэнд продолжит работать, только промежуточный уровень будет перезапущен, и он может получить результат из бэкэнда, когда запрос впоследствии будет повторен поисковой системой.
Проблема в том, как определить файлы. Их имена меняются случайным образом. Я намерен использовать хеш-функцию, такую как MD5, для хэширования содержимого файла. Я хорошо знаю парадокс дня рождения и использовал оценку из связанной статьи, чтобы вычислить вероятность. Если я предполагаю, что у меня не более 100 000 файлов, вероятность того, что два файла имеют одинаковый MD5 (128 бит), составляет около 1,47x10-29.
Должен ли я заботиться о такой вероятности столкновения или просто предполагать, что равные значения хеша означают равное содержимое файла?
6 ответов
Равный хеш означает равный файл, если кто-то злоумышленник не возится с вашими файлами и не вводит коллизии. (это может иметь место, если они загружают материал из Интернета). В этом случае используйте функцию, основанную на SHA2.
Нет случайных столкновений MD5, 1,47x10-29 - это действительно очень небольшое число.
Чтобы преодолеть проблему перефразирования больших файлов, у меня была бы трехфазная схема идентификации.
- Один размер файла
- Размер файла + хэш 64K * 4 в разных позициях в файле
- Полный хеш
Так что если вы видите файл с новым размером, который вы наверняка знаете, у вас нет дубликата. И так далее.
Тот факт, что вероятность равна 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/
Для временных имен файлов используйте функциональные возможности ОС. Вероятно, он использует промежуточный подкаталог, эпоху Unix и т. д.