MD5 от затейников из штатовского киберкомандования

8. July 2010, 23:43 Занимательное, Математика, Новостное

Сейчас самый популярный хеш – 9ec4c12949a4f31474f299058ce2b22a. Это число, размещённое на официальной нашивке штатовского киберкомандования. С подачи Wired многие кинулись “расшифровывать” – что значит сей хеш? Быстро выяснилось, что это как бы всего лишь MD5 от официального “бюрократического” описания миссии киберкомандования (текст не привожу, его легко найти; уже сутки как вошло в “Википедию”). Вроде бы, уже официальные лица подтвердили, что, да, так и есть – использовался текст описания миссии, несекретный. Пресса пошумела в англоязычном секторе. Сейчас российская подхватит. Очень много блогеры пишут. В общем, грамотный PR, без дураков.

Но что упускают из виду: в MD5 по определению есть коллизии. То есть, в одно значение функции отображается сколь угодно много текстов (не все осмысленные, да). Поэтому вовсе не факт, что именно опубликованный текст нужно принимать за реальную задумку. Ну, подумаешь, сказали: “да, вот этот самый текст!” А может, там совсем другой текст-то был заложен, ага. Шутка оказалась с намёком, с двойным дном.

Ну и учитывайте ещё, что в MD5 заданные пары текстов, порождающих коллизии, находить много проще, чем подбирать коллизию к заданному хешу (на этом эффекте три года назад сломали SSL).

Вот.

()

Похожие записки:



Далее - мнения и дискуссии

(Сообщения ниже добавляются читателями сайта, через форму, расположенную в конце страницы.)

Комментарии читателей блога: 11

  • 1. 9th July 2010, 00:05 // Читатель jno написал:

    Занятно…

  • 2. 9th July 2010, 05:57 // Читатель kaschey написал:

    А число вариантов-то посчитали? :-)
    Среди всех когда-либо написанных человечеством текстов и тех, которые будут написаны в ближайшие тысячелетия (учитывая и это сообщение :-) ) скоре всего не найдется ни одной коллизиии!
    Для шанса 50/50 надо 4 000 000 000 ^ 2 текстов.
    А для подбора коллизии к нужному тексту надо перебрать 4 000 000 000 ^ 4 вариантов.

    С осмысленным текстом задача пока не решаема. Со случайными наборами, да, “пары” находятся легко.

  • 3. 9th July 2010, 09:27 // Читатель aa написал:

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

  • 4. 9th July 2010, 10:07 // Читатель arcman написал:

    MD5 слаб получается.
    как дальше жить?

  • 5. 9th July 2010, 11:09 // Читатель Сергей написал:

    to arcman:

    man md5 выдает в разделе NOTES следующее:

    MD2, MD4, and MD5 are recommended only for compatibility with existing applications. In new applications, SHA-1 or RIPEMD-160 should be preferred.

    слабость md5 стала широко известна уже давно. примерно с тех пор как появились практичные алгоритмы взлома. так что неудивительно что хэш был расшифрован так быстро. а начет двойного дна, сложноватая задачка судя по всему.

  • 6. 9th July 2010, 19:30 // Александр Венедюхин ответил:

    А число вариантов-то посчитали?

    А число вариантов (вариантов чего, кстати?) – оно тут не так важно. Мы же вольны выбирать любую коллизию, подстраивая оба текста под неё.

    Тем более, что коллизии в MD5 известны много лет. Это вообще нестойкий алгоритм, как уже написали.

  • 7. 10th July 2010, 10:29 // Читатель kaschey написал:

    Может не совсем правильно выразился, но чтобы текст X подогнать под хеш текста Y мы должны вставить туда белеберду равноценную 9ec4c12949a4f31474f299058ce2b22a. Так как каждый измененный/вставленный символ дает нам 1 / (2^16) успеха. Можно представить, что алгоритм слаб как XOR и смоделировать.

  • 8. 10th July 2010, 15:24 // Александр Венедюхин ответил:

    Ну, не обязательно белеберду.

  • 9. 12th July 2010, 05:14 // Читатель kaschey написал:

    Ну попробуйте смоделировать. Сделайте 16-и байтовый XOR-хеш этого поста и подгоните под него предыдущий (или другой, подлиннее). Мне почему-то задача кажется, что это будет ручная и не обязательно выполнимая работа. А там более серьезный MD5.

  • 10. 12th July 2010, 10:32 // Читатель arcman написал:

    “Как подделывают CRC16/32
    Автор: (c)Крис Касперски ака мыщъх”
    http://www.insidepro.com/kk/118/118r.shtml

  • 11. 12th July 2010, 15:15 // Александр Венедюхин ответил:

    Ну попробуйте смоделировать. Сделайте 16-и байтовый XOR-хеш…

    А там более серьезный MD5.

    Простите, мне не ясно, что Вы хотите доказать. Коллизии в MD5 многократно вычислялись на практике. Это очень старая тема. Есть примеры и с исполняемыми файлами (имеющими одинаковое значение MD5, но выполняющими совершенно разные функции), и с документами в PostScript. Это общеизвестно, на мой взгляд.

    Да, понятно, что подготовка коллизии с текстами – она непростая. Но эти тексты – лишь потоки байтов. И, отметьте ещё раз, там другая задача: нужно не подобрать текст под заданную коллизию, а сгенерировать пару произвольных текстов, порождающих коллизию. Это важное вычислительное отличие.

    (Что Вы имеете в виду под “XOR-хеш”? Если речь о суммировании, то подобрать пару произвольных различных текстов с одинаковой суммой – задача, очевидно, не сложная. Попробуйте её решить сами.)