Прошу немного просветить про МД5.
Вобщем есть прошивка под контроллер. В ней проверяется целостность байт по следующей схеме:
Считается MD5 сумма, заданного количества байт (все полезные байты прошивки). Потом эта сумма криптуется алгоритмом RSA с 1760 битным ключем. Менять RSA ключи нельзя, они проверяются. (Вернее можно, но придется прошивку в корне переписать).
Что я хочу сделать. Увеличить размер проверяемых байт (например) на размер блока МД5, 64 байта. И подобрать эти последние добавленные байты, так чтобы сумма МД5 нового файла прошивки сошлась с суммой оригинальной прошивки.
Соответственно вопросы:
1. Не преувеличиваю-ли я размер добавляемых байт? Может достаточно добавить 4 - 16 байт?
2. Есть какие-то известные брутфорсы, которые допускают ввести начальную МД5, отличную от стандартной (0123456789ABCDEFFEDCBA9876543210), и считающую размер в битах для финального блока не от нуля, а от заданного размера?

| Сообщение посчитали полезным:

это тебе не crc32

-----
Array[Login..Logout] of Life

| Сообщение посчитали полезным:

Забей. Просто забей. То, что ты ищешь, называется "рассчет коллизии" и этого покамест никто еще не сделал. Когда сделают, можно будет забыть о цифровых подписях. Были пара ученых (японец и словак вроде), которые придумали туннелирование. Когда флипаешь несколько определенных бит на входе и получаешь как бы ту же хеш-сумму, но это скорей забавный фокус и практического никакого смысла не несет.

-----
2 оттенка серого

| Сообщение посчитали полезным:

Ну а по существу-то можно ответить? Я готов на брутфорс потратить и пол-года и год. В принципе сейчас прошивка работает как надо, но надо все сделать правильно. Есть комп, который можно не отключать. Если надо то и друзей подключу к брутфорсу.
Про коллизии читал, но это не мой случай. Там расчитывается один блок по оригинальному блоку. В моем случае оригинального блока нет. Поэтому только брутфорс.

| Сообщение посчитали полезным:

Это pre-image attack, сложность где-то 2^128, т.к. для MD5 нету хороших атак в случае pre-image.
Вы не сможете сделать такой перебор.

Можно попробовать сделать атаку meet-in-the-middle.
Нужно, чтобы паддинг в RSA не проверялся.
То есть, любой рандомный кусок байт должен считаться валидной подписью с неким MD5 хешем внутри.

Итак, на i-ом шаге вы генерите случайно подпись Si, расшифровываете ее публичным ключом, получаете некий MD5 хеш Hi.
Далее, генерите случайно прошивку, получаете хеш прошивки Li.
Согласно парадоксу дней рождения, одно из L1, ..., Li совпадет с одним из H1, ..., Hi при i около 2^(128/2)=2^64.
2^64 - возможно, не такой и сложный перебор.

Если не выйдет, то есть всякие атаки на подпись RSA, кроме тупо факторизации, но там жесть.

| Сообщение посчитали полезным:

Атаки на RSA я не рассматриваю. Только на МД5.
Хотя-бы на первый вопрос ответьте? Хватит добавки из 4-16 байт или обязательно 64 байта?

| Сообщение посчитали полезным:

Подбор хеша MD5 сводится к одному простому действию - вы рандомно меняете что-то в прошивке и получаете совершенно случайный хеш.
Длина прибавки вообще ни на что не влияет, это все равно случайный хеш.

| Сообщение посчитали полезным:

Kuzya69 пишет:
Хотя-бы на первый вопрос ответьте? Хватит добавки из 4-16 байт
Не факт, что хватит 64. МД5 считается с блоков по 64 байта, хвост выравнивается. У тебя на выходе 2^(8*16) комбинаций, ты хочешь с 2^32 туда заехать?

-----
2 оттенка серого

| Сообщение посчитали полезным:

Гуглится элементарно, зачем с этим на форум приходить(.

Для MD4 достаточно просто находится, даже в тасках CTF попадается подобное.
Для MD5 тяжелее.

Теория и исходный код: http://www.win.tue.nl/hashclash/
Пример использования: https://natmchugh.blogspot.com/2015/02/create-your-own-md5-collisions.html

-----
127.0.0.1, sweet 127.0.0.1

| Сообщение посчитали полезным:

OKOB, надо различать pre-image attack и collision attack.
Вы дали ссылку на collision attack. Человеку нужен pre-image attack, точнее даже 2nd pre-image attack.

| Сообщение посчитали полезным:

..Теория и исходный код..
Опять вы про коллизии, это не мой случай. Мне нельзя менять байты прошивки, чтобы подобрать коллизию, мне как-бы надо подобрать пароль (комбинацию байт) под известный хэш. При заданном начальном векторе и заданном размере в битах.

| Сообщение посчитали полезным:

Мужыки, так вот эта фигня реалистична или нет?
https://exelab.ru/f/action=vthread&forum=5&topic=25222#5
2^64 шагов нужно сделать, описанных выше.
Сколько будет стоить, сколько времени, если на ботнете, и т.п.?

| Сообщение посчитали полезным:

Kuzya69 пишет:
Мне нельзя менять байты прошивки, чтобы подобрать коллизию,
Твоя задача взять значение предпоследней итерации MD5 и подбирать содержимое последнего буфера. Это то же самое, только даже хуже, учитывая поле длины в нем.

Добавлено спустя 6 минут
kunix пишет:
Можно попробовать сделать атаку meet-in-the-middle.
Это техника Блехенбахера, 2006 год. Работает только с публичной экспонентой 3, уже давным-давно все либо от нее отказались, либо ввели значащее поле в младших битах.

-----
2 оттенка серого

| Сообщение посчитали полезным:

Kuzya69, какой алгоритм проверки подписи?
Какая экспонента, какой паддинг, как проверяется?
Просто есть еще атака кубического корня, если экспонента=3 и проверка паддинга с ошибкой.\

[f13nd пишет:
Это техника Блехенбахера, 2006 год. Работает только с публичной экспонентой 3, уже давным-давно все либо от нее отказались, либо ввели значащее поле в младших битах.
Что-то мне кажется, это две совершенно разные атаки.
meet-in-the-middle насрать на экспоненту.

| Сообщение посчитали полезным:

Твоя задача взять значение предпоследней итерации MD5 и подбирать содержимое последнего буфера.
Все верно, только все брутфорсы, которые я находил, подбирают со стандартным начальным вектором и считают размер от начала подбираемого "пароля". А тут надо немного изменять алгоритм брутфорса. Может кто встречал уже готовый, под мою задачу? Боюсь сам я его не напишу, я знаком только с Делфи. Вернее напишу, но он будет медленным.
какой алгоритм проверки подписи?
Я-же писал - RSA с 1760 битным ModulusN. После декриптовки, обычное побайтное сравнение.
Какая экспонента, какой паддинг, как проверяется?
Экспонента стандартная 0х10001, а вот что такое паддинг, пойду гуглить, я такое слово первый раз слышу.
Если неправильно понял, то поправьте. Если паддинг - это добивка криптуемых байт до определенного размера сообщения, то в моем случае к МД5-сумме, перед криптовкой в RSA, спереди, добавляются 0х12 байт, и они тоже учавствуют в побайтном сравнении. Я это не написал сразу, так как считал, что это не важно.
Но вообще, мне не нужно RSA трогать, пусть остается как есть. Мне нужен подбор МД5.

| Сообщение посчитали полезным:

kunix пишет:
вы попутали две совершенно разные атаки.
Ну допустим, у меня глаз за "Нужно, чтобы паддинг в RSA не проверялся" зацепился. По сути то же самое и на той же уязвимости основано.

Добавлено спустя 7 минут
Kuzya69 пишет:
Я-же писал - RSA с 1760 битным ModulusN. После декриптовки, обычное побайтное сравнение.
128 бит или 1760 сравнивает?

-----
2 оттенка серого

| Сообщение посчитали полезным:

128 бит или 1760 сравнивает?
272 бита сравниваются. Там даже немного посложнее, еще перед этими битами-байтами, дожны стоять 0хFF байты обязательно, иначе проверку не пройдет.

| Сообщение посчитали полезным:

Kuzya69 пишет:
272 бита сравниваются. Там даже немного посложнее, еще перед этими битами-байтами, дожны стоять 0хFF байты обязательно, иначе проверку не пройдет. Ну значит парадокс дней рождения и 136 бит экспоненциального модулирования. Займет это год или меньше, не узнаешь, пока не попробуешь.

-----
2 оттенка серого

| Сообщение посчитали полезным:

Kuzya69 пишет:
272 бита сравниваются. Там даже немного посложнее, еще перед этими битами-байтами, дожны стоять 0хFF байты обязательно, иначе проверку не пройдет.
Если так, то meet-in-the-middle без шансов
Будете перебирать до тепловой смерти вселенной.
Перебор уже 2^80 вариантов считается невозможным.

Kuzya69 пишет:
Мне нужен подбор МД5.
Вы не подберете содержимое прошивки по заданному MD5 хешу, еще раз повторяю, прямым текстом.
Там будет сложность где-то 2^128.

Kuzya69 пишет:
Экспонента стандартная 0х10001
Про атаку Bleichenbacher можно забыть.

| Сообщение посчитали полезным:

Ну кстати хешклеш можно посмотреть https://github.com/cr-marcstevens/hashclash-old-svn-repo/blob/master/downloads/hashclash-r38-win32-cpcgui-beta.zip
Напиши что он выдаст.

-----
2 оттенка серого

| Сообщение посчитали полезным:

Там будет сложность где-то 2^128.
Это понятно, но это максимальная сложность. Вероятность попадания на меньшей размерности добавляемых байт все-же существует (не 16 байт, а например 8).
Кто-бы помог подправить исходник BarsWF, чтобы принимал в параметрах начальный вектор и начальную длину? Я в Сях не силен, была бы Делфи, разобрался-бы.
Ну кстати хешклеш можно посмотреть...
Ну тут что-то много настроек, может лучше выложить что нужно, и сами посмотрите, боюсь быстро я с этой прогой не разберусь. Скажите какие данные нужны, выложу.

| Сообщение посчитали полезным:

Kuzya69 пишет:
Кто-бы помог подправить исходник BarsWF, чтобы принимал в параметрах начальный вектор и начальную длину?


В 15й раз напоминаю, что длина у тебя в последнем кадре и подбираешь ты только его. Не подойдет тебе эта программа. Хешклеш вон вверху предназначен для подгонки мд5 одного файла под мд5 другого, шут его знает работает ли оно и сколько.

-----
2 оттенка серого

| Сообщение посчитали полезным:

В 15й раз напоминаю, что длина у тебя в последнем кадре и подбираешь ты только его. Не подойдет тебе эта программа.
А вот это высказывание не понятно. BarsWF работает с паролями длиной 1-15 символов-байт. Как раз получается последний кадр. Т.е. он на лету меняет размер в последнем блоке. Когда только начинаются итерации, он присваивает длине значение 0 (или 1), и постепенно ее длину инкрементирует. Если в самом начале задать не 0(или 1), а то что введем в параметрах, то все будет идти и дальше как надо.

| Сообщение посчитали полезным:

Kuzya69 пишет:
и постепенно ее длину инкрементирует

Инкременирует от 1 до 15? Длина вот. В каждом способе надо самому это выставлять в исходнике.


-----
2 оттенка серого

| Сообщение посчитали полезным:

Инкременирует от 1 до 15?
Я язык Си не понимаю, но это естественно вытекает из алгоритма брутфоса. Прога начинает с коротких паролей и переходит к следующим.
Правда там есть еще параметр как минимальная длина пароля. Тут я не знаю как реализовано.
В каждом способе надо самому это выставлять в исходнике.
Скорее всего в исходнике можно выставить максимальную длину, чтобы прога не брутила до конца вселенной. А в параметрах, можно задать минимальную длину.
for(int i=0;i<4;i++)
Да и наверное это не то. Откуда "i<4" взялось? Это скорее размерность Dword-а, единицы информации для МД5.

| Сообщение посчитали полезным:

А как меняют прошивки для этого девайса штатным образом?

| Сообщение посчитали полезным:

dosprog пишет:
А как меняют прошивки для этого девайса штатным образом?
Штатным образом очевидно прошивка с валидной цифровой подписью.

-----
2 оттенка серого

| Сообщение посчитали полезным:

Штатным образом очевидно прошивка с валидной цифровой подписью.
Так точно. Только мы не знаем закрытой экспоненты, чтобы самим подписать изменившуюся МД5 сумму.

| Сообщение посчитали полезным:

Там точно не участвует размер кода? - Откуда такая уверенность?

И проверками занимается код из этой самой прошивки?
- Это к тому, что в таком случае надо ковырять это самое гадство в самой прошивке.
Если это возможно



| Сообщение посчитали полезным:

Kuzya69 пишет:
Да и наверное это не то. Откуда "i<4" взялось?

Взял бы уже реализацию мд5 на понятном тебе языке да посмотрел. Цикл лишним видимо зацепил. Размер 8 последних байт кадра, в битах. Следующий за последним байтом выставляется 0x80. Set32 очевидно длину устанавливает. Для пароля 32бит длины за глаза.

Добавлено спустя 15 минут
dosprog пишет:
- Это к тому, что в таком случае надо ковырять это самое гадство в самой прошивке.
Знал бы ты, как это ковыряют, не имея возможности поменять алгоритм проверки. И флеш умудряются без стирания патчить единицами поверх через дыру в протоколе, лишь бы это обмануть; и неиспользуемые инженерные интерфейсы находят чтоб подрезать ключ для авторизации тоже в инженерном режиме прямо из оперативки. А некоторые даже то ли покупают у разработчиков, то ли воруют с заводов рса ключи для этой авторизации.

-----
2 оттенка серого

| Сообщение посчитали полезным: