Беру любой набор байт наугад (будет Signature) , расшифровываю их публичным Key (будет MD5 хеш) , потом напускаю MD5 брутфорсер на этот хеш и получаю Message . Вуаля ?

Или второй вариант , беру любой Message , получаю MD5 хеш от него , а потом перебираю любые Signature пока результат её расшифровки не совпадёт с этим хешем . Ес-сно можно взять не один Message и хеш , а целый массив , и перебирать пока не совпадёт с любым одним из массива .

Это же быстрее , чем факторизовать . Или где меня опять перекосило ?

Разумеется, перекосило. Дело в том, что MD5 изначально разрабатывалась как функция, устойчивая к коллизиям. Т.е. для того, чтобы осуществить твою атаку (bruteforce), тебе потребуется 2^64 итерации (результирующее значение MD5 - 128 бит) для атаки методом дней рождения. На простом языке это означает, что ты позеленеешь перебирать это дело. Загляни на reng.ru - там много воплей было в теме "Коллизии. Или писец подкрался незаметно". У MD5 нашли таки коллизии, однако там не все так просто. :) Так что, с MD5 пока связываться не советую.

А как же всякие LC+ , InsidePro и т.д. ? Они можно сказать моментом находять пароль по хешу . Или там не MD5 юзаеться ?
Я вот к примеру взял Ultra (c) v1.0 cracking machine by bart/x , ввёл хеш и за 04 сек. она мне нашла то слово , от которого я брал хеш .

Про новые коллизии я слыхал , в ru.crypt тоже обсуждали , пока с ними не связываюсь .

это говорит о том, что выбран слабый пароль. Возьми пароль с энтропией хотябы в 64 бита и засекай время :)

Все эти программы перебирают пароли, но никак не обращают хеш... они просто пробуют пароли из словаря, либо по брутфорсу.

Кроме того, в Windows для NTLM-хеша используется не MD5, а MD4, для которого, вообще говоря, известны методы обращения...

volodya
Т.е. для того, чтобы осуществить твою атаку (bruteforce), тебе потребуется 2^64 итерации (результирующее значение MD5 - 128 бит)

точно в 2^64 ? может быть все-таки 2^127 ?

Ты слышал - я упоминал атаку дней рождения. Так что, все таки, 2^64 :) flankerx, поправь меня, если ошибаюсь :)

Не, не надо меня поправлять. Все я прав. Открываем Менезеса, 9 глава. Раздел - 9.7.1 Birthday attacks - и читаем что там написано. Внимательно. Потом снимаем шляпу и говорим: "ты такой умный, Володя, ты читаешь хорошие книги" :)
Я планирую осветить часть таких вопросов в третьей части упаковщиков. Работа над статьей идет очень интенсивно.

AFAIK, днем рождения можно найти пару коллизий за 2^64, но при этом нужно сохранять все ранее сгенеренные пары текст-хешзначение. А чтобы найти прообраз для данного хеш-значения вроде все-таки работать подольше надо... все, сейчас пойду книжку почитаю :)

Да блин , обломс короче :)
Хотя , так помечтать , что выбрав я любую сигнатуру наугад , расшифровав её , получил хеш , а этот хеш оказался бы от простого слова "user" , то брутфорс длился бы не больше минуты .
В общем даже если понадобиться 2^127 итераций , но фортуна повернёться передом , то может обойтись в 2^64 :)

шансов на это 2^-63, или приблизительно 10^-19... все еще хочешь попробовать? ;-)

Icebp
„Так а что там непонятно? Вроде я все писал довольно прозрачно без всяких изощрений. Приведи пример того что тебе непонятно.“
Дело не в том, что мне что-то конкретно не понятно, просто ц тебя сорцы так оформлены. Чужой текст на асме вообще тяжело читать. Ладно, по теме, начал сравнивать со своей реализацией (года 2 назад было, уже забыл все) - я могу ошибаться, но дело может быть в функции div256, мало того, что она довольно криво написана - мешанина 8-, 16- и 32-битных регистров скорости еще никому не добавляла, так можно и вообще без нее написать. Почитай про CRT, например.
Да, еще, выкинь нафик ммх - оно так как зайцу стоп-сигнал...

bogrus
На цифровую подпись с использованием RSA могут быть более простые атаки, чем разложение на множители. Есть так называемая мультипликативная атака. Пусть есть две подписи: RSA(a) и RSA(b), где a и b - это хеши, а RSA - это результат RSA-шифрования. Тогда справедливо равенство:
RSA(a*b)=RSA(a)*RSA(b). Итак, имея две подписи можно построить и третью. Если есть еще подписи, то можно брать их всякие произведения и попытаться найти требуемый хеш.
masquer
Похоже ты прав: больше всего мне не нравится именно процедура деления, слишком уж какая то громоздкая она получилась. Насчет MMX я думаю так быстрее будет чем через 32-х битные регистры, ведь как-никак 64 бита. А что ты имел в виду, говоря про CRT? (мне в голову только приходит Cathode Ray Tube). Я не пойму как можно было написать без процедуры деления с остатком, ведь это же основная вещь в RSA.
All
Я что то слышал насчет алгоритма быстрого деления, может ли кто-нибудь рассказать про него? А то у меня все в лоб считается. Пытался понять как же винамп мог привести к ускорению работы пограммы. Как включил комп в ДОС-е посмотрел что в регистрах CR0 и CR4. Было CR0=10h, CR4=2000h. В винде когда запустил винамп, то стало: CR0=0, CR4=0. Но моя программа по-прежнему тормозила. Закрыл винамп, вышел из винды, опыть посмотрел регистры и увидел что опять CR0=10h и CR4=2000h. Но при всем при этом моя программа стала работать быстрее. Так что дело похоже не в CR0 и CR4. Здесь кто-то упоминал еще о флаге AC. Посмотрю его. Вот еще думаю: могла ли винда менять какие-нибудь MSR-ы?

„Насчет MMX я думаю так быстрее будет чем через 32-х битные регистры, ведь как-никак 64 бита.“
через rep movsd может быть даже побыстрее будет :)

„А что ты имел в виду, говоря про CRT?“
Chinese Remainder Theorem

Ты лучше литературу почитай - Handbook of Applied Cryptography, например

Я что то слышал насчет алгоритма быстрого деления, может ли кто-нибудь рассказать про него?

Мда... Не любим мы Кнута читать. 2 том. Глава 4.3.1. Алгоритм D (деление неотрицательных целых чисел).

volodya
„Мда... Не любим мы Кнута читать. 2 том. Глава 4.3.1. Алгоритм D (деление неотрицательных целых чисел).“
Читал я в свое время и про быстрое деление и про умножение. Но эти алгоритмы эффективны только при аппаратной реализации, а программно будет хуже, чем дедовское "деление углом". Или я не прав ?

masquer
Я посмотрел китайскую теорему об остатках. Если я правильно тебя понял с ее помощью можно выполнить более быстрое деление с остатком, я прав?
volodya
Я нашел в электронном виде книжку Кнута, но она какая то урезанная и там как назло нет именно того, что ты упоминаешь. В печатном виде похоже достать его будет еще сложнее. Было бы неплохо, если кто даст ссылку на полный электронный вариант его "Искусства программирования".