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

Мое лучшее на данный момент решение:

parallel --block=512M --pipepart -a …HUGEFILE… --progress --recend '' \ -k -j …NUMofProcessesSay4… md5sum | md5sum

- Следует отметить, что:

1. Полученный хеш md5 не относится к файлу, а скорее к md5 его частей, но все же он позволяет вам сравнивать, идентична ли реплика источнику
2. Он также не работает очень хорошо, особенно когда вы используете pipe а не файл как ввод
3. parallelс --pipepart как я выяснил, не поддерживает разделы диска

Так что я бы хотел услышать и другие способы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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