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

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

История и предпосылки появления

До появления схемы Меркла — Дамгора существовала потребность в криптографически стойких хеш-функциях, которые могли бы преобразовывать входные данные произвольной длины в выходное значение фиксированной длины (например, 128, 160 или 256 бит). Прямое применение сжимающей функции, работающей с блоками фиксированного размера, к сообщению произвольной длины было невозможно. В 1979 году Ральф Меркл в своей докторской диссертации, посвящённой криптографическим протоколам и обеспечению безопасности, формализовал метод, который позволял обрабатывать сообщения любой длины с использованием только сжимающей функции. В 1989 году Иван Дамгор в своей работе «A Design Principle for Hash Functions» независимо описал аналогичную конструкцию. Обе работы показали, что если сжимающая функция является защищённой от коллизий (то есть никто не может найти два разных блока, дающих одинаковый выход), то сама хеш-функция, построенная по схеме Меркла — Дамгора, также будет защищена от коллизий для сообщений произвольной длины.

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

Схема Меркла — Дамгора работает итеративно, обрабатывая входное сообщение по частям (блокам). Процесс обычно состоит из трёх основных этапов: дополнение (padding), разбиение на блоки и итерационное сжатие.

Дополнение (Padding)

Поскольку сжимающая функция может обрабатывать только блоки фиксированного размера (например, 512 или 1024 бит), исходное сообщение произвольной длины необходимо дополнить до размера, кратного размеру блока. Дополнение выполняется таким образом, чтобы однозначно определить исходную длину сообщения. В стандартной конструкции Меркла — Дамгора к концу сообщения сначала добавляется единичный бит, затем — необходимое количество нулевых битов, и в самом конце — блок, содержащий длину исходного сообщения в битах (обычно в виде 64-битного или 128-битного числа). Это так называемое дополнение MD (Merkle-Damgård strengthening). Такая схема гарантирует, что, например, сообщение «100» и сообщение «1» с последующим дополнением до того же размера не дадут одинакового хеша.

Разбиение на блоки

После дополнения сообщение делится на последовательность блоков одинакового размера: \( M_1, M_2, ..., M_n \), где \( M_n \) — последний блок, который содержит информацию о длине исходного сообщения.

Итерационное сжатие

На этом этапе применяется сжимающая функция \( f \), которая принимает на вход два аргумента:

• внутреннее состояние (chaining value) — результат предыдущей итерации;
• блок входного сообщения \( M_i \).

Начальное внутреннее состояние (initialization vector, IV) задаётся фиксированной константой (для каждой хеш-функции она своя). Процесс выглядит следующим образом:

1. \( H_0 = IV \) (начальное значение).
2. Для каждого блока \( M_i \) от \( i = 1 \) до \( n \):

• \( H_i = f(H_{i-1}, M_i) \).

Результатом работы хеш-функции после обработки последнего блока является итоговое значение \( H_n \), которое может быть при необходимости обрезано или преобразовано (в зависимости от спецификации функции).

Устойчивость к коллизиям

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

Применение в криптографии

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

• MD4: разработан Рональдом Ривестом в 1990 году, один из первых, но позже были найдены уязвимости.
• MD5: разработан в 1991 году, долгое время был стандартным для проверки целостности файлов и паролей, но к концу 2000-х годов коллизии стали находить практически, после чего его использование резко сократилось.
• SHA-0: предшественник SHA-1, выпущенный в 1993 году, но из-за дефекта в сжимающей функции был быстро отозван.
• SHA-1: разработан Агентством национальной безопасности (АНБ) США и опубликован в 1995 году. Широко применялся до 2017 года, когда была опубликована практическая коллизионная атака.
• SHA-2: семейство алгоритмов (SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256), все из которых построены на схеме Меркла — Дамгора. На данный момент (начало 2020-х годов) считаются безопасными и являются государственным стандартом хеширования в России (ГОСТ Р 34.11-2012 при этом использует другую структуру — на основе блочного шифра, но SHA-256 и SHA-512 широко применяются в международных протоколах).

Недостатки и критика

Несмотря на свою фундаментальность, схема Меркла — Дамгора имеет ряд теоретических и практических недостатков, которые привели к поиску альтернативных конструкций, таких как Sponge-конструкция (применяется в SHA-3).

Атаки расширения длины (Length extension attack)

Это одна из самых известных уязвимостей, присущих именно схеме Меркла — Дамгора. Если злоумышленник знает хеш \( H(M) \) сообщения \( M \) (но не само \( M \)) и длину \( M \), он может вычислить хеш сообщения \( M' = M \ || \ P \ || \ X \), где \( P \) — блок дополнения сообщения \( M \), а \( X \) — произвольные данные, которые злоумышленник добавляет. Для этого злоумышленнику нужно просто продолжить итерационный процесс, используя известное значение \( H(M) \) в качестве нового начального состояния сжимающей функции. Это делает функцию уязвимой в некоторых протоколах аутентификации, например, в HMAC или при подписи хеша.

Практические коллизии

Хотя на бумаге схема наследует устойчивость от сжимающей функции, на практике у многих реализаций (MD4, MD5, SHA-0, SHA-1) были найдены уязвимости именно в самой сжимающей функции. Атаки, такие как дифференциальный криптоанализ, позволили находить коллизии для SHA-1 значительно быстрее, чем теоретический предел, что дискредитировало конкретные алгоритмы, но не саму конструкцию.

Отсутствие недетерминированного входа

Схема Меркла — Дамгора является полностью детерминированной. Это сделало её математически простой, но лишило возможности встраивания дополнительных механизмов, таких как замена начального вектора для разных целей без изменения сообщения.

Альтернативы и современное состояние

Основной альтернативой на сегодняшний день является Sponge-конструкция (губчатая конструкция), используемая в семействе SHA-3 (стандарт Keccak). В ней данные поглощаются блок за блоком, а затем выжимаются в выходные данные любой желаемой длины. Она лишена атаки расширения длины и более гибка. Тем не менее, SHA-2 (Меркла — Дамгора) продолжает широко использоваться и является криптографически стойкой функцией при правильном применении. Для протоколов, устойчивых к атакам расширения длины, часто используется HMAC (Hash-based message authentication code), который как раз и был разработан для защиты от этой атаки.

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

Источники

• Меркл, Р. (1979). Secrecy, Authentication, and Public Key Systems (докторская диссертация, Стэнфордский университет).
• Дамгор, И. (1989). A Design Principle for Hash Functions (Advances in Cryptology — CRYPTO ’89, Springer).
• Ривест, Р. (1992). The MD5 Message-Digest Algorithm (RFC 1321).
• Агентство национальной безопасности США. (1995). Secure Hash Standard (FIPS PUB 180-1).
• Национальный институт стандартов и технологий (NIST). (2015). SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions (FIPS PUB 202).