Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску
MD4
Общий
ДизайнеровРональд Ривест
Впервые опубликованоОктябрь 1990 [1]
СерииMD2 , MD4, MD5 , MD6
Деталь шифра
Размеры дайджеста128 бит
Размеры блоков512 бит
Раундов3
Лучший публичный криптоанализ
Атака коллизий, опубликованная в 2007 году, может обнаружить коллизии для полного MD4 менее чем за 2 хэш-операции. [2]

MD4 Message-Digest Algorithm является криптографической хэш - функция , разработанная Ривест в 1990 году [3] длина дайджеста составляет 128 бит. Алгоритм повлиял на более поздние разработки, такие как алгоритмы MD5 , SHA-1 и RIPEMD . Инициализм «MD» означает «Дайджест сообщения».

Одна операция MD4: MD4 состоит из 48 таких операций, сгруппированных в три цикла по 16 операций. F - нелинейная функция; одна функция используется в каждом раунде. M i обозначает 32-битный блок ввода сообщения, а K i обозначает 32-битную константу, различную для каждого раунда.

Безопасность MD4 была серьезно скомпрометирована. Первая полная коллизионная атака против MD4 была опубликована в 1995 году, и с тех пор было опубликовано несколько новых атак. По состоянию на 2007 год атака может вызвать коллизии менее чем за 2 операции хеширования MD4. [2] Также существует теоретическая атака на прообраз .

Вариант MD4 используется в схеме URI ed2k для предоставления уникального идентификатора файла в популярных P2P-сетях eDonkey2000 / eMule. MD4 также использовался протоколом rsync (до версии 3.0.0.)

MD4 используется для вычисления дайджестов ключей NTLM на основе паролей в Microsoft Windows NT, XP, Vista, 7, 8 и 10. [4]

Безопасность [ править ]

Слабые стороны MD4 были продемонстрированы Ден Боером и Босселарсом в статье, опубликованной в 1991 году. [5] Первая полнофункциональная коллизионная атака MD4 была обнаружена Гансом Доббертином в 1995 году, на выполнение которой в то время требовалось всего несколько секунд. [6] В августе 2004 г. Wang et al. обнаружил очень эффективную атаку коллизий, наряду с атаками на более поздние конструкции хэш-функций в семействе MD4 / MD5 / SHA-1 / RIPEMD. Этот результат был улучшен позже Сасаки и др., И создание коллизии теперь так же дешево, как и ее проверка (несколько микросекунд). [2]

В 2008 году сопротивление прообразу MD4 также было сломлено Гаэтаном Леурентом с атакой 2 102 . [7] В 2010 году Гуо и др. Опубликовали 2 атаки 99,7 . [8]

В 2011 году RFC 6150 заявил, что RFC 1320 (MD4) является историческим (устаревшим).

Хеши MD4 [ править ]

128-битные (16-байтовые) хэши MD4 (также называемые дайджестами сообщений ) обычно представлены как 32-значные шестнадцатеричные числа. Следующее демонстрирует 43-байтовый ввод ASCII и соответствующий хэш MD4:

MD4 ( «быстрая коричневая лиса прыгает через ленивый г OG»)= 1bee69a46ba811185c194762abaeae90

Даже небольшое изменение в сообщении (с огромной вероятностью) приведет к совершенно другому хешу, например, изменение d на c :

MD4 ( «быстрая коричневая лиса прыгает через ленивую гр ог»)= b86e130ce7028da59e672d56ad0113df

Хеш строки нулевой длины:

MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0

Тестовые векторы MD4 [ править ]

Следующие тестовые векторы определены в RFC 1320 (алгоритм дайджеста сообщения MD4).

MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729dMD4 ("дайджест сообщения") = d9130a8164549fe818874806e1c7014bMD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8582f241db351ce627e153e7f0e4MD4 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536

Пример столкновения MD4 [ править ]

Позволять:

k1 = 839c7a4d7a92cb 5 678a5d5 b 9eea5a7573c8a74deb366c3dc20a083b69f5d2a3bb3719dc69891e9f95e809fd7e8b23ba6318ed d 45e51fe39708bf9427e9c3c k2 = 839c7a4d7a92cb d 678a5d5 2 9eea5a7573c8a74deb366c3dc20a083b69f5d2a3bb3719dc69891e9f95e809fd7e8b23ba6318ed c 45e51fe39708bf9427e9c3

k1 ≠ k2, но MD4 (k1) = MD4 (k2) = 4d7e6a1defa93d2dde05b45d864c429b

Обратите внимание, что две шестнадцатеричные цифры k1 и k2 определяют один байт входной строки, длина которого составляет 64 байта.

См. Также [ править ]

  • Сводка по безопасности хеш-функции
  • Сравнение криптографических хеш-функций
  • MD2
  • MD5
  • MD6

Ссылки [ править ]

  • Берт ден Бур, Антун Босселэрс: Атака на последних двух раундах MD4. Крипто 1991: 194–203
  • Ганс Доббертин: Криптоанализ MD4. Быстрое программное шифрование 1996: 53–69
  • Ганс Доббертин, 1998. Криптоанализ MD4. J. Cryptology 11 (4): 253–271.
  • Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, Xiuyuan Yu: Криптоанализ хеш-функций MD4 и RIPEMD. Еврокрипт 2005: 1–18
  • Ю Сасаки, Лей Ван, Кадзуо Охта, Нобору Кунихиро: новое отличие сообщений для MD4. Быстрое программное шифрование 2007: 329–348
  1. ^ "Алгоритм дайджеста сообщений MD4" . Сетевая рабочая группа. Октябрь 1990 . Проверено 29 апреля 2011 .
  2. ^ a b c Ю Сасаки; и другие. (2007). «Новое различие сообщений для MD4» (PDF) . Цитировать журнал требует |journal=( помощь )
  3. ^ "Что такое MD2, MD4 и MD5?" . Стандарты криптографии с открытым ключом (PKCS): PKCS # 7: Стандарт синтаксиса криптографических сообщений: 3.6 Другие криптографические методы: 3.6.6 Что такое MD2, MD4 и MD5? . RSA Laboratories. Архивировано из оригинала на 2011-09-01 . Проверено 29 апреля 2011 .
  4. ^ «5.1 Вопросы безопасности для разработчиков» . Проверено 21 июля 2011 . Получение ключа из пароля описано в [RFC1320] и [FIPS46-2].
  5. ^ Берт ден Бур, Antoon Bosselaers (1991). «Атака на последние два раунда MD4» (PDF) . Архивировано из оригинального (PDF) 23 мая 2003 года. Цитировать журнал требует |journal=( помощь )
  6. ^ Ганс Доббертин (1995-10-23). «Криптоанализ MD4». Журнал криптологии . 11 (4): 253–271. DOI : 10.1007 / s001459900047 . S2CID 7462235 . 
  7. ↑ Gaëtan Leurent ( 10 февраля 2008 г.). «MD4 не односторонний» (PDF) . FSE 2008. Цитировать журнал требует |journal=( помощь )
  8. ^ https://www.academia.edu/20987202/Advanced_Meet-in-the-Middle_Preimage_Attacks_First_Results_on_Full_Tiger_and_Improved_Results_on_MD4_and_SHA-2

Внешние ссылки [ править ]

  • RFC 1320 - Описание MD4 Роном Ривестом
  • RFC 6150 - MD4 в исторический статус
  • Ривест, Рональд (1991). «Алгоритм дайджеста сообщений MD4». Успехи в криптологии-CRYPT0 '90 . Конспект лекций по информатике. 537 . Springer Berlin / Heidelberg. С. 303–311. DOI : 10.1007 / 3-540-38424-3_22 . ISBN 978-3-540-54508-8. Отсутствует или пусто |title=( справка )

Коллизионные атаки [ править ]

  • Атака на последних двух раундах MD4
  • Улучшенная атака столкновения на MD4
  • Bishop Fox (ранее Stach & Liu) Быстрый генератор столкновений MD4