Схема Меркля — Дамгора¶

Схема Меркля — Дамгора — это конструкция криптографических хеш-функций, позволяющая преобразовывать хеш-функцию, работающую с сообщениями фиксированной длины, в хеш-функцию, способную обрабатывать сообщения произвольной длины. Названа в честь Ральфа Меркля и Ивана Дамгора, которые независимо друг от друга предложили эту конструкцию в конце 1970-х — начале 1980-х годов. Схема лежит в основе многих широко используемых хеш-функций, включая MD5, SHA-1 и семейство SHA-2.

¶История

Идея построения хеш-функций на основе итеративного сжатия впервые была предложена Ральфом Мерклем в 1979 году в его докторской диссертации. Он описал метод, при котором сообщение разбивается на блоки, и каждый блок последовательно обрабатывается с использованием внутреннего состояния. В 1989 году Иван Дамгор независимо опубликовал работу, в которой формализовал эту конструкцию и доказал её криптографическую стойкость при условии, что используемая функция сжатия является коллизионно-стойкой. С тех пор схема Меркля — Дамгора стала стандартной парадигмой для проектирования хеш-функций.

¶Принцип работы

Схема Меркля — Дамгора состоит из нескольких этапов:

1. Дополнение (падинг): Исходное сообщение произвольной длины дополняется до длины, кратной размеру блока, обрабатываемого функцией сжатия. Обычно дополнение включает бит «1», затем необходимое количество нулевых битов, а в конце — длину исходного сообщения в битах, закодированную фиксированным числом байтов (например, 64 или 128 бит). Это гарантирует, что сообщения разной длины будут иметь разные хеш-значения.

1. Разбиение на блоки: Дополненное сообщение разбивается на последовательные блоки фиксированной длины (например, 512 бит для MD5 и SHA-1, 1024 бит для SHA-256).

1. Инициализация: Задаётся начальное значение внутреннего состояния (IV — Initialization Vector), которое является константой, определённой в спецификации хеш-функции.

1. Итеративное сжатие: Каждый блок сообщения последовательно обрабатывается функцией сжатия \( f \), которая принимает на вход текущее состояние (размером, например, 160 бит для SHA-1) и очередной блок сообщения, и выдаёт новое состояние. Формально: \( h_i = f(h_{i-1}, m_i) \), где \( h_0 = IV \), \( m_i \) — i-й блок сообщения.

1. Финализация: После обработки всех блоков полученное состояние \( h_n \) (или его часть) выдаётся в качестве хеш-значения сообщения. В некоторых функциях финализация может включать дополнительные преобразования, например, усечение или повторное сжатие.

¶Свойства и криптостойкость

Основное свойство схемы Меркля — Дамгора заключается в том, что если функция сжатия \( f \) является коллизионно-стойкой (то есть для неё вычислительно сложно найти два различных входа, дающих одинаковый выход), то и вся хеш-функция, построенная по этой схеме, будет коллизионно-стойкой. Это было доказано Дамгором и Мерклем. Однако на практике это свойство выполняется при условии, что дополнение корректно и включает длину сообщения.

Схема Меркля — Дамгора обладает рядом недостатков, которые были выявлены со временем:

• Уязвимость к атакам удлинения сообщения (length extension attack): Зная хеш \( H(M) \) для сообщения \( M \), можно вычислить хеш для сообщения \( M \| P \| X \), где \( P \) — дополнение, соответствующее длине \( M \), а \( X \) — произвольное дополнительное сообщение, не зная самого \( M \). Это делает схему непригодной для некоторых криптографических протоколов, например, для построения кодов аутентификации сообщений (MAC) без дополнительной модификации.

• Чувствительность к коллизиям в функции сжатия: Если найдена коллизия для функции сжатия, то можно построить коллизию для всей хеш-функции. Это было продемонстрировано на примере MD5 и SHA-1.

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

¶Примеры хеш-функций на основе схемы

Схема Меркля — Дамгора использована в следующих широко распространённых хеш-функциях:

• MD5 (размер хеша 128 бит, размер блока 512 бит) — разработана Роном Ривестом в 1991 году. В настоящее время считается криптографически нестойкой из-за обнаруженных коллизий.
• SHA-1 (размер хеша 160 бит, размер блока 512 бит) — разработана АНБ США в 1995 году. С 2017 года рекомендуется не использовать из-за успешных атак на коллизии.
• SHA-2 (включает SHA-224, SHA-256, SHA-384, SHA-512) — разработана АНБ в 2001 году. Размеры блоков: 512 бит для SHA-256 и 1024 бит для SHA-512. На 2025 год считается криптостойкой, но постепенно вытесняется SHA-3.

¶Модификации и альтернативы

Для устранения недостатков схемы Меркля — Дамгора были предложены различные модификации:

• HAIFA (HAsh Iterative FrAmework) — предложена в 2006 году, включает счётчик блоков и соль в качестве дополнительных входов функции сжатия, что предотвращает атаки удлинения.
• Широкопипельная конструкция (wide-pipe) — использует внутреннее состояние большего размера, чем выходной хеш, что повышает устойчивость к коллизиям.
• Конструкция с удвоением (double-pipe) — разновидность широкопипельной, где состояние вдвое больше хеша.

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

¶Применение

Хеш-функции на основе схемы Меркля — Дамгора широко применяются в:

• Цифровых подписях — для сокращения размера подписываемых данных.
• Проверке целостности данных — например, в протоколах загрузки файлов (MD5, SHA-1).
• Хранении паролей — хотя для этой цели теперь рекомендуется использовать специализированные функции (bcrypt, Argon2), исторически применялись MD5 и SHA-1.
• Криптовалютах — в биткойне используется SHA-256, построенный по схеме Меркля — Дамгора, для хеширования блоков и транзакций.

¶Критика

Основная критика схемы Меркля — Дамгора связана с её уязвимостью к атакам удлинения сообщения, что делает её непригодной для некоторых криптографических приложений без дополнительных мер (например, использования HMAC). Кроме того, с развитием вычислительной техники и криптоанализа многие функции на этой схеме (MD5, SHA-1) были скомпрометированы, что привело к переходу на более стойкие алгоритмы, такие как SHA-2 и SHA-3. Тем не менее, схема остаётся важной исторической вехой в криптографии и продолжает использоваться в современных системах, где требуется высокая производительность и проверенная стойкость.

¶Источники

• Меркль, Ральф. «Secrecy, authentication, and public key systems». Докторская диссертация, Стэнфордский университет, 1979.
• Дамгор, Иван. «A design principle for hash functions». Advances in Cryptology — CRYPTO’89, 1989.
• Шнайер, Брюс. «Прикладная криптография». 2-е издание, 1996.
• Стандарты NIST: FIPS 180-4 (Secure Hash Standard), FIPS 202 (SHA-3).
• Менезес, Альфред; ван Ооршот, Пол; Ванстон, Скотт. «Handbook of Applied Cryptography». CRC Press, 1996.