Как я должен обрабатывать коллизии контрольной суммы в моем приложении?

Question

У меня есть часть моего приложения, которая хранит файлы. Поскольку мы потенциально можем добавлять многие из одного и того же файла, я сначала сохраняю хэш каждого файла. Если два файла имеют одинаковый хэш, мы выбрасываем один, и оба «ссылки» на этот файл указывают на один и тот же физический файл.

1. Насколько я должен беспокоиться о хеш-коллизиях?

2. Что делать в случае столкновения? Вся суть моего кода до сих пор зависит от отсутствия двух разных файлов с одинаковым хешем. В случае коллизии мое приложение сейчас выбрасывает совершенно другой файл и указывает на файл с таким же хешем.

3. Должен ли я использовать что-то кроме MD5? Имеет ли SHA-1 лучшую частоту столкновений?

Answer 1

Если вы не находитесь в действительно ДЕЙСТВИТЕЛЬНО критически важном приложении, не беспокойтесь о хеш-коллизиях. Они настолько редки, что многие вещи предполагают, что этого не произойдет, и катастрофические вещи произойдут с этими вещами, если это предположение окажется ложным только один раз.

SHA1 имеет большее пространство вывода, чем MD5 (и на него также известно меньше атак), так что это определенно не худший выбор. Если вы боитесь, что кто-то будет активно конфликтовать с вашими хэшами, возможно, хорошей идеей будет более поздний вариант SHA, такой как SHA-256.

Answer 2

Вероятность коллизии между хэшами любых двух случайно выбранных битовых потоков обратно пропорциональна числу различных состояний, которые представляет хеш. Таким образом, 64-битный хэш кодирует 2 ** 64 состояний и имеет шанс 1 / (2**64) коллизии для любой пары файлов. Но вы действительно обеспокоены вероятностью коллизий по (большому) набору файлов, поэтому вам нужно вычислить «парадокс дня рождения», включив вероятность парного коллизии и ожидаемое количество файлов.

Но я думаю, что суть в том, что выбрасывать файл без сравнения - небезопасная вещь, даже если числа говорят, что вероятность столкновения мала.

Answer 3

В предоставленном сценарии вам никогда не придется беспокоиться. 2 разных документа не могут иметь одинаковую контрольную сумму, если они не совпадают. Представь себе:

var a = 1; var b = 2;

b + 3 = 5; // правда да! + 3! = 5; // коллизия невозможна, если переменная a не равна 2

var 'a' с любым значением, отличным от 2, никогда не сможет вычислить значение 5, поэтому столкновение невозможно. Поскольку вы используете (или должны использовать) алгоритм одностороннего хеширования контрольной суммы, результирующий хеш всегда будет зависеть от его входных данных

Коллизии хэшей случаются, когда вы имеете дело со случайно сгенерированными хешами, которые из-за их случайных неуказанных входных данных могут столкнуться, хотя и маловероятно.

Пожалуйста, обратите внимание, я ни в коем случае не делаю вывод, что алгоритмы хеширования в одном направлении выполняются простым добавлением. Я просто использую сложение в качестве простого примера, основанного на простом представлении о том, что они оба принимают набор значений и выводят различные заданные значения на их основе.