Структура Меркла — Дамгора
Структура Меркла-Дамгарда (англ. Merkle–Damgård construction или Merkle–Damgård hash function) - метод построения криптографических хеш-функций. Криптографическая хеш-функция должна преобразовывать входное сообщение произвольной длины в выходное сообщение фиксированной длины. этого можно достичь, разбив входное сообщение на блоки одинакового размера, и преобразовывать последовательно обработав их односторонней функцией сжатия, которая преобразовывает сообщение фиксированной длины в более короткое выходное сообщение фиксированной длины. Функция сжатия также может быть специально построена для хеширования или может представлять собой функцию блочного шифрования. Хеш-функция Меркла-Дамгарда разбивает входное сообщение на блоки и работает с ними по очереди с помощью функции сжатия, каждый раз принимая входной блок с выходным от предыдущего раунда.
Структура Меркла-Дамгарда была описана в докторской диссертации Ральфа Меркла. Ральф Меркл и Иван Дамгор независимо показали: если функция сжатия устойчива к коллизиям, то и хеш-функция будет также устойчива. Чтобы доказать устойчивость стуктуры, Меркл и Дамгор предложили дополнить сообщение блоком, который кодирует длину первоначального сообщения. Это называется упрочнение Меркла-Дамгарда (англ. Merkle–Damgård strengthening).
На рисунке односторонняя функция сжатия обозначена f, и преобразует два входных блока фиксированной длины в выходной блок того же размера, что и входные. Алгоритм начинает с начального значения - вектора инициализации (на рисунке - IV). Вектор инициализации - фиксированное значение (зависит от реализации алгоритма). Для каждого блока сообщения, функция сжатия f принимает результат предыдущего раунда и блок сообщения, и производит промежуточный результат. Последний блок дополняется нулями, если необходимо. Также, добавляется блок с информацией о длине целого сообщения (см. подробный пример ниже).
Для упрочнения хеша, последний результат иногда пропускают через функцию финализации (finalisation function). Функция финализации может использоваться для уменьшения размера выходного хеша, сжатием результата последней функции f в хеш более маленького размера, или чтобы гарантировать лучшее смешивание битов и усилить влияние небольшого изменения входного сообщения на хеш (avalanche effect). Функция финализации часто строится с использованием функции сжатия.
Характеристики безопасности
Структура Меркла-Дамгарда популярна из-за того, что ,как было доказано, если односторонняя функция сжатия f устойчива к коллизиям, то и хеш-функция, Построенная на ее основе, будет также устойчива к коллизиям. К сожалению, эта структура имеет несколько нежелательных свойств:
- Дополнение до необходимой длины - когда атакующий найдет хотя бы одну коллизию, он очень легко может найти другие.
- Нахождение второго сообщения, дающего такой-же хеш (англ. second preimage attacks) для длинных сообщений всегда намного более эффективны, чем перебор(brute force)
- Множественные коллизии (много сообщений имеют одинаковый хеш) могут быть найдены лишь немного большими усилиями, чем коллизии.
- Атаки дополнением сообщения: При данном хеше H(X) неизвестного входного сообщения X, легко найти значение H(pad(X)||Y), где pad - функция дополнения . Это значит, что возможно найти хеши входных сообщений, связанных с X, даже когда X остается неизвестным. Random oracle не имеет такой возможности, и это может привести к простым атакам даже на схемы, безопасность которых была даказана для модели атак random oracle.
Пример дополнения сообщения
Для того, чтобы передать сообщение в функцию сжатия, необходимо дополнить последний блок до полного определёнными данными (обычно нулями).
Например, предположим, сообщение - “HashInput” и размер блока дляфункции сжатия - 8 байт (64 бит). В таком случае, получится 2 блока: HashInpu t0000000
Но этого недостаточно, так как это будет означать, что различные сообщения, начинающиеся одними и теми же символами, и заканчивающимися нулями или другими байтами из заполнителя , будут поступать в функцию сжатия совершенно одинаковыми блоками, и будет получаться одинаковая хеш-сумма.
В нашем примере, например, сообщение “HashInput00” , будет разделено на такие же блоки, что и первоначальное сообщение “HashInput”.
Чтобы этого избежать, первый бит добавляемых данных, должен быть изменен.Так как заполнитель обычно состоит из нулей, первый бит заполнителя должен быть заменён на “1”.
В нашем примере, мы получим следующее: HashInpu t1000000
Чтобы усилить хеш, можно добавить длину сообщения в дополнительном блоке
В нашем примере мы получим три блока: HashInpu t1000000 00000009
Чтобы избежать двусмысленности, значение длины сообщения должно быть само по себе устойчиво к добавлению заполнителя в блок. Наиболее распространенные реализации используют фиксированный размер (обычно 64 или 128 бит в современных алгоритмах) и фиксированную позицию в конце последнего блока для кодирования значения длины сообщения. Однако, немного расточительно кодировать один дополнительный блок для длины сообщения. Поэтому, существует небольшая оптимизация алгоритма, которая часто используется. Если в последнем блоке сообщения достаточно места значение длины сообщения может быть добавлено к нему.
Например, возьмем в нашем примере, что длина сообщения кодируется в 5 байт. Это означает, что к последний блок содержит “00009”.
То есть получаем 2 блока:
HashInpu t1000009
См. также
Ссылки
- Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone (2001), chapter 9.
- Introduction to Modern Cryptography, by Jonathan Katz and Yehuda Lindell. Chapman and Hall/CRC Press, August 2007, page 134 (construction 4.13).