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

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

История

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

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

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

Процесс хеширования состоит из нескольких этапов:

1. Дополнение (Padding): Исходное сообщение дополняется до длины, кратной размеру блока \( m \). Дополнение обычно включает в себя добавление единичного бита, затем нулевых битов, и в конце — длины исходного сообщения в битах (как правило, в виде 64-битного целого числа). Это гарантирует, что разные сообщения, даже если они отличаются только длиной, дадут разные хеши. Например, в SHA-256 сообщение дополняется так, чтобы его длина стала кратной 512 битам.

1. Инициализация: Задаётся начальное значение (Initialization Vector, IV) — константа фиксированного размера \( n \), которая служит первым состоянием. Для каждой хеш-функции это значение уникально (например, для SHA-256 это набор из 8 шестнадцатеричных чисел).

1. Итеративное сжатие: Сообщение разбивается на блоки \( M_1, M_2, \dots, M_k \) размером \( m \) бит. Затем последовательно применяется сжимающая функция:

• \( H_0 = IV \)
• \( H_i = f(H_{i-1}, M_i) \) для \( i = 1, 2, \dots, k \)

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

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

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

Однако конструкция имеет ряд известных недостатков, которые были выявлены со временем:

• Атака удлинения сообщения (Length Extension Attack): Зная хеш \( H(M) \) и длину сообщения \( M \), злоумышленник может вычислить хеш для сообщения \( M \parallel P \parallel X \), где \( P \) — дополнение, соответствующее длине \( M \), а \( X \) — произвольные данные, не зная самого \( M \). Это делает конструкцию уязвимой для некоторых протоколов аутентификации (например, когда хеш используется как MAC без ключа). Хеш-функции семейства SHA-2 подвержены этой атаке, в то время как SHA-3 — нет.

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

• Чувствительность к структуре: Атаки, такие как атака на основе дифференциального криптоанализа, могут быть более эффективными против конкретных сжимающих функций, построенных по этой схеме, что привело к компрометации MD5 и SHA-1.

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

Большинство классических хеш-функций, разработанных до 2010-х годов, используют конструкцию Меркла — Дамгора:

• MD5: Разработана Рональдом Ривестом в 1991 году. Размер хеша — 128 бит. В настоящее время считается криптографически нестойкой из-за найденных коллизий и не рекомендуется для использования в системах, требующих безопасности.
• SHA-1: Разработана АНБ США в 1995 году. Размер хеша — 160 бит. С 2017 года считается уязвимой для атак на коллизию (атака SHAttered). В России и многих других странах её использование для создания электронной подписи запрещено или ограничено.
• SHA-2: Семейство, включающее SHA-224, SHA-256, SHA-384, SHA-512 и другие. Разработано АНБ в 2001 году. Является стандартом безопасности во многих протоколах (TLS, SSH, PGP). Несмотря на теоретическую уязвимость к атаке удлинения сообщения, на практике считается стойким на данный момент.
• RIPEMD-160: Разработана в Европе как альтернатива SHA-1. Используется в некоторых криптовалютах (например, Bitcoin для создания адресов).

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

Основная критика конструкции Меркла — Дамгора связана с атакой удлинения сообщения и сложностью доказательства безопасности для некоторых режимов работы. В ответ на это были разработаны альтернативные конструкции:

• Губчатая конструкция (Sponge construction): Используется в SHA-3 (Keccak). Она не подвержена атаке удлинения сообщения и позволяет строить как хеш-функции, так и другие криптографические примитивы (например, потоковые шифры) на одной основе.
• Конструкция Хааста (HAIFA): Модификация Меркла — Дамгора, в которой в сжимающую функцию добавляется счётчик обработанных битов и соль (salt), что делает её устойчивой к атаке удлинения сообщения и некоторым другим атакам.
• Конструкция с широкой трубкой (Wide-pipe construction): Использует внутреннее состояние большего размера, чем итоговый хеш, что повышает устойчивость к некоторым классам атак.

Применение

Несмотря на недостатки, хеш-функции на основе конструкции Меркла — Дамгора (особенно SHA-2) широко применяются в:

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

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

• Ральф Меркл также известен как один из изобретателей криптосистемы с открытым ключом (криптосистема Меркла — Хеллмана) и концепции дерева Меркла, которое используется для эффективной верификации данных в блокчейне.
• Иван Дамгор, датский криптограф, внёс значительный вклад в теорию хеш-функций, но его работа долгое время оставалась менее известной, чем работа Меркла, пока не была переоткрыта в 1990-х годах.
• Название «Меркла — Дамгора» часто сокращается до «MD-конструкция», что не следует путать с хеш-функцией MD5, которая является лишь одной из реализаций этой конструкции.

Источники

• 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.
• Ferguson, N., Schneier, B., & Kohno, T. (2010). Cryptography Engineering: Design Principles and Practical Applications. Wiley.