В этой статье я хочу рассказать как сгенерировать коллизию к имеющемуся md5 хешу. Для понимания статьи вам понадобится понимание работы алгоритма хеширования md5. О нём вы сможете прочитать здесь http://ru.wikipedia.org/wiki/MD5 Здесь я буду использовать обозначения именно из этой статьи. Итак md5 работает так: на входе он получает сообщение, которое подвергается выравниванию, после этого выравненное сообщение разбивается на блоки, каждый из которых проходит 4 раунда по 16 операторов. На выходе получается буфер ABCD, которой при выводе в обратном порядке (т.е. DCBA) и является хешем. Значит когда мы приступаем к генерации коллизии у нас есть только хеш и нет никакой информации об исходном сообщении. Поскольку мы не знаем длины сообщения после выравнивания, то предположим что его длина после выравнивания равна 512 (в дальнейшем мы убедимся, что это предположение ничему не противоречит). Так как длина сообщения после выравнивания равна 512, то для вычисления хеша понадобится 4 раунда (т.е. одна итерация). Перед первым раундом: A=AA=01 23 45 67 B=BB=89 AB CD EF c=CC=FE DC BA 98 D=DD=76 54 32 10 После 4 рунда An=AA+A Bn=BB+B Cn=CC+C Dn=DD=D (AnBnCnDn - выходной буфер) но мы знаем значения AA, BB, CC, DD (т.к. прошла только одна итерация). Также мы знаем значения Ax, Bx, Cx, Dx (это и есть хеш) Отсюда получаем A, B, C, D (это значения сразу после 16 оператора 4 раунда). Теперь подробнее рассмотрим сами операторы. Как мы знаем они имеют вид [ABCD k s i] или что тоже самое A = B +((Ax+Fun(B,C,D)+X[k]+T)<<<s) (я специально взял два обозначения: A и Ax, так как за A я обозначил выходное значение оператора, а за Ax - входное значение оператора). В этом уравнении есть две неизвестные: Ax и X[k].(Это верно, так как мы будем рассматривать каждый оператор начиная с 16 оператора 4 раунда(так как выходные значения именно этого оператора у нас уже есть)). После несложных преобразований мы из этого уравнения получаем следующее: ((A-B)>>>s)-(Fun(B,C,D)+T) = Ax + X[k] Так мы будем преобразовывать (и подставлять в него известные значения) каждый оператор начиная с 16 оператора 4 раунда и заканчивая 1 оператором 2 раунда включительно. (Почему мы не захватываем операторы 1 раунда объясняется позже). Причём везде мы будем считать что Ax = 00 00 00 00(для удобства) Теперь вспомним, что при выравнивании исходное сообщение сначала дополняется единичным битом , а затем энным количеством нулей. Нам было бы выгодно если эта единица и нули были бы НЕ в одном 32 битном блоке с самим сообщением. Для этого предположим, что длина исходного сообщения была 128 бит. Последние 64 бита выравнивания - это длина исходного сообщения в битах (т.е. 000...00010000000). Итак мы не затрагивали операторы первого раунда, так как именно в нём в последний раз используются 15 и 16 блоки выравненного сообщения (последние 64 бита). А именно они используются в 15 и 16 операторах 1 раунда. Значит преобразовав их к виду ((A-B)>>>s)-(Fun(B,C,D)+T) = Ax + X[k] мы вместо того, что бы принимать Ax=00 00 00 00 примем X[15]=0000...000100000 X[14]=0...00000000 (здесь индексы 15 и 14 так как нумерация блоков начинается с 0) Далее мы также подставляем вместо X[k] нужные значения руководствуясь тем что с 13 по 4 блок включительно идут одни нули и только в начале 4 блока идёт 1. Мы действуем так вплоть до 4 оператора 1 раунда. Так как в этих последних 4-х операторах в последний раз используются A, B, C и D, а начальные значения у них обязательно должны быть: A=01 23 45 67 B=89 AB CD EF c=FE DC BA 98 D=76 54 32 10 то преобразовав очередной оператор к виду ((A-B)>>>s)-(Fun(B,C,D)+T) = Ax + X[k] мы подставляем значение Ax равное начальному соответствующему ему значению. После всех этих манипуляций мы получаем буфер: X[0],X[1],X[2],X[3],...,X[14],X[15] Это выравненное начальное сообщение (или точнее его коллизия), значит интересующее нас начальное сообщение хранится в буфере X[0]X[1]X[2]X[3](точнее его битовое представление). Собственно всё.
Да я хотел и сейчас хочу реализовать данный метод на C. Но решил сначала узнать мнение других насчёт эффективности данного метода.
очень сложно оценить эффективность по такой статье. вполне возможно, что есть какая-то ошибка, которую ты не учел. с реализацией могу помочь, если хочешь.
Да с реализацией мне помощь бы не помешала. Я ,например, не знаю как перевести строку в двоичный код, ну то есть записать её в виде последовательности бит.
этого делать не надо. char и так последовательность бит. я думаю, этот разговор надо продолжить в icq. он получается уже немного не по теме топика.
Интересная статья. По сабжу нашел сорцы на С code.google.com/p/paulzcycoding/source/browse/trunk/security/hw1/evilize-0.1/?r=2 Автор утверждает,что программа генерирует коллизии.
возьми любой тестовый хэш из этого раздела и попробуй подобрать к нему вводное сообщение по своему методу "на бумаге". Потом найди где у тебя ошибка, и напиши нам тут и еще. Не путайте генерацию коллизий между двумя заранее неизвестными (рандомными) наборами символов - эта задача уже решена, причем неоднократно. И программы такие тоже есть, только практической пользы от таких коллизий ноль, и генерацию коллизии к заранее заданному хэшу. Эта задача не была решена ни одним коллективом ученых и математиков во всем мире за все 10+ лет с момента создания алгоритма. Не стоит исходить из того, что вы, друзья, самые умные в мире. Скорее стоит исходить из того, что вы входите в те 99,9999% которые в очередной раз пытаясь найти решение никем прежде не решенной задачи допустили ошибку.
Monsieur, логика файла md5coll_lib.c действительно очень сильно похожа на то, что описано в статье. Vlad1792, посмотри тоже, может быть это действительно реализованный метод? ЗЫ: да, похоже на то, но частью исходников можно воспользоваться. ЗЫЗЫ: ErrorNeo прав... попробуй подобрать для начала.
почему нет? мы же работаем с битовыми последовательностями. они в десятичной форме могут быть отрицательными вполне. или я что-то не так понял?
Меня просто вот что смутило. Берём, например, сообщение qwerty. Его хеш: d8578edf8458ce06fbc5bb76a58c5ca4 Тогда A = a58c5ca4 B = fbc5bb76 C = 8458ce06 D = d8578edf Что вычислить значения A B C D которые были сразу после 16 оператора 4 раунда мы должны с написанными выше значениями сделать следующее: A = a58c5ca4 - 01234567 B = fbc5bb76 - 89abcdef C = 8458ce06 - fedcba98 D = d8578edf - 76543210 Ну вот в значении C мы имеем 8458ce06 < fedcba98 => 8458ce06 - fedcba98 < 0 Или я не прав?
Ну я имел ввиду, что 8458ce06 меньше чем fedcba98, поэтому 8458ce06 - fedcba98 будет меньше нуля. Или я ошибаюсь и 8458ce06 НЕ меньше чем fedcba98?
