Семейство MD4

Семейство MD4 — это группа криптографических хеш-функций, разработанных Рональдом Ривестом в 1990 году. Основная функция семейства, MD4 (Message Digest 4), предназначена для преобразования входных данных произвольной длины в фиксированное 128-битное хеш-значение (дайджест). Семейство включает в себя оригинальную функцию MD4, а также её модификации и последовательные версии, такие как MD5 и MD2, которые легли в основу многих стандартов безопасности. MD4 считается устаревшей и небезопасной для криптографических целей из-за выявленных уязвимостей, однако её алгоритмы широко использовались в протоколах аутентификации и проверки целостности данных.

История

Разработка и публикация

MD4 была разработана Рональдом Ривестом, профессором Массачусетского технологического института (MIT), и впервые опубликована в 1990 году. Она была создана для замены более ранних хеш-функций, таких как MD2, и предназначалась для использования в протоколах цифровых подписей и проверки целостности файлов. Алгоритм был опубликован в виде технического отчёта MIT и впоследствии включён в стандарт RFC 1186 (1990 год) и его обновление RFC 1320 (1992 год). В основе MD4 лежала идея быстрого вычисления хеша на 32-битных процессорах, что делало её эффективной для программной реализации.

Распространение и криптоанализ

В начале 1990-х годов MD4 получила широкое распространение в системах UNIX (например, в протоколах аутентификации NTLM и SMB) и в некоторых криптографических библиотеках. Однако уже в 1991 году Ден Боер и Антон Босселаерс обнаружили слабые места в алгоритме, а в 1995 году Ханс Доббертин продемонстрировал первую практическую атаку на коллизию (нахождение двух разных сообщений с одинаковым хешем). Впоследствии были разработаны более эффективные атаки, такие как атака Ван Сяоюня и Юя Хунбо (2004 год), которая позволяла найти коллизию для MD4 за несколько секунд на обычном компьютере. Это привело к отказу от использования MD4 в новых системах безопасности.

Наследие

MD4 послужила основой для создания более стойкой хеш-функции MD5, которая была опубликована Ривестом в 1992 году. MD5 также впоследствии была признана небезопасной, но её алгоритм базируется на тех же принципах, что и MD4. Кроме того, некоторые элементы MD4 были использованы в разработке стандарта SHA-1 (Secure Hash Algorithm 1), хотя последний имеет более сложную структуру.

Алгоритм работы

Общая схема

MD4 обрабатывает входные данные блоками по 512 бит (64 байта). Если длина сообщения не кратна 512 битам, оно дополняется (паддинг) до нужной длины. Процесс включает три основных этапа:

1. Дополнение сообщения: к сообщению добавляется единичный бит, затем нулевые биты до тех пор, пока длина не станет на 64 бита меньше, чем кратное 512. В конце добавляется 64-битное представление исходной длины сообщения.
2. Инициализация: четыре 32-битных регистра (A, B, C, D) инициализируются фиксированными значениями: A = 0x67452301, B = 0xEFCDAB89, C = 0x98BADCFE, D = 0x10325476.
3. Обработка блоков: каждый 512-битный блок проходит через три раунда функций сжатия, каждый из которых состоит из 16 шагов. В каждом раунде используются нелинейные булевы функции (F, G, H) и константы, зависящие от номера шага.

Функции раундов

• Раунд 1: функция F(X, Y, Z) = (X & Y) | (~X & Z). Выполняется 16 шагов.
• Раунд 2: функция G(X, Y, Z) = (X & Y) | (X & Z) | (Y & Z). Выполняется 16 шагов.
• Раунд 3: функция H(X, Y, Z) = X ^ Y ^ Z. Выполняется 16 шагов.

На каждом шаге выполняется операция сложения, циклического сдвига влево и добавления константы. После обработки всех блоков получается 128-битный дайджест, объединённый из значений регистров A, B, C, D.

Скорость и эффективность

MD4 была спроектирована для высокой скорости работы на 32-битных процессорах. В тестах 1990-х годов она была примерно в 2–3 раза быстрее, чем MD5, и в 10 раз быстрее, чем SHA-1. Однако эта скорость достигалась за счёт упрощения криптографических операций, что сделало её уязвимой для атак.

Классификация и варианты

Основные версии

• MD4 (RFC 1320): оригинальная версия, описанная в 1992 году. Использует 3 раунда по 16 шагов.
• MD4 (RFC 1186): предварительная версия, опубликованная в 1990 году, с незначительными отличиями в константах и порядке операций.
• MD4-256: экспериментальная модификация с увеличенным до 256 бит размером дайджеста, не получившая широкого распространения.

Производные функции

• MD5: улучшенная версия MD4, опубликованная в 1992 году. Добавлен четвёртый раунд, изменены константы и порядок операций, что повысило стойкость, но не устранило уязвимости.
• MD2: более ранняя хеш-функция Ривеста, не связанная напрямую с MD4, но входящая в то же семейство.
• RIPEMD: семейство хеш-функций, разработанное в Европе, частично основанное на идеях MD4, но с улучшенной стойкостью.

Применение

Историческое использование

MD4 применялась в следующих областях:

• Протоколы аутентификации: в системах Microsoft Windows (NTLMv1, NTLMv2) для хеширования паролей. В NTLMv1 использовалась MD4 напрямую, в NTLMv2 — комбинация MD4 и HMAC-MD5.
• Проверка целостности: в некоторых версиях протокола SMB (Server Message Block) для проверки целостности сетевых пакетов.
• Цифровые подписи: в ранних реализациях стандарта PKCS#7 и в некоторых криптографических библиотеках (например, OpenSSL до версии 0.9.6).

Современное состояние

Из-за доказанной нестойкости MD4 не рекомендуется к использованию в новых системах безопасности. В большинстве современных приложений она заменена на SHA-2 (SHA-256, SHA-512) или SHA-3. Однако MD4 всё ещё может встречаться в устаревших системах, таких как старые версии Windows (до Windows 2000) или в некоторых эмуляторах и образах дисков.

Криптоанализ и уязвимости

Атаки на коллизию

Основная уязвимость MD4 — возможность нахождения коллизий (двух разных сообщений с одинаковым хешем). Первая практическая атака была предложена Хансом Доббертином в 1995 году, которая требовала около 2^20 операций (примерно 1 миллион). В 2004 году Ван Сяоюнь и Юй Хунбо разработали атаку, которая находила коллизию за 2^8 операций (256 шагов), что делает возможным вычисление на обычном компьютере за доли секунды. В 2007 году была продемонстрирована атака на коллизию для MD4 с использованием 2^2 операций (4 шага) при определённых условиях.

Атаки на прообраз

Атаки на нахождение прообраза (восстановление исходного сообщения по хешу) для MD4 также возможны, но требуют больше вычислительных ресурсов. В 2008 году была предложена атака сложностью 2^102, что всё ещё делает MD4 уязвимой для целенаправленного взлома.

Последствия

Уязвимости MD4 привели к тому, что она была исключена из стандартов безопасности, таких как FIPS 180 (США) и ГОСТ Р 34.11 (Россия). В России для криптографических целей рекомендуется использовать хеш-функции, соответствующие ГОСТ Р 34.11-2012 («Стрибог»), которые обеспечивают стойкость к коллизиям и прообразам.

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

• MD4 была одной из первых хеш-функций, подвергшихся систематическому криптоанализу, что стимулировало развитие теории хеширования.
• В 1991 году, ещё до публикации RFC 1320, алгоритм MD4 был включён в протокол NTLM, что привело к его широкому распространению в корпоративных сетях.
• Некоторые современные криптографические атаки, такие как атака на протоколы аутентификации (например, атака «Pass-the-Hash»), используют уязвимости MD4 для взлома паролей в Windows-системах.

Источники

• RFC 1320 — The MD4 Message-Digest Algorithm (1992)
• RFC 1186 — MD4 Message Digest Algorithm (1990)
• Доббертин, Х. «The First Practical Collision for MD4» (1995)
• Ван, С., Юй, Х. «How to Break MD5 and Other Hash Functions» (2004)
• Ривест, Р. «The MD4 Message Digest Algorithm» (1990, MIT)
• Шнайер, Б. «Прикладная криптография» (1996)