Вычисление хеш-кода для большого файла параллельно

Question

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

Обычно вы последовательно хешируете байты файлов, используя хэш-функцию (скажем, дляпример SHA-256, хотя я, скорее всего, буду использовать Skein, поэтому хеширование будет медленнее по сравнению со временем, которое требуется для чтения файла с [быстрого] SSD).Давайте назовем этот метод 1.

Идея состоит в том, чтобы параллельно хэшировать несколько блоков по 1 МБ файла на 8 процессорах, а затем хэшировать объединенные хэши в один финальный хеш.Давайте назовем этот метод 2.

Изображение, изображающее этот метод, выглядит следующим образом:

---

---

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

Например:

Давайте использовать SHA-256 варианта SHA-2 и установите размер файла 2 ^ 34 = 34 359 738 368 байт.Поэтому, используя простой проход (метод 1), я бы получил 256-битный хеш для всего файла.

Сравните это с:

Используя параллельное хеширование (т. Е. Метод 2).), Я бы разбил файл на 32 768 блоков по 1 МБ, хэшировал эти блоки с помощью SHA-256 на 32 768 хешей по 256 бит (32 байта), объединял хэши и делал окончательный хэш результирующего конкатенированного набора данных размером 1 048 576 байт, чтобымой последний 256-битный хеш для всего файла.

Является ли метод 2 менее безопасным, чем метод 1, с точки зрения вероятности и / или вероятности коллизий?Возможно, мне следует перефразировать этот вопрос следующим образом: облегчает ли злоумышленник метод 2 созданию файла, который хэширует то же значение хеш-функции, что и исходный файл, за исключением, разумеется, тривиального факта, что атака методом "грубой силы" будет дешевле, посколькухэш может быть рассчитан параллельно на N cpus?

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

Answer 1

Хэширование на основе блоков (ваш метод 2) - это хорошо известная методика, которая используется на практике:

• Хеш-дерево, Меркле, Тигровое хеш-код
• хэш файла eDonkey2000 (одноуровневое дерево с размером блока ~ 9 МБ)

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

Answer 2

Некоторые современные конструкции хэшей позволяют запускать их параллельно.См. Эффективный параллельный алгоритм для хэш-функций Скейна .Если вы хотите использовать новый (и, следовательно, менее тщательно протестированный) алгоритм хэширования, это может дать вам необходимое увеличение скорости на многопроцессорной машине.* Конкурс NIST SHA-3 , поэтому он не полностью не протестирован.

Answer 3

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

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

Однако, если вы разбиваете исходный файл на блоки, скорость атаки теперь зависит от самого маленького блока (или размера блока, который вы хотите изменить). Так как размер файла линейно увеличивается со временем хэширования, файл 100 ГБ займет примерно 2000 секунд для каждой перестановки / MD5, а блок 1 МБ позволит злоумышленнику попробовать 50 в секунду .

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