Помогите оптимизировать на скорость...

Написал я вот подборщик CRC32 (ну вернее не совсем CRC32), собственно и за асм взялся чтоб его написать. Работать стал быстрее, но всеравно на полный перебор 10-тизначных авриантов нужно не одна тысяча лет. Если кому не трудно, посмотрите, может ктонить чтонить и переделает... задача чтоб быстрее переберало. Очень надо !!!!... сейчас на селероне 1.7, 256мб памяти перебирает со скоростью 20 000 000 в секунду... исходники в архиве. Очень тормозит чтение из памяти, но обойти его не придумал как. Если что-нибудь коряво написано - не смеятся, это первая прога на асме.



Заранее спасибо..

_1054071320__Brut.zip

 

Тебе надо найти любой пасс, CRC32 которого будет равно 0E40BE346h ?

 

Не любой, а ВСЕ... ну в разумных пределах конечно, примерно до 12-тизначных включительно (хотябы)... и алгоритм этот не совсем CRC32 (хотя очень похож), потомучто те пасы которые находит мой подборщик имеют CRC другое (я проверял калюкулятором хэшэй), но одинаковое у всех... а та прога в которую этот пас ввожу хавает любой, но если неправильный (хотя и в зашифрованом виде выглядит как 0E40BE346h) то выдаёт рантайм-ерор... вобщем потом из всех найденых нада будет найти тот единственный и неповторимый.



очень ресурсоёмкой по времени командой является вот эта :

movzx ESI, byte ptr [EBX+EBP]



её как-то можно заменить lodsb, но у меня не получается, и так все регистры задействованы (кроме ECX), а ей нужны AEX и ESI



Та и вообще неплохо былоб пересмотреть сам алгоритм генерации слов для перебора, может и его можна ка-то оптимизировать...

 

Msg_pass db "PASSWORD FOUND : ", 0



Судя по этой строке ты должен знать, что н0ль является признаком её конца, так вот у тебя обычный CRC32! С той лишь разницей, что в твоем исходнике этот н0ль включается в расчет контрольной суммы, а в калюкуляторе хешей не включается, как в той проге я не знаю, но перепроверь обязательно



movzx ESI, byte ptr [EBX+EBP] не должна быть ресурсоемкой, lodsb тоже бесполезен, у тебя плохая реализация (может завтра уже посмотрю подробно код и перепишем), CRC32 можно посчитать примерно таким кодом

Код (Text):

1. ;=====================================================================
2.             mov     ebx,offset sPass + sizeof.sPass
3.             mov     ecx,- sizeof.sPass
4. ;=====================================================================
5. crc32:      xor     edx,edx
6.             or      eax,-1
7. @@:         mov     dl,byte ptr [ebx + ecx]
8.             xor     dl,al
9.             shr     eax,8
10.             xor     eax,dword ptr [offset RandomArr + edx*4]
11.             inc     ecx
12.             jnz     @b
13.             not     eax
14. ;=====================================================================

Но сперва прочти http://reng.ru/board/viewtopic.php?t=1637 и определись, надо ли тебе ВСЕ пароли

 

Спасибо за линк, уже читал. Ноль должен включатся полюбому, это делает та прога для которой собственно пароль и подбираю. Пароли действительно нужны все, немного обьясню : та прога для которой подбираю пароль хранит CRC правильного пароля, правильный пароль нужен для расшифровки файлов, тоесть если ввести вместо правильного любой другой у которого CRC такая же, то прога его примет, но файлы то всёравно не расшифруются, тоесть единсвенный вариан - найти все пароли, а потом вручную проверять тот или нет...



movzx ESI, byte ptr [EBX+EBP] ресурсоёмка потому что в ней происходит чтение из памяти, которая намного медленнее процессора, строка ведь выполняется для каждого символа в пароле, когда я её коментирую - скорость возрастает намного.. в одной из статей в разделе "оптимизация" написано что lodsb будет быстрее, но заменить у меня не получилось, может я что-то не так понял...

 

Ты уверен? Что там за алгоритм шифрования? ИМХО его тоже надо обязательно посмотреть, хотя бы для выяснения какой длины может быть пароль шифрования (для сокращения перебора)

Это да, но только в начале! 1 Кб CRC32 таблица (RandomArr) быстро окажется в кеше L1 и никакого чтения памяти не будет, lodsb в твоем случае не поможет!

 

Какой алгоритм шифрования не знаю.. в CRC еле разобрался, могу скинуть прогу - поковыряеш, 11мб весит...



в строке movzx ESI, byte ptr [EBX+EBP] не из црц таблици байты берутся, а из строки с проверяемым паролем, которая каждый раз разная.

Кстати есть ещё идея запоминать зашифрованую строку без одного символа, а потом не перешифровывать заново все символы, а брать уже зашифрованые, и шифровать ещё с одним (который изменился), а когда меняется больше одного перешифровывать всю строку.... но реализовать у меня тоже не получилось...

 

Не, дофига (такой объем разве ночью качать, можешь посмотреть какая иногда у меня скорость



По поводу строки с паролем, она то разная, но тоже должна быть в кеше или буфере вывода из конвеера



По поводу идеи давно понятно как надо делать, црц для всего считать не надо, только последние 4 байта (которые попробуем держать\инкрементировать в регистре, реализация не за горами)



Надо определится с длиной пароля! Натрави Cryptosearcher (в инструментах wasm.ru раздел крипто если не ошибаюсь) на прогу, какие она понаходит алгоритмы кроме црц?

 

LAZAR

> "в строке movzx ESI, byte ptr [EBX+EBP] не из црц таблици байты берутся, а из строки с проверяемым паролем, которая каждый раз разная"



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



А тормозок у тебя может быть в inc EBX, т.к. inc сама по себе не шустрая инструкция (ждет установки флага CF от предыдущей операции) а тут еще и movzx ее вынуждена ждать. Поэтому inc EBX лучше засунуть куду-нить в середину или в конец цикла и еще лучше заменить на add EBX,1.



И еще не стоит пренебрегать выравниванием переменных. После RandomArr лучше сначала разместить все dd, затем sPass (можно с align 32, чтобы целиком в линейке кэша была) и уж потом маловажные строки Msg и т.п.

 

С оптимизацией потом разберемся надо подумать насколько вероятно найти пароль, посмотрел прогу и имеем ситуацию: Это инсталлятор (Gentee installer), для установки программы сперва необходимо ввести пароль (длина до 256 любых символов) CRC32 которого будет = 0xE40BE346, если совпадает то на основе пароля строится таблица 256 байт, оч. похожа на построение RC4 но попроще, из пароля "5553",0 получилась такая:

Код (Text):

1. 01 05 05 09 09 15 15 11 11 15 15 69 69 65 65 61
2. 61 65 65 69 69 55 55 51 51 55 55 49 49 45 45 41
3. 41 45 45 49 49 55 55 51 51 55 55 69 69 65 65 61
4. 61 65 65 69 69 95 95 91 91 95 95 89 89 85 85 81
5. 81 85 85 89 89 95 95 91 91 95 95 69 69 65 65 61
6. 61 65 65 69 69 55 55 51 51 55 55 49 49 45 45 41
7. 41 45 45 49 49 55 55 51 51 55 55 69 69 65 65 61
8. 61 65 65 69 69 15 15 11 11 15 15 09 09 05 05 01
9. 01 05 05 09 09 15 15 11 11 15 15 69 69 65 65 61
10. 61 65 65 69 69 55 55 51 51 55 55 49 49 45 45 41
11. 41 45 45 49 49 55 55 51 51 55 55 69 69 65 65 61
12. 61 65 65 69 69 95 95 91 91 95 95 89 89 85 85 81
13. 81 85 85 89 89 95 95 91 91 95 95 69 69 65 65 61
14. 61 65 65 69 69 55 55 51 51 55 55 49 49 45 45 41
15. 41 45 45 49 49 55 55 51 51 55 55 69 69 65 65 61
16. 61 65 65 69 69 15 15 11 11 15 15 09 09 05 05 01

На основе таблицы похоже распаковываются и расшифровываются некие данные(файлы и возможно MZ\PE), такого здорового алгоритма я не встречал (в аттаче, начинается с 0x0040183B), возможно быстрее действительно перебирать по CRC32, тогда желательно бы знать примерный вид серийников у этих инсталляторов, если кто встречал, иначе будет долго

_337455622__list.zip

 

Я ещё давно пытался найти или саму прогу для создания этих инсталяторов, или расшифровшик, но не то ни другое не нашел.

А передирать таблицу может реальней ???... в ней заметны какие-то закономерности. Если ничего не выдет, то помоги просто оптимизировать код.

 

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

_592267856__bruteforce_crc32.zip

 

Если кто-то для себя будет юзать, то учтите, перед сравнением с CRC должна быть команда not eax

Код (Text):

1.             xor     eax,dword[crc32_table+ecx*4]
2.             [b]not     eax[/b]
3. ;=====================================================================
4.             cmp     eax,0x9ae0daaf      ; (CRC32 of string '12345678')
5.             jz      @found
6. ;=====================================================================

Но в целях экономии времени лучше сделать эту операцию один раз на кулькуляторе

_162688859__8_crc32.asm

 

bogrus

Чего-то я не понял - ты никак полный перебор всех символов замутил ?



Известно же, что значение CRC32 определяется последними 4-мя байтами (см.например "CRC and how to Reverse it" by anarchriz). Поэтому перебирать последние 4 символа незачем. Нужно предварительно реверсировать заданное значение not(CRC) на 4 нулевых символа назад, затем перебираем первые символы и полученное not(CRC) ксорим с контрольным значением и получаем последние 4 символа. Остается только проверить их на принадлежность выбранному алфавиту (цифры, буквы и т.п.). Экономия - имхо гигантская Вот примерчик реверса для заданного CRC:

Код (Text):

1. crc32 E40BE346
2. not   [b]1B[/b]F41CB9      < ищем в таблице число [b]1B[/b]xxxxxx
3. -------v----------------
4. 55h   [b]1B[/b]01A57B      < нашли значение в таблице по индексу [b]55[/b]h          
5. xor     F5B9C2[b]55[/b]    < xor, shl 8, or index          
6. ---------v--------------
7. 57h     F50FC457            
8. xor       B60602[b]57[/b]          
9. -----------v------------
10. 3Fh       B6662D3D          
11. xor         602F6A[b]3F[/b]            
12. -------------v----------
13. 9Fh         60B08ED5            
14. xor           9FE4EA[b]9F[/b]   < реверс 1
15. ===============v========
16. 4Fh           9FBFE4A5
17. xor             5B0E3A[b]4F[/b] < реверс 2

Реверс 1 используется если CRC считается без учета замык.нуля, а 2 - с учетом.

Например, пароль из 5 символов: берем первый символ 31h = "1", not(CRC32) = 7C231048, для реверса 2 имеем последние символы = 7C231048 xor 5B0E3A4F = 272D2A07 - не пойдет, т.к. есть < 21h; берем 32h = "2" получаем аналогично BE247BBD = "Ѕ{$ѕ" и решаем брать или нет

 

leo Я это понял только вчера перед сном! В аське LAZAR сказал, что заключающий ноль (он считается в этой проге) можно не пересчитывать, т.к. все найденные пароли имеют одно и тоже CRC32, соотв. убрал из брута, и поставил сравнение с 0xf5b9c255, я было подумал оно сходится из-за нуля, но только потом допер сравнить црц у следующих паролей бум переделывать

 

2 bogrus



Ну, дядя, ты крут =))) такого прироста производительности я не ожидал, на моём компе перебирает 167000000 авриантов в сек, а сой перебирал 20000000 вариантов в сек... нужно как-то сделать чтоб небыло заточено под одну длину... тоесть чтоб начинало с 1-го символа, потом с 2-х... и т.д. Можна я думаю сделать сразу ну скажем на 20 символов, и чтоб после шифрования каждого проверяло не конец ли строки (0), и смотря где этот конец обнаружен прыгало на инкримент пароля в нужное место... Блин, вотэто я обьяснил =))) И ещё, к байтам регистров ЕАХ, ЕВХ... и т.д. можно обрашаться отдельно... так можно выделить 3 регистра на храние пароля... это будет 12 символов.. вобщем гду-то в этом направлении можна делать..

 

2 leo



Так ты посмотри, там же перебирается только изменившиеся символы... вроде оптимальней некуда (в плане чтоб не делать одно и тоже)....

 

И ещё идея - Неплохо былоб сделать чтоб набор символов для перебора мог быть произволный, а не диапазон из аски-таблици. Где-то я читал описание алгоритма, набор символов заносится в массив и позицией следующего элемента в массиве будет аски предыдущего. Это сэкономит время, и можно быдет постоить прерывный набор символов...

 

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



К примеру у нас CRC32 = 0xd7f3c592, сравнение было таким

Код (Text):

1. ;=====================================================================  
2.             cmp     eax,not 0xd7f3c592    ; (not(CRC32)'012345678912')
3.             jz      @found
4. ;=====================================================================

Теперь пойдет по такому пути

Код (Text):

1. ;=====================================================================
2.             xor     eax,0xE04EFC32*
3.             cmp     eax,'8912'
4.             jz      @found
5. ;=====================================================================
6. *                   280C3A6D  ; (not(CRC32)'012345678912')
7.             38h     2802B89E
8.                       0E82F338
9.             08h       0EDB8832
10.                         597B0A08
11.             7Ch         59B33D17
12.                           C8371F7C
13.             32h           C8D75180
14.                             E04EFC32
15. ;=====================================================================

Надо будет ещё реализовать сравнение \cmp eax,'8912'\, сделать массив для прерывного набора символов и подумать над переменной длиной

 

А так ведь можно высчитать не только последние 4 символа, а все? Т.е. автоматически с таблицы понасчитывать возможные значения для 4-х символьного пароля, 5-ти, 6-ти и т.д., а потом этот массив значений проверять на вхождение требуемых символов?