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

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

История

Идея построения хеш-функций с переменной длиной входа на основе фиксированной сжимающей функции впервые была предложена Ральфом Мерклом в 1979 году в его докторской диссертации «Secrecy, Authentication, and Public Key Systems». Меркл описал метод, который он назвал «мета-методом» (meta-method) для построения хеш-функций. В 1989 году Иван Дамгор опубликовал работу «A Design Principle for Hash Functions», в которой независимо сформулировал аналогичную конструкцию и доказал её стойкость при условии устойчивости к коллизиям базовой сжимающей функции. С тех пор конструкция получила название «Структура Меркла-Дамгора» (Merkle–Damgård construction).

В 1990-е и 2000-е годы эта конструкция стала стандартом де-факто для проектирования хеш-функций. На ней были основаны MD4, MD5, SHA-0, SHA-1, а также всё семейство SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512). Однако после серии успешных атак на MD5 и SHA-1, а также теоретических работ, выявивших уязвимости конструкции (например, атаки удлинения сообщения), в конкурсе SHA-3 (2007–2012) победила альтернативная конструкция — губчатая функция (Keccak).

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

Структура Меркла-Дамгора решает задачу преобразования сообщения произвольной длины в хеш-значение фиксированной длины (например, 256 бит для SHA-256). Процесс состоит из нескольких этапов.

1. Дополнение (падинг)

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

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

Дополненное сообщение разбивается на последовательные блоки фиксированной длины (например, 512 бит для SHA-256). Обозначим их как \( M_1, M_2, \ldots, M_n \).

3. Инициализация

Задаётся начальное значение (initialization vector, IV) — константа фиксированной длины, которая является стартовым состоянием для первого блока.

4. Итеративное сжатие

Каждый блок сообщения \( M_i \) обрабатывается сжимающей функцией \( f \), которая принимает два аргумента: текущее состояние \( H_{i-1} \) (длиной, равной выходной длине хеша) и блок сообщения \( M_i \). Результат — новое состояние \( H_i \): \[ H_i = f(H_{i-1}, M_i) \] Для первого блока \( H_0 = IV \). Процесс повторяется для всех блоков.

5. Вывод

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

Свойства и стойкость

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

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

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

Применение

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

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

Альтернативы

Из-за выявленных недостатков структуры Меркла-Дамгора (особенно атаки удлинения сообщения) были разработаны альтернативные конструкции:

• Губчатая функция (sponge construction) — используется в SHA-3 (Keccak). Позволяет получать хеш произвольной длины и устойчива к атаке удлинения.
• HAIFA (HAsh Iterative FrAmework) — модификация Меркла-Дамгора, в которой в сжимающую функцию добавляется счётчик обработанных битов и соль, что устраняет атаку удлинения.
• Конструкция Davies-Meyer — используется внутри некоторых хеш-функций (например, в SHA-2) для построения сжимающей функции на основе блочного шифра.

Критика

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

Источники

• Merkle, R. C. (1979). Secrecy, Authentication, and Public Key Systems. Ph.D. dissertation, Stanford University.
• 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. CRC Press.
• National Institute of Standards and Technology (NIST). FIPS PUB 180-4: Secure Hash Standard (SHS). 2015.
• Wang, X., Yu, H. (2005). «How to Break MD5 and Other Hash Functions». Advances in Cryptology — EUROCRYPT 2005.