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

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

История

Концепция была независимо предложена двумя исследователями в конце 1970-х годов. Ральф Меркл (Ralph Merkle) в 1979 году в своей докторской диссертации описал метод построения хеш-функций на основе блочных шифров, который позже получил название «схема Меркля — Дамгора». В том же году Иван Дамгор (Ivan Damgård) опубликовал работу, в которой доказал, что если функция сжатия является коллизионно-стойкой, то и вся хеш-функция, построенная по данной схеме, также будет коллизионно-стойкой. Это доказательство стало фундаментальным для криптографии и обеспечило теоретическую основу для многих последующих разработок.

Устройство

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

После дополнения сообщение разбивается на блоки фиксированной длины (например, 512 или 1024 бита). Далее запускается итеративный процесс:

1. Устанавливается начальное значение (initialization vector, IV) — фиксированный вектор, определённый спецификацией хеш-функции.
2. Первый блок сообщения подаётся на вход функции сжатия вместе с IV.
3. Результат работы функции сжатия становится новым состоянием, которое подаётся на вход вместе со следующим блоком сообщения.
4. Процесс повторяется для всех блоков сообщения.
5. После обработки последнего блока полученное состояние (обычно после дополнительного преобразования) выдаётся в качестве итогового хеш-значения.

Функция сжатия (compression function) принимает два входных аргумента: текущее состояние (размером, равным размеру хеша) и один блок сообщения. На выходе она выдаёт новое состояние того же размера. Внутреннее устройство функции сжатия может быть различным — например, в SHA-256 она основана на комбинации операций сложения, битовых сдвигов, XOR и нелинейных функций.

Свойства

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

Однако данная конструкция имеет и ряд недостатков:

• Уязвимость к атакам удлинения сообщения (length extension attack). Зная хеш сообщения H(M), злоумышленник может вычислить хеш сообщения M || pad(M) || X, не зная самого M. Это свойство позволяет подделывать аутентификационные коды (MAC) в некоторых протоколах, если они построены наивно. Данная атака возможна из-за того, что итоговое хеш-значение является просто внутренним состоянием после обработки последнего блока.
• Отсутствие устойчивости к коллизиям второго прообраза в некоторых вариантах. Хотя коллизионная стойкость доказана при условии стойкости функции сжатия, на практике были найдены коллизии для MD5 и SHA-1, что привело к их выводу из эксплуатации.
• Ограниченная производительность при параллельной обработке, так как каждый блок зависит от результата предыдущего.

Применение

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

• MD5 (Message Digest 5) — разработана Рональдом Ривестом в 1991 году. Размер хеша — 128 бит. В настоящее время считается небезопасной из-за найденных коллизий.
• SHA-1 (Secure Hash Algorithm 1) — разработана АНБ США в 1995 году. Размер хеша — 160 бит. С 2017 года рекомендуется к выводу из эксплуатации из-за коллизионных атак.
• SHA-2 (семейство: SHA-224, SHA-256, SHA-384, SHA-512) — разработана АНБ США в 2001 году. Размер хеша — от 224 до 512 бит. На данный момент считается безопасной и широко применяется в протоколах TLS, SSL, SSH, IPsec, а также в системах электронной подписи и блокчейне.
• RIPEMD-160 — разработана в рамках проекта RIPE (EU) в 1996 году. Размер хеша — 160 бит. Используется в криптовалюте Bitcoin наряду с SHA-256.

Критика и альтернативы

Недостатки структуры Меркла — Дамгора, особенно уязвимость к атакам удлинения сообщения, привели к разработке альтернативных конструкций. Наиболее известной является схема губки (sponge construction), используемая в хеш-функции SHA-3 (Keccak), которая была выбрана в результате конкурса NIST в 2012 году. Губка не подвержена атакам удлинения сообщения, обеспечивает лучшую параллелизацию и имеет более гибкие параметры.

Также существуют конструкции на основе блочных шифров (например, Matyas-Meyer-Oseas, Miyaguchi-Preneel), которые также могут быть использованы для построения хеш-функций, но они менее распространены.

Интересные факты

• Доказательство коллизионной стойкости, предложенное Дамгором, является одним из первых строгих доказательств в криптографии, связывающих стойкость хеш-функции со стойкостью её компонента.
• В 2005 году китайские криптографы Ван Сяоюнь и её коллеги опубликовали атаки на MD5 и SHA-1, которые позволили находить коллизии за практически приемлемое время. Это стало одним из важнейших событий в криптографии начала XXI века.
• Структура Меркла — Дамгора также используется в некоторых системах контроля целостности данных (например, в файловых системах ZFS и Btrfs) для проверки целостности блоков данных.

Источники

• Merkle, R. C. (1979). Secrecy, authentication, and public key systems. Stanford Ph.D. thesis.
• Damgård, I. (1989). A design principle for hash functions. Advances in Cryptology — CRYPTO'89.
• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography.
• NIST FIPS 180-4: Secure Hash Standard (SHS).
• Wang, X., Yu, H. (2005). How to Break MD5 and Other Hash Functions. EUROCRYPT 2005.