06-10-2023
Структура Меркла-Дамгарда (англ. Merkle–Damgård construction или англ. Merkle–Damgård hash function) — метод построения криптографических хеш-функций. Криптографическая хеш-функция должна преобразовывать входное сообщение произвольной длины в выходное сообщение фиксированной длины. Этого можно достичь путём разбиения входного сообщения на блоки одинакового размера и их последовательной обработки односторонней функцией сжатия, которая преобразовывает входное сообщение фиксированной длины в более короткое выходное сообщение фиксированной длины. Функция сжатия либо может быть специально построена для хеширования либо может представлять собой функцию блочного шифрования. Хеш-функция Меркла-Дамгарда разбивает входное сообщение на блоки и работает с ними по очереди с помощью функции сжатия, каждый раз принимая входной блок с выходным от предыдущего раунда.
Структура Меркла-Дамгарда была описана в докторской диссертации Ральфа Меркла[1]. Ральф Меркл и Иван Дамгор независимо показали: если функция сжатия устойчива к коллизиям, то и хеш-функция будет также устойчива.[2][3] Чтобы доказать устойчивость структуры, Меркл и Дамгор предложили дополнить сообщение блоком, который кодирует длину первоначального сообщения. Это называется упрочнение Меркла-Дамгарда (англ. Merkle–Damgård strengthening).
На рисунке односторонняя функция сжатия обозначена f, и преобразует два входных блока фиксированной длины в выходной блок того же размера, что и входные. Алгоритм начинает с начального значения — вектора инициализации (на рисунке — IV). Вектор инициализации — фиксированное значение (зависит от реализации алгоритма). Для каждого блока сообщения, функция сжатия f принимает результат предыдущего раунда и блок сообщения, и производит промежуточный результат. Последний блок дополняется нулями, если необходимо. Также, добавляется блок с информацией о длине целого сообщения (см. подробный пример ниже).
Для упрочнения хеша, последний результат иногда пропускают через функцию финализации (finalisation function). Функция финализации может использоваться для уменьшения размера выходного хеша, сжатием результата последней функции f в хеш более маленького размера, или чтобы гарантировать лучшее смешивание битов и усилить влияние небольшого изменения входного сообщения на хеш (Лавинный эффект, avalanche effect). Функция финализации часто строится с использованием функции сжатия.
Популярность структуры Меркла-Дамгарда обусловлена тем, что, как было доказано, если односторонняя функция сжатия f устойчива к коллизиям, то и хеш-функция, построенная на ее основе, будет также устойчива к коллизиям. Эта структура имеет несколько нежелательных свойств:
Для того, чтобы передать сообщение в функцию сжатия, необходимо дополнить последний блок до полного определёнными данными (обычно нулями).
Но этого недостаточно, так как это будет означать, что различные сообщения, начинающиеся одними и теми же символами, и заканчивающимися нулями или другими байтами из заполнителя, будут поступать в функцию сжатия совершенно одинаковыми блоками, и будет получаться одинаковая хеш-сумма.
Чтобы этого избежать, первый бит добавляемых данных, должен быть изменен. Так как заполнитель обычно состоит из нулей, первый бит заполнителя должен быть заменён на «1».
Чтобы усилить хеш, можно добавить длину сообщения в дополнительном блоке
Чтобы избежать двусмысленности, значение длины сообщения должно быть само по себе устойчиво к добавлению заполнителя в блок. Наиболее распространенные реализации используют фиксированный размер (обычно 64 или 128 бит в современных алгоритмах) и фиксированную позицию в конце последнего блока для кодирования значения длины сообщения. Однако, немного расточительно кодировать один дополнительный блок для длины сообщения. Поэтому, существует небольшая оптимизация алгоритма, которая часто используется. Если в последнем блоке сообщения достаточно места значение длины сообщения может быть добавлено к нему.
То есть получаем 2 блока:
В 2006 году был предложен подход HAIFA, при котором Структура Меркла — Дамгарда немного модифицируется. В каждую функцию сжатия дополнительно к блоку сообщения подается текущее смещение в входном файле и, опционально, некоторая соль.
Из-за некоторых слабых мест структуры Меркла-Дамгарда, особенно проблемы, связанной с дополнением сообщения до необходимой длины, Стефан Лакс (Stefan Lucks) предложил использовать wide-pipe хеш[7] вместо структуры Меркла-Дамгарда. Wide-pipe хеш очень похож на структуру Меркла-Дамгарда, но имеет больше внутренних состояний, то есть битовая длина, использующаяся внутри алгоритма больше, чем выходная. Таким образом, последний этап — вторая функция сжатия, которая сжимает последнее внутреннее значение хеша в окончательное значение. SHA-224 и SHA-384 были получены из SHA-256 и SHA-512 соответственно, путём применения этого алгоритма.
Структура Меркла — Дамгарда.