Как проверить идентичность огромных файлов, если хеширование связано с процессором?

К сожалению, MD5 - это линейный процесс, состояние которого зависит от всех предыдущих входных данных. Другими словами, вы не можете по-настоящему распараллелить это. Более того, я не знаю ни одного реального хэша, который бы не работал таким образом.

Что вы можете сделать (и, основываясь на вашем ответе, который вы делаете), это разделить исходные файлы и одновременно вычислить сумму md5sum каждого чанка.

Если вы не можете / не хотите этого делать, вам пришлось использовать более быструю хеш-функцию, такую как xxHash, CityHash или SpookyHash

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

Обработка всего файла практически невозможна. MD4 или CRC32, вероятно, ваши лучшие ставки для широко развернутого и быстрого алгоритма (хотя CRC32 будет гораздо менее эффективным, чем MD4).

Тестирование различных реализаций вашего алгоритма выбора поможет. Если вы сможете найти хорошо протестированную реализацию asm, она, вероятно, улучшит производительность своих кузенов C/C++.

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

Этот Gist может быть хорошим началом для чего-то в Python.

Я работаю над проектом хеширования дерева, который предназначен именно для этой проблемы: готовое параллельное хеширование больших файлов. Теперь он работает, хотя он и не был проверен, и есть большая вероятность, что изменения по сравнению с обзором приведут к изменениям в окончательном дайджесте. Тем не менее, это очень быстро: https://github.com/oconnor663/bao

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

Рассмотрим подход BitTorrent: при создании торрента все файлы разделяются на "блоки", каждый блок хэшируется отдельно, и каждый из этих хэшей записывается в файл.torrent. Это то, что позволяет одноранговому устройству постепенно проверять поступающие данные, не дожидаясь завершения загрузки всего файла. Ошибки также могут быть исправлены отдельно для каждого блока, вместо того, чтобы требовать повторной передачи всего файла. Помимо логистических преимуществ, этот подход также позволяет масштабировать хеширование по нескольким ядрам - если доступно 8 ядер, можно одновременно хэшировать 8 блоков.

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

Вы можете использовать md5deep для этого и hashdeep для других хэшей. Он поддерживает многопоточность с -j флаг. По умолчанию он создает поток хеширования для каждого ядра. Он также имеет флаг для разбиения файлов на части перед хэшированием, но не будет использовать несколько потоков в одном файле. Я использовал это для получения sha256 из полумиллиона файлов, и это прекрасно работало. Он также имеет рекурсивную флэш-память, которая облегчает обработку больших деревьев каталогов.

Вот справочная страница для этого http://md5deep.sourceforge.net/md5deep.html и git-репо https://github.com/jessek/hashdeep

Имя пакета в Ubuntu и Debian - md5deep и включает hashdeep.

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

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

Как и предполагали другие, вы можете создать хеш-функцию как хеш-код объединенных хеш-кодов каждого из блоков заданного размера в оригинале. До тех пор, пока размер блока достаточно велик, чтобы затруднить обращение хэшей отдельных блоков, это, вероятно, будет работать достаточно хорошо для большинства целей. Насколько большой это должно быть, зависит от того, насколько предсказуемо содержание этих блоков. Если вы можете оценить энтропию и выбрать размер блока таким образом, чтобы вы получали 128+ битов энтропии на блок, этого должно быть достаточно для большинства целей (и избыточного для многих, где безопасность не является первостепенной задачей).

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

Возможно, стоит отметить, что наличие фиксированного размера блока означает, что основной недостаток MD5 не имеет значения - хакер не может добавить дополнительные данные в блок.

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

Функция из группы функций Skein, использующая необязательный режим хэш-дерева, может подойти вам. Опять же, CRC32 может быть всем, что вам нужно.