Конструкция Меркла-Дамгора

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

История

Идея построения хеш-функции из сжимающей функции, которая обрабатывает блоки данных фиксированного размера, восходит к ранним работам по криптографии. В 1979 году Ральф Меркл в своей докторской диссертации «Secrecy, Authentication, and Public Key Systems» описал метод, который он назвал «мета-методом» (meta-method). Он предложил использовать итеративное применение сжимающей функции к последовательным блокам сообщения, при этом результат предыдущего шага подавался на вход следующего.

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

Конструкция Меркла-Дамгора стала стандартом де-факто для проектирования хеш-функций на протяжении десятилетий. Она была использована в алгоритмах MD4, MD5, SHA-0, SHA-1 и SHA-2. Однако в конце 2000-х годов были обнаружены теоретические уязвимости, связанные с атаками на удлинение сообщения (length extension attack), что привело к разработке альтернативных конструкций, таких как губчатая конструкция (sponge construction), используемая в SHA-3.

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

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

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

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

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

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

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

Устанавливается начальное значение (initialization vector, IV) — константа фиксированного размера, равного размеру выходного хеша. Это значение является входом для первой сжимающей функции.

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

Сжимающая функция \( f \) принимает два аргумента: текущее состояние \( H_i \) (размером, равным размеру хеша) и очередной блок сообщения \( M_{i+1} \). Результатом является новое состояние \( H_{i+1} \). Процесс повторяется для всех блоков:

\[ H_0 = IV \] \[ H_{i+1} = f(H_i, M_{i+1}) \quad \text{для } i = 0, 1, \ldots, n-1 \]

Вывод

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

Свойства и безопасность

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

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

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

Применение

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

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

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

Основная критика конструкции Меркла-Дамгора связана с атакой на удлинение сообщения. Эта уязвимость привела к разработке альтернативных схем, которые лишены этого недостатка. Наиболее известная альтернатива — губчатая конструкция (sponge construction), используемая в SHA-3 (Keccak). В губчатой конструкции сообщение «впитывается» в состояние, а затем хеш «выжимается» из него, что делает атаки на удлинение сообщения невозможными.

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

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

• Конструкция Меркла-Дамгора была настолько влиятельной, что в течение многих лет все новые хеш-функции проектировались именно по этой схеме.
• Ральф Меркл также известен как соавтор криптосистемы Меркла-Хеллмана и изобретатель деревьев Меркла, широко используемых в блокчейне.
• Иван Дамгор, помимо работы над хеш-функциями, внёс вклад в теорию кодирования и криптографию.

Источники

• 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. In: Brassard, G. (eds) Advances in Cryptology — CRYPTO’ 89 Proceedings. CRYPTO 1989. Lecture Notes in Computer Science, vol 435. Springer, New York, NY.
• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
• Ferguson, N., Schneier, B., Kohno, T. (2010). Cryptography Engineering: Design Principles and Practical Applications. Wiley.