Сейчас на форуме: tyns777, Lohmaty (+6 невидимых)

 eXeL@B —› Вопросы новичков —› Как подобрать добавочные байты, чтобы сошлась MD5 сумма файла?
<< . 1 . 2 . 3 .
Посл.ответ Сообщение

Ранг: 30.1 (посетитель)
Активность: 0.07↘0
Статус: Участник

 Создано: 23 июня 2018 19:20
· Личное сообщение · #1

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



Ранг: 315.1 (мудрец), 631thx
Активность: 0.3↗0.33
Статус: Модератор
CrackLab

 Создано: 24 июня 2018 01:19
· Личное сообщение · #2

Kuzya69
Тебе же 10 раз сказали, что это нереально
Запускай факторизацию рса, ибо тоже есть вероятность, что первые числа подойдут.




Ранг: 312.0 (мудрец), 349thx
Активность: 0.46↗0.65
Статус: Участник
Advisor

 Создано: 24 июня 2018 01:21
· Личное сообщение · #3

Kuzya69 пишет:
На выходе может быть абсолютно непредсказуемое значение.
содержимое да, но длинна выхлопа не меняется.

-----
Чтобы юзер в нэте не делал,его всё равно жалко..

Ранг: 30.1 (посетитель)
Активность: 0.07↘0
Статус: Участник

 Создано: 24 июня 2018 01:26
· Личное сообщение · #4

Запускай факторизацию рса, ибо тоже есть вероятность, что первые числа подойдут.
Запускал уже, и если грамотно подобраны сомножители под ModulusN, то там действительно ловить нечего, на больших числах. Потому-как коллизии исключены. А на МД5, коллизии есть, и их может быть очень много, и никто не знает сколько их.
содержимое да, но длинна выхлопа не меняется.
Да. А где я другое мог написАть?



Ранг: 158.4 (ветеран), 123thx
Активность: 0.14↗0.49
Статус: Участник

 Создано: 24 июня 2018 01:27
· Личное сообщение · #5

Bronco пишет:
а откуда такая уверенность, что на входе значение меньше чем его хеш на выходе из алго?
Ну, он же задачу так ставит: посчитать хеш от патченной прошивки, а потом использовать его как вектор инициализации и добручивать хвост в 1..8 байт, пока не получится нужный оригинальный хеш.




Ранг: 312.0 (мудрец), 349thx
Активность: 0.46↗0.65
Статус: Участник
Advisor

 Создано: 24 июня 2018 01:46 · Поправил: Bronco
· Личное сообщение · #6

rmn пишет:
а потом использовать его как вектор инициализации
угу...очевидно инит вектор уже в другом алгоритме, допускаю что это RSA.
ну соль от мд5 можно и от не патченного массива получить, главное чтобы дамп прошивки был.
только смысл её брутить, мне не понятен. если диспут о содержимом массива, и подбора цепочки байт, то ответ во втором посте, это не црц32, не прокатит.

-----
Чтобы юзер в нэте не делал,его всё равно жалко..


Ранг: 271.2 (наставник), 331thx
Активность: 0.32↗1.49
Статус: Участник

 Создано: 24 июня 2018 02:20
· Личное сообщение · #7

Bronco пишет:
только смысл её брутить, мне не понятен. может быть чтоб цифровая подпись валидной стала, но это не точно.

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

Ранг: 431.7 (мудрец), 390thx
Активность: 0.73↘0.32
Статус: Участник

 Создано: 24 июня 2018 09:08
· Личное сообщение · #8

Мда. За время обсуждения уже можно было залепить примитивный брутер
и к этому моменту уже оно бы само показало, реально ли задуманное, или нет..



Ранг: 71.2 (постоянный), 33thx
Активность: 0.05↗0.12
Статус: Участник

 Создано: 24 июня 2018 09:51 · Поправил: kunix
· Личное сообщение · #9

Тут кто-то писал, что 2^64 перебрать нереально.
Вики другого мнения.
https://en.wikipedia.org/wiki/MD5CRK

В таком случае, блин, есть следующая идея. Я и не думал, что такое возможно, если честно.
Итак, мы пропатчили прошивку без изменения длины. Хеш прошивки изменился, длина осталась той же.
Допустим, в конце прошивки после всех патчей остался некий 64-байтный блок, который мы можем свободно патчить.

Рассмотрим, как работает тело цикла for i from 0 to 63.
Пусть M[i] - это i-ый байт текущего 64-байтного блока, а S[i] = (A,B,C,D) - текущее состояние в начале i-ой итерации, четыре DWORD-а, 16 байт.

Там в теле цикла фактически что-то типа S[i+1] = FU(S[i],i,M[i]).
Причем, если посмотреть на https://upload.wikimedia.org/wikipedia/commons/thumb/a/a5/MD5_algorithm.svg/300px-MD5_algorithm.svg.png, видно,
что эта FU - обратимая функция, т.е. зная i и M[i] мы можем так же быстро вычислить S[i] = UF(S[i+1],i,M{i}).

Тогда у нас c одной стороны
S[32] = FU(F[31],31,M[31]) = FU(FU(F[30],30,M[30]),31,M[31]) = ... = FU1(S[0],M[0],...,M[31]);
И с другой стороны
S[32] = UF(S[33], 32, M[32]) = UF(UF(S[34], 33, M[33]), 32, M[32]) = ... = UF1(S[64],M[32],...,M[63]);
S[0] и S[64] заданы извне.
Мы выбираем их так, чтобы все раунды MD5 после текущего вычислялись как в старой прошивке.
В частности, нужно учесть вот это
Code:
  1. //Add this chunk's hash to result so far:
  2.     a0 := a0 + A
  3.     b0 := b0 + B
  4.     c0 := c0 + C
  5.     d0 := d0 + D


Итак, нам похимичить с M[0],...,M[31] и M[32],...,M[63], чтобы совпало S[32], 16 байт.
Короче, можно делать birthday attack, сложность будет 2^64.
Достаточно, чтобы длина прошивки не менялась и был 64-байтный блок после всех патчей, который мы можем свободно менять.
Короче, это некий пиздец. Где я ошибся?

РАЗОБРАЛСЯ... Суть в том, что там на самом деле
S[32] = FU1(S[0],M[0],...,M[31],M[32],...,M[63]);
S[32] = UF1(S[64],M[0],...,M[31],M[32],...,M[63]);
Поэтому не получится посчитать их независимо.


Псевдокод MD5 с википедии:
https://en.wikipedia.org/wiki/MD5
Code:
  1. //Note: All variables are unsigned 32 bit and wrap modulo 2^32 when calculating
  2. var int[64] s, K
  3. var int i
  4.  
  5. //s specifies the per-round shift amounts
  6. s[ 0..15] := { 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22 }
  7. s[16..31] := { 5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20 }
  8. s[32..47] := { 4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23 }
  9. s[48..63] := { 6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21 }
  10.  
  11. //Use binary integer part of the sines of integers (Radians) as constants:
  12. for i from 0 to 63
  13.     K[i] := floor(232 &#215; abs(sin(i + 1)))
  14. end for
  15. //(Or just use the following precomputed table):
  16. K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
  17. K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 }
  18. K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be }
  19. K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 }
  20. K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa }
  21. K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 }
  22. K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed }
  23. K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a }
  24. K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c }
  25. K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 }
  26. K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 }
  27. K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 }
  28. K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 }
  29. K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 }
  30. K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 }
  31. K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }
  32.  
  33. //Initialize variables:
  34. var int a0 := 0x67452301   //A
  35. var int b0 := 0xefcdab89   //B
  36. var int c0 := 0x98badcfe   //C
  37. var int d0 := 0x10325476   //D
  38.  
  39. //Pre-processing: adding a single 1 bit
  40. append "1" bit to message    
  41. // Notice: the input bytes are considered as bits strings,
  42. //  where the first bit is the most significant bit of the byte.[48]
  43.  
  44. //Pre-processing: padding with zeros
  45. append "0" bit until message length in bits &#8801; 448 (mod 512)
  46. append original length in bits mod 264 to message
  47.  
  48. //Process the message in successive 512-bit chunks:
  49. for each 512-bit chunk of padded message
  50.     break chunk into sixteen 32-bit words M[j], 0 &#8804; j &#8804; 15
  51. //Initialize hash value for this chunk:
  52.     var int A := a0
  53.     var int B := b0
  54.     var int C := c0
  55.     var int D := d0
  56. //Main loop:
  57.     for i from 0 to 63
  58.         var int F, g
  59.         if 0 &#8804; i &#8804; 15 then
  60.             F := (B and C) or ((not B) and D)
  61.             g := i
  62.         else if 16 &#8804; i &#8804; 31 then
  63.             F := (D and B) or ((not D) and C)
  64.             g := (5&#215;i + 1) mod 16
  65.         else if 32 &#8804; i &#8804; 47 then
  66.             F := B xor C xor D
  67.             g := (3&#215;i + 5) mod 16
  68.         else if 48 &#8804; i &#8804; 63 then
  69.             F := C xor (B or (not D))
  70.             g := (7&#215;i) mod 16
  71. //Be wary of the below definitions of a,b,c,d
  72.         F := F + A + K[i] + M[g]
  73.         A := D
  74.         D := C
  75.         C := B
  76.         B := B + leftrotate(F, s[i])
  77.     end for
  78. //Add this chunk's hash to result so far:
  79.     a0 := a0 + A
  80.     b0 := b0 + B
  81.     c0 := c0 + C
  82.     d0 := d0 + D
  83. end for
  84.  
  85. var char digest[16] := a0 append b0 append c0 append d0 //(Output is in little-endian)
  86.  
  87. //leftrotate function definition
  88. leftrotate (x, c)
  89.     return (x << c) binary or (x >> (32-c));


Ранг: 271.2 (наставник), 331thx
Активность: 0.32↗1.49
Статус: Участник

 Создано: 24 июня 2018 10:16 · Поправил: f13nd
· Личное сообщение · #10

kunix пишет:
Тут кто-то писал, что 2^64 перебрать нереально.
Если о предложенной ранее meet-in-middle на саму цп, то каждая итерация подразумевает проверку получившейся цп публичным ключем. RSA в чистом виде практически нигде не применяется, потому что кампуцер не умеет ни умножать ни делить, может это делать только сложением-сравнением с чудовищными потерями времени.

Не знаю что ты в псевдокоде углядел, МД5 это FF, GG, HH и II-операции над разными комбинациями A,B,C,D (один из которых обновляется каждой такой операцией), даннми из буфера и константой. Предыдущее состояние МД5 в конце складывается с получившимися A,B,C,D. Не понял что ты хочешь "посчитать быстро".

Получить A можно без 3 последних операций, B,C,D соответственно без 0,1 и 2, больше из алгоритма нечего выбрасывать и "посчитать быстро" без всего остального - как?
Code:
  1. stdcall md5_II,[nA],[nB],[nC],[nD],dword [binCalcBuffer+04*4],06,0xF7537E82
  2. mov [nA],eax
  3. stdcall md5_II,[nD],[nA],[nB],[nC],dword [binCalcBuffer+11*4],10,0xBD3AF235
  4. mov [nD],eax
  5. stdcall md5_II,[nC],[nD],[nA],[nB],dword [binCalcBuffer+02*4],15,0x2AD7D2BB
  6. mov [nC],eax
  7. stdcall md5_II,[nB],[nC],[nD],[nA],dword [binCalcBuffer+09*4],21,0xEB86D391
  8. mov [nB],eax


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

Ранг: 71.2 (постоянный), 33thx
Активность: 0.05↗0.12
Статус: Участник

 Создано: 24 июня 2018 10:31 · Поправил: kunix
· Личное сообщение · #11

f13nd пишет:
Если о предложенной ранее meet-in-middle на саму цп, то каждая итерация подразумевает проверку получившейся цп публичным ключем. RSA в чистом виде практически нигде не применяется, потому что кампуцер не умеет ни умножать ни делить, может это делать только сложением-сравнением с чудовищными потерями времени.
Я вообще говорил о возможности совершения 2^64 операций средне-малой вычислительной сложности на доступном железе.
Если одна операция медленнее другой в 100 раз, можно взять ботнет в 100 раз больше, понимаешь?
Поэтому разброс достаточно большой может быть.
Это все равно лишь грубые прикидки.


f13nd пишет:
Не знаю что ты в псевдокоде углядел, МД5 это FF, GG, HH и II-операции над разными комбинациями A,B,C,D, даннми из буфера и константой.
MD5 - это в первую очередь хеш-функция, построенная из некоего блочного шифра по Merkle–Damgård, с внутренним состоянием 16 байт.
Я не разбираюсь в этом псевдокоде с FF, GG, HH и II, мне надо подумать.
Мне нравится псевдокод у википидоров, там все более-менее понятно.

Добавлено спустя 6 минут
f13nd пишет:
Не знаю что ты в псевдокоде углядел, МД5 это FF, GG, HH и II-операции над разными комбинациями A,B,C,D (один из которых обновляется каждой такой операцией), даннми из буфера и константой. Предыдущее состояние МД5 в конце складывается с получившимися A,B,C,D. Не понял что ты хочешь "посчитать быстро".

Если я верно понимаю, все эти FF, GG, HH и II - обратимые операции (если знать кусок сообщения M[i], конечно).
Единственная необратимая операция - это сложение в конце, но мой метод работает внутри одного блока, между двумя сложениями, ему похер на сложения.

UPD:

Ну короче, эти FF, GG, HH, II - это итерации цикла. Это все FU в моей терминологии.
Они обратимы, если знать нужный байт сообщения.
Code:
  1. #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
  2. #define FF(a, b, c, d, x, s, ac) \
  3.   {(a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \
  4.    (a) = ROTATE_LEFT ((a), (s)); \
  5.    (a) += (b); \
  6.   }


Ранг: 271.2 (наставник), 331thx
Активность: 0.32↗1.49
Статус: Участник

 Создано: 24 июня 2018 10:38
· Личное сообщение · #12

kunix пишет:
можно взять ботнет в 100 раз больше, понимаешь? Если всю мочу собрать, да при том умело, можно солнце обосцать, чтоб оно шипело!

kunix пишет:
Я не разбираюсь в этом псевдокоде с FF, GG, HH и II, мне надо подумать. Просто он нифига непонятен и все. Ключевое слово "внутреннее состояние", которое меняется в процессе, и не проделав всю последовательность, "быстро получить результат" нельзя.

Добавлено спустя 17 минут
kunix пишет:
Ну короче, эти FF, GG, HH, II - это итерации цикла. Это все FU в моей терминологии.
Они обратимы, если знать нужный байт сообщения.
Что во что ты обратишь? Мгновенные значения A,B,C,D в нужный байт буфера? Из чего ты обратишь эти самые мгновенные A,B,C,D? Из других мгновенных значений двигаясь либо от предыдущего значения МД5, либо от последующего. И там другие значения байт из буфера будут участвовать, их ты откуда обратишь?

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

Ранг: 71.2 (постоянный), 33thx
Активность: 0.05↗0.12
Статус: Участник

 Создано: 24 июня 2018 11:04 · Поправил: kunix
· Личное сообщение · #13

f13nd, чувак, ты просто нихуя не понял, что я написал.
Значения буфера я задаю сам, случайным образом, ферштейн?
Моя задача, задавая значения буфера, свести концы с концами.
А именно, чтобы один S[32] совпал с другим S[32].
Так как S[32] - всего 16 байт, я это сделаю за 2^{128/2} = 2^64 операций.




Ранг: 271.2 (наставник), 331thx
Активность: 0.32↗1.49
Статус: Участник

 Создано: 24 июня 2018 11:07
· Личное сообщение · #14

kunix пишет:
Моя задача, задавая значения буфера, свести концы с концами. Значения буфера задаешь ты сам и "быстро проверяешь, не применив весь алгоритм"... Как?

Добавлено спустя 15 минут
kunix пишет:
А именно, чтобы один S[32] совпал с другим S[32].
Так как S[32] - всего 16 байт, я это сделаю за 2^{128/2} = 2^64 операций.
S(0) инициализирующее значение, S(64) значение на выходе, S(32) очевидно посередине. Подобрать такие значения М[0..31] и М[32..63], чтоб S(33..63) совпадали с эталонными. Учитывая то, что каждый из байтов M используется по во всём алгоритме по 4 раза, мне кажется это дичь какая-то. Ну попробуй.

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

Ранг: 71.2 (постоянный), 33thx
Активность: 0.05↗0.12
Статус: Участник

 Создано: 24 июня 2018 11:26 · Поправил: kunix
· Личное сообщение · #15

f13nd пишет:
S(0) инициализирующее значение, S(64) значение на выходе, S(32) очевидно посередине. Подобрать такие значения М[0..31] и М[32..63], чтоб S(33..63) совпадали с эталонными. Учитывая то, что каждый из байтов M используется по во всём алгоритме по 4 раза, мне кажется это дичь какая-то. Ну попробуй.
Да, вот где я ошибся. Перепутал K[i] с M[g]. Думал, каждый байт буфера лишь один раз используется.

UPD.
Но гляди, если получится найти 4 DWORD-а в исходном буфере и некое S[k] так, первые два DWORD-а применяются до S[k], а вторые два после S[k], то все сработает.
Это я к чему - самостоятельно хороший криптографически стойкий хеш сходу придумать ну очень сложно.
Будет куча проебов.




Ранг: 271.2 (наставник), 331thx
Активность: 0.32↗1.49
Статус: Участник

 Создано: 24 июня 2018 12:08 · Поправил: f13nd
· Личное сообщение · #16

kunix пишет:
найти 4 DWORD-а в исходном буфере и некое S[k] так, первые два DWORD-а применяются до S[k], а вторые два после S[k], то все сработает.
Сомневаюсь. Я в свое время с рипемд160 просто конское количество часов просидел, раскидав его на and/or/xor операции над отдельными битами, и какой только дичи не перепробовал с этим графом. Есть там узлы потяжелей с 10-12 связями, но даже их перебор никаких похожих на успех результатов не принес. Это комплексная задача и на ряд элементарных не раскладывается.

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

Ранг: 71.2 (постоянный), 33thx
Активность: 0.05↗0.12
Статус: Участник

 Создано: 24 июня 2018 12:13
· Личное сообщение · #17

f13nd,
Для MD5 даже два таких DWORD не найти, там все неплохо перемешано.
Правда, есть еще такая вещь как multidimensional meet-in-the-middle
Но врядли что-то выйдет хорошее..



Ранг: 30.1 (посетитель)
Активность: 0.07↘0
Статус: Участник

 Создано: 25 июня 2018 12:17 · Поправил: Kuzya69
· Личное сообщение · #18

Еще вопросик можно? Каким компиллятором лучше воспользоваться, чтобы собрать исходник BarsWF, в исполняемые файлы под разные реализации (AMD, nVidia, SSE2, 32, 64 bits) ? Вроде нашел некоторые нужные участки кода, попробую исправить.




Ранг: 271.2 (наставник), 331thx
Активность: 0.32↗1.49
Статус: Участник

 Создано: 25 июня 2018 12:29
· Личное сообщение · #19

Kuzya69 пишет:
Каким компиллятором лучше воспользоваться, чтобы собрать исходник BarsWF
Файлы с расширением .vcxproj как бы намекают на главный сишный компилятор MS Visual Studio.

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

| Сообщение посчитали полезным: Kuzya69
<< . 1 . 2 . 3 .
 eXeL@B —› Вопросы новичков —› Как подобрать добавочные байты, чтобы сошлась MD5 сумма файла?
:: Ваш ответ
Жирный  Курсив  Подчеркнутый  Перечеркнутый  {mpf5}  Код  Вставить ссылку 
:s1: :s2: :s3: :s4: :s5: :s6: :s7: :s8: :s9: :s10: :s11: :s12: :s13: :s14: :s15: :s16:


Максимальный размер аттача: 500KB.
Ваш логин: german1505 » Выход » ЛС
   Для печати Для печати