Раскрываем подпись прошивки, поиск простых сомножителей ключа. Поделиться Опции

[puper]

Народ! А если собраться и сломать RSA.

При помощи распределённой обработки RSA 512 бит ломали на ~1.5 тыс компах за 7-8 месяцев (я видел упоминание о 2-х таких случаях), а у нас 1024 бита...

off_topic;
Вчера по RenTV показывали дядю, живёт в Липецке (вроде Кузнецов фамилия), попал в книгу рекордов Гинесса за то что извлек в уме (телепат типа ) корень 1000 степени из числа с ~540 десятичными знаками за 1 минуту и 1сек., комп. результат проверял > 2-х суток.
Вот этого дядю бы припахать на наши нужды....

[4inut]

2puper,

При помощи распределённой обработки RSA 512 бит ломали на ~1.5 тыс компах за 7-8 месяцев (я видел упоминание о 2-х таких случаях), а у нас 1024 бита...

а на мотофане ~40000 тыс. пользователей ;)

я не очень в это втыкаю, а для того чтобы сломать этот 1024 битый ключ нужна очень большая вычислительная мощность?

[puper]

я не очень в это втыкаю, а для того чтобы сломать этот 1024 битый ключ нужна очень большая вычислительная мощность?

Да утверждают что практически невозможно, по крайней мере если 512 взломали за 7 месяцев, то это не значит что 1024 уйдёт 7х2=14 месяцев, тут другая зависимость, т.е. за 14 месяцев при таком раскладе можно ломануть лишь 513 бит
и т.д. Крайне призачный шанс разложить это число наугад (на дурака) - если получится - то это везение в астрономических масштабах, проще споймать живого моторольца и пытать его (или поить).

А для распреденного подбора ещё клиента писать надо... Кто это будет делать?

[4inut]

2puper,
я правильно понимаю, под определенный размер прошивки, генерируется определенная подпись?

[puper]

я правильно понимаю, под определенный размер прошивки, генерируется определенная подпись?

Если я понимаю правильно, то размер подписи от размера подписываемого никак не зависит, тут выше Vilko писал, что сначала вычисляется хэш прошивки по алгоритму SHA-1, а уже этот хэш подписывается. 1024 бита взяли, потому что уже есть прецедент ломания 512 бит. И про RSA вот тут (ссылка тож от Vilko) хорошо написано.

[Vilko]

Если я понимаю правильно, то размер подписи от размера подписываемого никак не зависит, тут выше Vilko писал, что сначала вычисляется хэш прошивки по алгоритму SHA-1, а уже этот хэш подписывается. 1024 бита взяли, потому что уже есть прецедент ломания 512 бит. И про RSA вот тут (ссылка тож от Vilko) хорошо написано.

правильно, от размера не зависит.
и потом - подпись генерится на КАЖДОЕ изменение в прошивке. т.е. если в новой версии изменилс хоть 1 байт - уже новая подпись выпускается.

и если уж ломать - гораздо реальнее сломать (подобрать) SHA-1 хеш на свой измененный код. на это надо несравнимо меньше операций, чем на факторизацию.
а учитывая тонкости реализации подписи именно в моторах - нужно подобрать хеш только на блок длиной 128 байт. этого будет достаточно, чтобы делать в дальнейшем любые изменения в прошивке без дополнительного подбора.

[hobbit19]

про RSA читал!!!!!!!
но на сайте 40000 пользователей!!!
Вдруг повезет!!!!!

[JenFA]

hobbit19, есть такая хорошая программка, Brutus называется. Ломает пароли методом перебора (Brute Force). Ну так вот, при выборе особо сложного задания, она выдала замечательную фразу:

"The attack you order is likely to take several billion years to execute.
Brute has calculated, that you stand more chance by telephoning the target system
and asking the username/password"

=) Вот и тут тоже самое.

[4inut]

И если вы подберет хеш на блок 128 байт, можно будет добавлять компоненты в прошивку, например из прошивки в620 вырвать кусок отв. за запись видео и всунуть в с650? ;D

мечты..

[Regressor]

По поводу системы подбора на машинах пользователей мотофана. RSA ломало порядка 50000 участников! Причем у некоторых участников было больше одной машины. У некоторых участников было по несколько тысяч машин. Т.е. это в любом случае не 1.5 тыс компьютеров. Исходный код клиента distributed.net лежит на http://www.distributed.net/source/ а вот исходников ceрвера нету. Траффик между серверами и клиентами ОЧЕНЬ большой и нагрузка на сервер тоже немаленькая, т.е. помимо всего прочего это нехилые денежные затраты для организаторов всего этого действа. Так что затея с взломом отпадает сама собой. SHA хэш подобрать действительно проще :)

[KQ_44]

Ладно, с тем, что - вроде ясно! Осталось определить кто и как!
Будем ждать пока это сделает Vilko или посоучаствуем
или опять будем ныть про тисячи машин и "затея с взломом отпадает сама собой"?!

[dimichxp]

hobbit19,

остается писать клиента и сервера для распределенного перебора. сам писать не могу, опыта мало )))

[hobbit19]

а кто умеет????столько народу на форуме!!!
неужели никто не может???










-----------------------------------------------------------------------------------------------------------------------------
яву в с350 тоже искали.................................... но так и не нашли.

[dion]

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

А так в принципе на C++ я бы написал.

[hobbit19]

насчет трафика верно подметил!!!
его надо свести к минемому!!!
если можешь напиши!!!!









-----------------------------------------------------------------------------------------------------------------------------
кто ищет -тот всегда найдет.

[Evy]

Интересно, кстати, было б "добить" BlowFish, которым криптуются прошивки для C350, T72x и т.п. Мы ведь там взяли готовые P и S массивы (сама моторола хранит их в прошивке, чтобы не пересчитывать). А ключевое слово, по которому генерятся Пи и С массивы так и не нашли. Может нахождение этого слова что-нибудь да даст?

[puper]

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

Много скепсиса у меня на тему перербора, но если начнём, то видится мне это так:
Весь диапазон от 0 до N надо поделить на блоки. Серевер ведёт учёт занятых блоков (взятых в обработку), и выдаёт клинету очередной необработанный диапазон и помечает "в обработке".
Клиент получает его и начинает перебирать в этом дипапазоне все простые числа, когда найдено очередное простое число Х, так что N делится на X без остатка то это (Х и результат) и будут наши искомые числа. Проблема-дилема в том, что простые числа надо перебирать на ходу, т.е таблицу с числами не составишь - ресурсов не хватит.
Когда перебраны все числа в блоке, результат отправляется на сервер. Серевер помечает этот блок - "отработано". Видимо клиенту на этом этапе не следует сообщать о нахождении числа, т.к. всегда найдётся такой индюк, который монополизирует себе эти числа. Если блок очень долго "в обработке" - значит клиент забил на это дело и блок снова надо разлочить - кто другой возьмёт.
Преимущества такого метода:
1. Сервер очень прост - он ничё не делает только следит за резервацией блоков и проверка результата
2. Трафик мал - один раз надо получить диапазон, обработка идёт без конекта, затем конект-отправка результата.
На клиенте надо реализовать какой-то быстрый алгоритм нахождения очередного простого числа, ну и деление (сравнение) - оптимизировать до последнего такта.
Ещё вопрос - перебирать все числа или принять какие-то допуски (вряд ли один из сомножителей будет 3, 7 , 11 и т.д.)

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

Сам я вряд ли смогу сделать - сильно уж пугают такие большие числа (одна ошибка может свести на нет весь труд) - но если будем начинать - то семь раз отмерь - один отрежь.

[dion]

:) Идея интересная, но может лучше не RSA перебирать. Ждем мнение Vilko

[dion]

Вариант 3: Клиент, при соединения просит у сервера известные простые числа, сервер их отдает, дальше клиент че-то сам считает и при следующем онлайне отдает серверу и насчитванные им простые числа.

[KQ_44]

про RSA:
1. Для делфы есть библиотека FGInt - для больших целых.
2. Начинать надо с больших чисел - где-то встречал рекомендацию для RSA выбирать близкие простые (разница - несколько порядков).
3. http://www.cryptography.ru/db/msg.html?mid...uri=node29.html - "введение в криптографию"
главы о простых числах и RSA - очень неплохо написано и есть пояснения того, что нематиматикам не понятно.
4. http://www.frenchfries.net/paul/factoring/theory/index.html - этот тип собрал основную информацию о алгоритмах факторизации частично с исходниками на Сях. Там 16 алгоритмов.

Vilko: Там при проверке подписи используются некие порты - можеш сказать что-либо о них.
Пытаюсь снизу в верх перевести асм в что-либо более простое и понятное. Процедуры SHA уже переписал, а выше застрял.

tushik: А зачто такой цвет ядовитый у сайта?

[hobbit19]

а насчет перебора есть идеи????
и все-таки сможем ли мы заменить в теле флешку вслучие удачи????

[dimichxp]

hobbit19,

Мда... Какая свзяь между заменой флешки и редактированием прошивки?

[hobbit19]

в смысле доработка прошивки для потдержки памяти большего обьема!!!

[hobbit19]

спасибо за ответ.
сейчас самое главное сломать.
а кто нибудь прикидывал скока нужно времени ели машин будет около 10 тысяч
больше думаю не соберем!!!!

[hobbit19]

кстати в инете читал что в xbox RSA 2048 бит.правда его не сломали
подробнее на www.theoneproject.com

[hobbit19]

нашел сайт с исходниками системы распределенных вычеслений BOINC
http://boinc.berkeley.edu/source/ думаю если не много доработать они нам сгодяться.

[creer]

А зачем пытаться вычислять простые числа? Ведь в их уже находят в проекте GIMPS (Great Internet Mersenne Prime Search). Максимальное простое число найденное ими - 2^25964951 (42 Мерсеновское число), т.е. примерно 10^7816229. Значит им гарантированно известно все простые числа до корня из этого числа. Этого хватит не только на 1024 битный ключ. Осталось эти числа как-то взять у них.

[hobbit19]

НУ попроси у них
может дадут!!!!
все равно самим надо будет вычислять дальше.

[dion]

Тут еще нужно нормальный алгоритм вычисления найти. Если мы будем каждое число делить на все меньшие его числа, то далеко не уедем...

[dimichxp]

creer,

GIMPS ищет числа Мерсенна (Ферма) вида (2^2p)-1, а это не все числа, которые нам нужны.

dion,

Тут еще нужно нормальный алгоритм вычисления найти. Если мы будем каждое число делить на все меньшие его числа, то далеко не уедем...

Алгоритм Miller-Rabin уже реализован в пакете GNU Multiplie Precision для работы с большими числами.

[dion]

dimichxp, пакет посмотрю.

[alo33]

Я тут пару прог нашел - может кому понадобятся
http://ktulu.com.ar/en/djohn.php
ОС: Unix
Описание: Основное назначение этого программного продукта - созданией некой распределённой сети для ускорения процесса взлома пароля, который основан на алгоритме работы популярного взломщика John The Ripper. Управляет распределением работы и ресурсов сервер под управлением djohnd, он же занимается координацией работы клиентов (программа djohn).
http://usuarios.lycos.es/reinob/
ОС: Cross-platform
Описание: Программа для взлома паролей при помощи словаря или непосредственно перебором по символам. Умеет подбирать пароль, используя регулярные выражения, что облегчает подбор при известной хотя бы некоторой части пароля. Поддерживает следующие виды паролей: MD4 hash, MD5 hash, NT MD4/Unicode, Lotus Domino HTTP password (R4) и SHA-1. LM (LAN Manager).

[dion]

Итак результаты сегодняшних переговором меня, gopher и dimichxp:

1. 2^512 длина 154-155 знаков
2. Перебор лучше начинать с 2^512-1 и в сторону убывания
3. Юзать будем пока это:

Код

  THE GNU MP LIBRARY


GNU MP is a library for arbitrary precision arithmetic, operating on signed
integers, rational numbers, and floating point numbers.  It has a rich set of
functions, and the functions have a regular interface.

GNU MP is designed to be as fast as possible, both for small operands and huge
operands.  The speed is achieved by using fullwords as the basic arithmetic
type, by using fast algorithms, with carefully optimized assembly code for the
most common inner loops for lots of CPUs, and by a general emphasis on speed
(instead of simplicity or elegance).

GNU MP is believed to be faster than any other similar library.  Its advantage
increases with operand sizes for certain operations, since GNU MP in many
cases has asymptotically faster algorithms.

GNU MP is free software and may be freely copied on the terms contained in the
files COPYING.LIB and COPYING (most of GNU MP is under the former, some under
the latter).

4. Я пока взялся за сервер. Себе я его представлю как CGI скрипт. Работать будет вместе с апачем. Его функции - только раздача кому что делать. Ни каких вычислений он выполнять не будут. Общаться с клиентами будет GET/POST запросами. Трафик между клиентом и сервером минимален: от сервера начальное и конечночные числа. Соответственно клиент отвечает что порцию проверил/еще не успел. На сервере должна быть БД mysql. В ней будут хранится кому какя порция дана, и когда клиент последний раз выходил на связь. + На сервере число N - последняя цифра, которую он отдал

5. Алгоритм работы сервера: При коннекте он смотрит в БД, есть ли там записи, что один из клиентов взял себе порцию но уже очень давно не выходил на связь (Допустим неделю., -> он забил). Если есть то клиенту выдается эта порция. Если таких записей нет, то выдается диапазон N...N+delta, где delta - количество цифр в порции. Дальше заносим эти данные в БД. N увеличиваем на delta

6. За клиент вроде как взялся dimichxp.

PS. Для сервера будет нужен хостинг с поддержкой CGI и MYSQL

[G.off]

dion,
молодчина! уже кое что...

[Vilko]

dion,
сервер именно cgi хочешь сделать? если сотворишь на php - то хост можно мой использовать, тарффика это дело вроде немного есть будет.

[Apostol]

Вопрос :
Высчитывать эти числа нужно будет самим или прога есть какая-то,кот. сама все сделает? :)

[dion]

Vilko, я пока просто на CGI остановился из-за незнания php. В нем из операций с длинными числами нужно будет просто сделать сложенние. В той либе оно уже реализованно. А траффика там действительно немного. Передаются то всего пару чисел.

Apostol, Та либа, цитату с README которой я приводил уже содержит пример, вычисляющий простые числа в заданном диапазоне. К ней нужно будет добавить GUI, общение с сервером ну и проверку каждого простого числа.

Сообщение отредактировал dion - 3.5.2005, 21:36

[4inut]

2dion,
А сколько по времени займет написание сервера и клиента?

[Apostol]

[b]Apostol/b], Та либа, цитату с README которой я приводил уже содержит пример, вычисляющий простые числа в заданном диапазоне. К ней нужно будет добавить GUI, общение с сервером ну и проверку каждого простого числа.

TO dion (Возможно торможу,сильно не пинай) Чет я не понял это ты мне ответил? если да, то лучше ответь : нужно ли будет,при вычислении чисел думать мозгами или нет