Структура Меркла — Дамгора
Структура Меркла-Дамгарда (англ. Merkle–Damgård construction или англ. Merkle–Damgård hash function) — метод построения криптографических хеш-функций. Криптографическая хеш-функция должна преобразовывать входное сообщение произвольной длины в выходное сообщение фиксированной длины. Этого можно достичь путём разбиения входного сообщения на блоки одинакового размера и их последовательной обработки односторонней функцией сжатия, которая преобразовывает входное сообщение фиксированной длины в более короткое выходное сообщение фиксированной длины. Функция сжатия либо может быть специально построена для хеширования либо может представлять собой функцию блочного шифрования. Хеш-функция Меркла-Дамгарда разбивает входное сообщение на блоки и работает с ними по очереди с помощью функции сжатия, каждый раз принимая входной блок с выходным от предыдущего раунда.
Структура Меркла-Дамгарда была описана в докторской диссертации Ральфа Меркла[1]. Ральф Меркл и Иван Дамгор независимо показали: если функция сжатия устойчива к коллизиям, то и хеш-функция будет также устойчива.[2][3] Чтобы доказать устойчивость структуры, Меркл и Дамгор предложили дополнить сообщение блоком, который кодирует длину первоначального сообщения. Это называется упрочнение Меркла-Дамгарда (англ. Merkle–Damgård strengthening).
На рисунке односторонняя функция сжатия обозначена f, и преобразует два входных блока фиксированной длины в выходной блок того же размера, что и входные. Алгоритм начинает с начального значения — вектора инициализации (на рисунке — IV). Вектор инициализации — фиксированное значение (зависит от реализации алгоритма). Для каждого блока сообщения, функция сжатия f принимает результат предыдущего раунда и блок сообщения, и производит промежуточный результат. Последний блок дополняется нулями, если необходимо. Также, добавляется блок с информацией о длине целого сообщения (см. подробный пример ниже).
Для упрочнения хеша, последний результат иногда пропускают через функцию финализации (finalisation function). Функция финализации может использоваться для уменьшения размера выходного хеша, сжатием результата последней функции f в хеш более маленького размера, или чтобы гарантировать лучшее смешивание битов и усилить влияние небольшого изменения входного сообщения на хеш (Лавинный эффект, avalanche effect). Функция финализации часто строится с использованием функции сжатия.
Алгоритмы, реализующие структуру Меркла-Дамгарда
- Message-Digest algorithm 5 (MD5)
- SHA-1
- Семейство SHA-2
Характеристики безопасности
Популярность структуры Меркла-Дамгарда обусловлена тем, что, как было доказано, если односторонняя функция сжатия f устойчива к коллизиям, то и хеш-функция, построенная на её основе, будет также устойчива к коллизиям. Эта структура имеет несколько нежелательных свойств:
- Атака нахождения второго прообраза для длинных сообщений всегда намного более эффективна, чем полный перебор. Атака для сообщения из 2k блоков может быть выполнена за время k × 2n/2+1 + 2n-k+1. Важно, что сложность атаки находится между 2n/2 и 2n когда сообщения длинные. Когда длина сообщения становится меньше, сложность приближается к 2n.
- Множественные коллизии (много сообщений имеют одинаковый хеш) могут быть найдены лишь незначительно бо́льшими усилиями, чем коллизии[4].
- Атаки дополнением сообщения: При данном хеше H(X) неизвестного входного сообщения X, легко найти значение H(pad(X) || Y), где pad — функция дополнения. Это значит, что возможно найти хеши входных сообщений, связанных с X, даже когда X остаётся неизвестным.[5] Случайный оракул не имеет такой возможности, и это может привести к простым атакам даже на схемы, безопасность которых была доказана для модели случайного оракула[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
Из-за некоторых слабых мест структуры Меркла-Дамгарда, особенно проблемы, связанной с дополнением сообщения до необходимой длины, Стефан Лакс (Stefan Lucks) предложил использовать wide-pipe хеш[7] вместо структуры Меркла-Дамгарда. Wide-pipe хеш очень похож на структуру Меркла-Дамгарда, но имеет больше внутренних состояний, то есть битовая длина, использующаяся внутри алгоритма больше, чем выходная. Таким образом, последний этап — вторая функция сжатия, которая сжимает последнее внутреннее значение хеша в окончательное значение. SHA-224 и SHA-384 были получены из SHA-256 и SHA-512 соответственно, путём применения этого алгоритма.
См. также
Примечания
- ↑ R.C. Merkle. Secrecy, authentication, and public key systems. Stanford Ph.D. thesis 1979, pages 13-15.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ S. Lucks, Design Principles for Iterated Hash Functions, In: Cryptology ePrint Archive, Report 2004/253, 2004.
Ссылки
 | В статье есть список источников, но не хватает сносок. |
- 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).