Структура Меркла

Структура Меркла-Дамгарда (англ. 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). Функция финализации часто строится с использованием функции сжатия.

Алгоритмы, реализующие структуру Меркла-Дамгарда

• Message-Digest algorithm 5 (MD5)
• SHA-1, SHA-2

Характеристики безопасности

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

• Дополнение до необходимой длины — когда атакующий найдет хотя бы одну коллизию, он очень легко может найти другие.
• Нахождение второго сообщения, дающего такой-же хеш (англ. second preimage attacks) для длинных сообщений всегда намного более эффективны, чем перебор (brute force). Атака для сообщения из 2^k блоков может быть выполнена за время k x 2^n/2+1 + 2^n-k+1. Важно, что сложность атаки находится между 2^n/2 и 2ⁿ когда сообщения длинные. Когда длина сообщения становится меньше, сложность приближается к 2ⁿ.
• Множественные коллизии (много сообщений имеют одинаковый хеш) могут быть найдены лишь незначительно большими усилиями, чем коллизии^[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

Wide pipe construction

The Wide pipe hash construction. The intermediate chaining values have been doubled.

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

См. также

• Хеширование
• Односторонняя функция

Ссылки

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

• 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).

Примечания

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.