Структура Меркла — Дамгарда

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Структура Меркла-Дамгарда (англ. Merkle–Damgård construction или англ. Merkle–Damgård hash function) — метод построения криптографических хеш-функций. Криптографическая хеш-функция должна преобразовывать входное сообщение произвольной длины в выходное сообщение фиксированной длины. Этого можно достичь путём разбиения входного сообщения на блоки одинакового размера и их последовательной обработки односторонней функцией сжатия, которая преобразовывает входное сообщение фиксированной длины в более короткое выходное сообщение фиксированной длины. Функция сжатия либо может быть специально построена для хеширования либо может представлять собой функцию блочного шифрования. Хеш-функция Меркла-Дамгарда разбивает входное сообщение на блоки и работает с ними по очереди с помощью функции сжатия, каждый раз принимая входной блок с выходным от предыдущего раунда.

Структура Меркла-Дамгарда была описана в докторской диссертации Ральфа Меркла[1]. Ральф Меркл и Иван Дамгор независимо показали: если функция сжатия устойчива к коллизиям, то и хеш-функция будет также устойчива.[2][3] Чтобы доказать устойчивость структуры, Меркл и Дамгор предложили дополнить сообщение блоком, который кодирует длину первоначального сообщения. Это называется упрочнение Меркла-Дамгарда (англ. Merkle–Damgård strengthening).

Merkle-Damgård hash construction

На рисунке односторонняя функция сжатия обозначена f, и преобразует два входных блока фиксированной длины в выходной блок того же размера, что и входные. Алгоритм начинает с начального значения — вектора инициализации (на рисунке — IV). Вектор инициализации — фиксированное значение (зависит от реализации алгоритма). Для каждого блока сообщения, функция сжатия f принимает результат предыдущего раунда и блок сообщения, и производит промежуточный результат. Последний блок дополняется нулями, если необходимо. Также, добавляется блок с информацией о длине целого сообщения (см. подробный пример ниже).

Для упрочнения хеша, последний результат иногда пропускают через функцию финализации (finalisation function). Функция финализации может использоваться для уменьшения размера выходного хеша, сжатием результата последней функции f в хеш более маленького размера, или чтобы гарантировать лучшее смешивание битов и усилить влияние небольшого изменения входного сообщения на хеш (Лавинный эффект, avalanche effect). Функция финализации часто строится с использованием функции сжатия.

Алгоритмы, реализующие структуру Меркла-Дамгарда[править | править вики-текст]

Характеристики безопасности[править | править вики-текст]

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

  • Дополнение до необходимой длины — когда атакующий найдет хотя бы одну коллизию, он очень легко может найти другие.
  • Нахождение второго сообщения, дающего такой же хеш (англ. second preimage attacks) для длинных сообщений всегда намного более эффективны, чем перебор (brute force). Атака для сообщения из 2k блоков может быть выполнена за время k x 2n/2+1 + 2n-k+1. Важно, что сложность атаки находится между 2n/2 и 2n когда сообщения длинные. Когда длина сообщения становится меньше, сложность приближается к 2n.
  • Множественные коллизии (много сообщений имеют одинаковый хеш) могут быть найдены лишь незначительно большими усилиями, чем коллизии[4].
  • Атаки дополнением сообщения: При данном хеше H(X) неизвестного входного сообщения X, легко найти значение H(pad(X)||Y), где pad — функция дополнения . Это значит, что возможно найти хеши входных сообщений, связанных с X, даже когда X остается неизвестным.[5] Random oracle не имеет такой возможности, и это может привести к простым атакам даже на схемы, безопасность которых была доказана для модели атак random oracle[6].

Пример дополнения сообщения[править | править вики-текст]

Для того, чтобы передать сообщение в функцию сжатия, необходимо дополнить последний блок до полного определёнными данными (обычно нулями).

Например, предположим, сообщение - «HashInput» и размер блока для функции сжатия - 8 байт (64 бит). В таком случае, получится 2 блока:
HashInpu t0000000

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

В нашем примере, например, сообщение «HashInput00» , будет разделено на такие же блоки, что и первоначальное сообщение «HashInput».

Чтобы этого избежать, первый бит добавляемых данных, должен быть изменен. Так как заполнитель обычно состоит из нулей, первый бит заполнителя должен быть заменён на «1».

В нашем примере, мы получим следующее:
HashInpu t1000000

Чтобы усилить хеш, можно добавить длину сообщения в дополнительном блоке

В нашем примере мы получим три блока:
HashInpu t1000000 00000009

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

Например, возьмем в нашем примере, что длина сообщения кодируется в 5 байт. Это означает, что последний блок содержит «00009».

То есть получаем 2 блока:

HashInpu t1000009

Модификации[править | править вики-текст]

HAIFA[править | править вики-текст]

В 2006 году был предложен подход HAIFA, при котором Структура Меркла — Дамгарда немного модифицируется. В каждую функцию сжатия дополнительно к блоку сообщения подается текущее смещение в входном файле и, опционально, некоторая соль.

Wide pipe construction[править | править вики-текст]

Пример Wide pipe. Промежуточное состояние в два раза больше, чем выход хеш-функции.

Из-за некоторых слабых мест структуры Меркла-Дамгарда, особенно проблемы, связанной с дополнением сообщения до необходимой длины, Стефан Лакс (Stefan Lucks) предложил использовать wide-pipe хеш[7] вместо структуры Меркла-Дамгарда. Wide-pipe хеш очень похож на структуру Меркла-Дамгарда, но имеет больше внутренних состояний, то есть битовая длина, использующаяся внутри алгоритма больше, чем выходная. Таким образом, последний этап — вторая функция сжатия, которая сжимает последнее внутреннее значение хеша в окончательное значение. SHA-224 и SHA-384 были получены из SHA-256 и SHA-512 соответственно, путём применения этого алгоритма.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. R.C. Merkle. Secrecy, authentication, and public key systems. Stanford Ph.D. thesis 1979, pages 13-15.
  2. R.C. Merkle. A Certified Digital Signature. In Advances in Cryptology — CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 218—238.
  3. I. Damgård. A Design Principle for Hash Functions. In Advances in Cryptology — CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 416—427.
  4. Antoine Joux. Multicollisions in iterated hash functions. Application to cascaded construction. In Advances in Cryptology — CRYPTO '04 Proceedings, Lecture Notes in Computer Science, Vol. 3152, M. Franklin, ed, Springer-Verlag, 2004, pp. 306—316.
  5. Yevgeniy Dodis, Thomas Ristenpart, Thomas Shrimpton. Salvaging Merkle-Damgård for Practical Applications. Preliminary version in Advances in Cryptology — EUROCRYPT '09 Proceedings, Lecture Notes in Computer Science Vol. 5479, A. Joux, ed, Springer-Verlag, 2009, pp. 371—388.
  6. J.S. Coron, Y. Dodis, C. Malinaud, and P. Puniya. Merkle-Damgård Revisited: How to Construct a Hash Function. Advances in Cryptology — CRYPTO '05 Proceedings, Lecture Notes in Computer Science, Vol. 3621, Springer-Verlag, 2005, pp. 21-39.
  7. S. Lucks, Design Principles for Iterated Hash Functions, In: Cryptology ePrint Archive, Report 2004/253, 2004.

Ссылки[править | править вики-текст]