stringtranslate.com

МД4

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

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

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

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

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

Безопасность

Слабости MD4 были продемонстрированы Деном Буром и Босселаерсом в статье, опубликованной в 1991 году. [5] Первая полнораундовая атака коллизий MD4 была обнаружена Гансом Доббертином в 1995 году, и на то время ее реализация занимала всего несколько секунд. [6] В августе 2004 года Ван и др. обнаружили очень эффективную атаку коллизий, наряду с атаками на более поздние конструкции хэш-функций в семействе 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("Быстрая коричневая лиса перепрыгивает через ленивую собаку ")= 1bee69a46ba811185c194762abaeae90

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

MD4("Быстрая коричневая лиса перепрыгивает через ленивого козла ")= б86е130це7028да59е672д56ад0113дф

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

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0

Векторы теста MD4

Следующие тестовые векторы определены в RFC 1320 (алгоритм MD4 Message-Digest):

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

Пример столкновения MD4

Позволять:

k1 = 839c7a4d7a92cb 5 678a5d5 b 9eea5a7573c8a74deb366c3dc20a083b69f5d2a3bb3719dc69891e9f95e809fd7e8b23ba6318ed d 45e51fe39708bf9427e 9c3e8b9 k2 = 839c7a4d7a92cb d 678a5d5 2 9eea5a7573c8a74deb366c3dc20a083b69f5d2a3bb3719dc69891e9f95e809fd7e8b23ba6318ed c 45e51fe39708bf9427e 9c3e8b9
MD4(k1) = MD4(k2) = 4d7e6a1defa93d2dde05b45d864c429b

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

Смотрите также

Ссылки

  1. ^ Rivest, Ronald L. (октябрь 1990 г.). "Алгоритм дайджеста сообщений MD4". Network Working Group . Получено 29.04.2011 .
  2. ^ abc Ю Сасаки и др. (2007). "Различие нового сообщения для MD4" (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  3. ^ "Что такое MD2, MD4 и MD5?". Стандарты криптографии с открытым ключом (PKCS): PKCS #7: Стандарт синтаксиса криптографических сообщений: 3.6 Другие криптографические методы: 3.6.6 Что такое MD2, MD4 и MD5? . RSA Laboratories. Архивировано из оригинала 2011-09-01 . Получено 2011-04-29 .
  4. ^ "5.1 Вопросы безопасности для разработчиков" . Получено 2011-07-21 . Выведение ключа из пароля описано в [RFC1320] и [FIPS46-2].
  5. ^ Берт ден Бур, Антон Босселаерс (1991). "Атака на последние два раунда MD4" (PDF) . Архивировано из оригинала (PDF) 2003-05-23. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  6. ^ Ганс Доббертин (1995-10-23). ​​"Криптоанализ MD4". Журнал криптологии . 11 (4): 253–271. doi : 10.1007/s001459900047 . S2CID  7462235.
  7. ^ Гаэтан Леран (10 февраля 2008 г.). «MD4 — это не одностороннее движение» (PDF) . ФСЕ 2008. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  8. ^ Го, Цзянь; Лин, Сан; Рехбергер, Кристиан; Ван, Хуасюн (2010). «Расширенные атаки на прообразы Meet-in-the-Middle: первые результаты на Full Tiger и улучшенные результаты на MD4 и SHA-2». Достижения в криптологии - ASIACRYPT 2010. Конспект лекций по информатике. Том 6477. С. 56–75. doi : 10.1007/978-3-642-17373-8_4 . hdl : 10356/94168 . ISBN 978-3-642-17372-1.

Внешние ссылки

Атаки со столкновениями