тормоза в RSA

А-а блин , там хеши . Есть у меня несколько копий этой статьи и многих других , сам уже запутался

Надо теперь подумать , что это меняет ...

 

Хм... Помоему тут не про то речь идет...

Icebp

Единственное что могу предположить это align памяти, у меня так уже было... При первом запуске где-то юзается неалигненная память - при втором - алигненная.

 

Icebp

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

 

snatch

Да я вроде использую нормальный генератор случайных чисел. Там у меня результат инструкции RDTSC после каждого нажатия клавиши используется для генерации случайных простых чисел. Получается аналог рулетки. Так как частота несколько гигагерц, то предсказать что получится не сможет даже тот кто жмет клавиши. Там в программе для рандомизации надо нажимать любую клавишу 8 раз для генерации первого простого числа и еще 8 раз для второго. Кстати я тут понял:

bogrus

У тебя программа висела потому что ты не жал клавиши. Нажатия требуются для рандомизации. Там когда нажмешь на экране будут появляться числа 1, 2, ... , 8 , потом начнется генерация первого простого числа и на экране будет мельтешить символ, показывая насколько быстро идет процесс. Как число сгенерится, то оно высветится на экране. Потом надо будет опять 8 раз нажать любую клавишу для генерации второго простого числа. Когда все сгенерится, то на экране появятся модуль RSA и секретный ключ. Чтобы сохранить результат в файлах надо будет нажать клавишу "w" (маленькая w, а не большая).

masquer

Так а что там непонятно? Вроде я все писал довольно прозрачно без всяких изощрений. Приведи пример того что тебе непонятно.

All

Интересно узнать как обстоит дело со скоростью моей программы у других. У кого-нибудь есть идеи насчет разной скорости до и после запуска винампа (на всякий случай еще раз повторю что в обоих случаях программа запускалась под чистым ДОС-ом, а следовательно в монопольном режиме)? У меня на этот счет подозрения примерно такого типа: винамп чего-то там инициализирует и из-за этого скорость выполнения инструкций MOVQ (ими я копирую большие участки памяти) в моей программе почему то растет. У кого есть какие мысли на это счет. Да, еще вопрос: я правильно понимаю, что сейчас наилучшим алгоритмом факторизации является метод решета общего числового поля или появились новые алгоритмы? Возможно ли, что АНБ или ФАПСИ знают какой то более крутой алгоритм или у них просто большие вычислительные мощности, а факторизуют они (если факторизуют вообще) тем же решетом общего числового поля.

Да, может выложить мою программу цифровой подписи?

 

Icebp

Что-то EMMS я заметил только перед самым int 20h, по-моему это не правильно.

 

года полтора назад в ru.crypt один человек говорил, что за 2 месяца на кластере из P-III сумел разложить 512-битный ключ Майкрософта, используемый для подписи дллок криптопровайдеров... Типа лень ему было каждую новую версию в Microsoft на подпись отсылать )

 

2Icebp, да, для больших чисел ничего лучше GNFS пока не придумали С этой штукой одна проблема -- нормальную реализацию достать очень непросто

 

Icebp

Про правильное использование MOVQ написано

, например, здесь :

http://www.sources.ru/NonCGI/Forum5/HTML/000080.html

Обязательно позаботься о выравнивании на границу

8 байт. dq по-моему этого не делает ? В статьях про быстроту Виндовс упоминалось, что необходимость сохранять MMX регистры тормозит переключение контекста.

Я не спец по MMX, но почему бы не быть такой ситуации - система ,узнав что MMX использовался

( возможно бит какой есть в Интеле), начинает сохранять его регистры - отсюда тормоза.

 

Icebp

Да , действительно . Надо было инструкцию по пользованию



flankerx

Неужели они когда-то использовали 512-бит , сейчас кажеться не меньше 1024 .



All можно я ещё вопросик не по теме .

Если в моей схеме Signature - это есть зашифрованный MD5 хеш от Message , тогда :



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



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



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

 

Насчет MMX valterg прав.

Как влияет winamp не знаю, но:

1) выравнивание на 8 обязательно (в смысле желательно)

2) в конце блока MMX пересылок желательно вставить инструкцию EMMS (признак очистки), иначе при переключении контекста ось может сохранять MMX регистры, хотя не знаю присутствует ли оно в коде.

3) можно дополнительно оптимизировать пересылки: например в процедуре copy25 8 раз повторяется movq mm0,m64 и movq m64,mm0, хотя для оптимизации работы конвейера лучше использовать

Код (Text):

1. movq mm0,..
2. movq mm1,..
3. ...
4. movq ..,mm0
5. movq ..,mm1
6. ...
7. emms
8. ret

Eсли EMMS не поможет, то не знаю, разве что подробнее рыться в IA-32 manual по использованию FPU и MMX (надеюсь, эмуляция FPU отключена, иначе movq вообще бы не работали)



PS: исправление - "иначе при переключении контекста ось может сохранять MMX регистры" - это фигня, прошу прощения. Сохранение состояния регистров не зависит от FPU Tag Word, а зависит только от реализации софта - либо FSAVE\FXSAVE (сохранять все), либо FSTENV (только управляющие регистры).



Что может остаться "полезного" от винампа после перезагрузки оси ? Состояние FPU (может пропущена инициализация FINIT) или какой флаг в CRx\EFLAGS (например AC) ?

 

Беру любой набор байт наугад (будет 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, например.

Да, еще, выкинь нафик ммх - оно так как зайцу стоп-сигнал...