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

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

История

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

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

Основная идея заключается в итеративном применении сжимающей функции \( f \) к последовательности блоков сообщения. Процесс можно разделить на три этапа: дополнение сообщения, разбиение на блоки и итеративное сжатие.

Дополнение сообщения (Padding)

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

1. К сообщению добавляется бит «1».
2. Затем добавляется необходимое количество нулевых битов.
3. В конце добавляется блок (обычно 64 или 128 бит), содержащий исходную длину сообщения в битах.

Это гарантирует, что два разных сообщения, даже если они различаются только длиной, после дополнения будут различаться.

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

После дополнения сообщение разбивается на блоки \( M_1, M_2, \ldots, M_n \) одинаковой длины (например, 512 или 1024 бита).

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

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

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

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

Однако со временем были выявлены и недостатки:

Атаки удлинения сообщения (Length Extension Attack)

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

Атаки на сжимающую функцию

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

Параллелизация

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

Модификации и альтернативы

Для устранения недостатков были разработаны различные модификации:

Широкая труба (Wide Pipe)

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

Ха-Эф-Эс (HAIFA — HAsh Iterative FrAmework)

Предложенная в 2006 году, эта конструкция добавляет к входу сжимающей функции номер блока и соль (salt), что делает её более устойчивой к атакам удлинения сообщения и позволяет эффективно использовать параллельные вычисления.

Губчатая конструкция (Sponge Construction)

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

Применение

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

• MD5 (разработана Рональдом Ривестом в 1991 году) — в настоящее время считается небезопасной для криптографических целей, но всё ещё используется для контроля целостности в некоторых системах.
• SHA-1 (разработана АНБ в 1995 году) — официально признана устаревшей и не рекомендуется к использованию после успешной демонстрации коллизий в 2017 году.
• SHA-256 и SHA-512 (семейство SHA-2, разработаны АНБ в 2001 году) — в настоящее время являются стандартом де-факто для многих криптографических приложений, включая цифровые подписи, сертификаты TLS и блокчейн (например, в биткойне).

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

• Ральф Меркл, один из авторов конструкции, также известен как создатель криптосистемы Меркла — Хеллмана (одна из первых систем с открытым ключом) и как один из пионеров концепции блокчейна (дерево Меркла).
• Иван Дамгор, датский криптограф, внёс значительный вклад в теорию хеш-функций, но его имя в русскоязычной литературе иногда транскрибируется как Дамгорд или Дамгард. В англоязычных источниках конструкция называется Merkle–Damgård construction.
• Несмотря на свои недостатки, конструкция Меркла — Дамгора остаётся одной из самых изученных и хорошо понятых в криптографии. Её анализ послужил основой для разработки более совершенных конструкций, таких как SHA-3.

Источники

• Меркл, Р. «Secrecy, authentication, and public key systems» (докторская диссертация, 1979).
• Дамгор, И. «A design principle for hash functions» (1989).
• Шнайер, Б. «Прикладная криптография» (глава о хеш-функциях).
• Стандарты NIST (FIPS PUB 180-4 для SHA-2).
• Обзорные статьи по криптографическим хеш-функциям в открытых источниках.