Форум АНТИЧАТ - Брут Md5 быстрее на 25%

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)

- С/С++, C#, Delphi, .NET, Asm (https://forum.antichat.xyz/forumdisplay.php?f=24)

- - Брут Md5 быстрее на 25% (https://forum.antichat.xyz/showthread.php?t=59821)

Брут Md5 быстрее на 25%

Побрутив мд5 хеш на своем компьютере (AMD65 3500+), программой PasswordsPro (5.5млн п/с) ), увидел цифру 10лет.
Подумалось, нельзя ли побыстрее? Оказалось можно.

Пример1 кода мд5 на делфи.

Код:

// function lrot32(a, b: dword): dword; register;

// begin result:= (a shl b) or (a shr (32-b));end;

a:=$67452301;b:=$efcdab89;c:=$98badcfe;d:=$10325476;

a:= b + lrot32(a + (d xor (b and (c xor d))) + data[ 0] + $d76aa478,7);

d:= a + lrot32(d + (c xor (a and (b xor c))) + data[ 1] + $e8c7b756,12);

и т.д

….

….

….

d:= a + lrot32(d + (a xor b xor c) + data[12] + $e6db99e5,11);

// здесь уже можно проводить проверу d.

// если не ровно код ниже (25%) выполнять не обязательно

c:= d + lrot32(c + (d xor a xor b) + data[15] + $1fa27cf8,16);

// здесь уже можно проводить проверу c.

b:= c + lrot32(b + (c xor d xor a) + data[ 2] + $c4ac5665,23);

// здесь уже можно проводить проверу b.

a:= b + lrot32(a + (c xor (b or (not d))) + data[ 0] + $f4292244,6);

// здесь уже можно проводить проверу a.

// до этого места md5 (снизу вверх) можно выполнить в обратом порядке

d:= a + lrot32(d + (b xor (a or (not c))) + data[ 7] + $432aff97,10);

c:= d + lrot32(c + (a xor (d or (not b))) + data[14] + $ab9423a7,15);

b:= c + lrot32(b + (d xor (c or (not a))) + data[ 5] + $fc93a039,21);

a:= b + lrot32(a + (c xor (b or (not d))) + data[12] + $655b59c3,6);

d:= a + lrot32(d + (b xor (a or (not c))) + data[ 3] + $8f0ccc92,10);

c:= d + lrot32(c + (a xor (d or (not b))) + data[10] + $ffeff47d,15);

b:= c + lrot32(b + (d xor (c or (not a))) + data[ 1] + $85845dd1,21);

a:= b + lrot32(a + (c xor (b or (not d))) + data[ 8] + $6fa87e4f,6);

d:= a + lrot32(d + (b xor (a or (not c))) + data[15] + $fe2ce6e0,10);

c:= d + lrot32(c + (a xor (d or (not b))) + data[ 6] + $a3014314,15);

b:= c + lrot32(b + (d xor (c or (not a))) + data[13] + $4e0811a1,21);

a:= b + lrot32(a + (c xor (b or (not d))) + data[ 4] + $f7537e82,6);

d:= a + lrot32(d + (b xor (a or (not c))) + data[11] + $bd3af235,10);

c:= d + lrot32(c + (a xor (d or (not b))) + data[ 2] + $2ad7d2bb,15);

b:= c + lrot32(b + (d xor (c or (not a))) + data[ 9] + $eb86d391,21);



currenthash[0]:= $67452301+a;

currenthash[1]:= $efcdab89+b;

currenthash[2]:= $98badcfe+c;

currenthash[3]:= $10325476]+d;

end;

Еще один пример2 как md5 выполняется в обратном порядке:

Код:

procedure rev_md5;

var a,b,c,d,e:dword;

begin

// в currenthash наш xеш, пароль от которого нужно найти

a:=currenthash[0]-$67452301;

b:=currenthash[1]-$efcdab89;

c:=currenthash[2]-$98badcfe;

d:=currenthash[3]-$10325476;

b:=b-c;

b:= ((b shr 21) or (b shl (32-21)));

b:= b - ((d xor (c or (not a))) + $eb86d391);

c:=c-d;

c:= ((c shr 15) or (c shl (32-15)));

c:= c - ((a xor (d or (not b))) + data[ 2] + $2ad7d2bb);

d:=d-a;

d:= ((d shr 10) or (d shl (32-10)));

d:= d - ((b xor (a or (not c))) + $bd3af235);

a:=a-b;

a:= ((a shr 6) or (a shl (32-6)));

a:= a - ((c xor (b or (not d))) + data[ 4] + $f7537e82);



b:=b-c;

b:= ((b shr 21) or (b shl (32-21)));

b:= b - ((d xor (c or (not a))) + $4e0811a1);

c:=c-d;

c:= ((c shr 15) or (c shl (32-15)));

c:= c - ((a xor (d or (not b))) + $a3014314);

d:=d-a;

d:= ((d shr 10) or (d shl (32-10)));

d:= d - ((b xor (a or (not c))) + $fe2ce6e0);

a:=a-b;

a:= ((a shr 6) or (a shl (32-6)));

a:= a - ((c xor (b or (not d))) + $6fa87e4f);



b:=b-c;

b:= ((b shr 21) or (b shl (32-21)));

b:= b - ((d xor (c or (not a))) + data[ 1] + $85845dd1);

c:=c-d;

c:= ((c shr 15) or (c shl (32-15)));

c:= c - ((a xor (d or (not b))) + $ffeff47d);

d:=d-a;

d:= ((d shr 10) or (d shl (32-10)));

d:= d - ((b xor (a or (not c))) + data[ 3] + $8f0ccc92);

a:=a-b;

a:= ((a shr 6) or (a shl (32-6)));

a:= a - ((c xor (b or (not d))) + $655b59c3);

b:=b-c;

b:= ((b shr 21) or (b shl (32-21)));

b:= b - ((d xor (c or (not a))) + $fc93a039);

c:=c-d;

c:= ((c shr 15) or (c shl (32-15)));

c:= c - ((a xor (d or (not b))) + data[$e] + $ab9423a7);

d:=d-a;

d:= ((d shr 10) or (d shl (32-10)));

d:= d - ((b xor (a or (not c))) + $432aff97);

// a,b,c,d для ускоренной проверки

srhash0:=a; 

srhash1:=b;

srhash2:=c;

srhash3:=d;

end;

Вообще то, если известен пароль (который содержится в data[] ) , мд5 можно выполнить полностью в обратном порядке и получить исходные константы в a,b,c,d

Но пароль не известен, поэтому остановимся на первом data[ 0], это первые 4 символа пароля.

Алгоритм перебора получается такой:
Заполняем data[1]..data[x] данными.
выполняем procedure rev_md5
и теперь заполняя data[0] (это четыре байта), перебираем и сравниваем сокращенным md5;
Если совпали srhash0==a;srhash1==b;srhash2:==c;srhash3==d; пароль у нас на экране.

Как можно еще, заметить отсутствуют data[ 4], data[ 5]…
Просто найти пароль длинной более 23 символов, нереально, так и незачем нагружать процессор заставляя его прибавлять нули.

Исходники и программу выкладывать не буду, тк
Допустил ошибку , выбрав в данном случае Delphi (умучился алгоритм оптимизировать), нужно сразу было на Си.
Но все равно 7.1 млн п/c вместо 5.5млн получилось.

Зы но 9 лет вместо 10 почти не радует :(.

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

Цитата:

Сообщение от AFoST

охринительный брутфорсер на АСМЕ

Без языка высокого уровня оптимизировать:

Код:

 a:=$67452301;b:=$efcdab89;c:=$98badcfe;d:=$10325476;

a:= b + lrot32(a + (d xor (b and (c xor d))) + data[ 0] + $d76aa478,7);

d:= a + lrot32(d + (c xor (a and (b xor c))) + data[ 1] + $e8c7b756,12);

В - (те же три строчки на asm)

Код:

// a-eax,b-ebx,c-ecx,d-edx

MOV EDX,$EFCDAB89

MOV ECX,$98BADCFE



MOV EAX,DWORD PTR DS:[ESI]

DEC EAX

ADD EAX,$D76AA478

ROL EAX,$7

ADD EAX,EDX



MOV EBX,EAX

AND EBX,$77777777

XOR EBX,ECX

ADD EBX,DWORD PTR DS:[ESI+$4]

ADD EBX,$f8fa0bcc

ROL EBX,$0C

ADD EBX,EAX

Времени 19 лет уйдет.

Поделить код на несколько частей и каждую часть отдать отдельному программеру. Стоящие вещи пишутся не в один день...

http://www.rewolf.cjb.net/
http://cracklab.ru/f/index.php?action=vthread&topic=5787&forum=6&page=-1

Код:

MOV EDX,$EFCDAB89

MOV ECX,$98BADCFE



MOV EAX,DWORD PTR DS:[ESI]

DEC EAX

ADD EAX,$D76AA478

ROL EAX,$7

ADD EAX,EDX



MOV EBX,EAX

AND EBX,$77777777

XOR EBX,ECX

ADD EBX,DWORD PTR DS:[ESI+$4]

ADD EBX,$f8fa0bcc

ROL EBX,$0C

ADD EBX,EAX

оптимизация? рассмешил ...
особенно
DEC EAX\ADD EAX,$D76AA478 подряд...

Цитата:

Сообщение от kez

оптимизация? рассмешил ...
особенно
Dec Eax\add Eax,$d76aa478 подряд...

Это компилятор Си смешной.

Откомпилил в си вставил в Delphi:
Предварительный рабочий вариант:
http://filesurf.ru/25687/keygenme.rar.html
10 хешей перебирает быстрее, чем PasswordsPro один.
Ответ создателя PasswordsPro о возможности добавить агоритм:

Цитата:

Интересная мысль, но думаю, что пока вряд ли она будет реализована в PPro, т.к. ваш алгоритм хорош для брутфорсера, заточенного "чисто" под MD5. Я же пока стремлюсь сделать ядро PPro универсальным - чтобы оно одними и теми же функциями работало с любым алгоритмом. И в очередной версии программы все алгоритмы будут вынесены в отдельные DLL-модули, что также будет очередным шагом на пути поддержки многопоточности. А затем уже можно будет приступать к точечной оптимизации каждого алгоритма внутри DLL-модуля. Но ваше предложение я учту, т.к. идея этого алгоритма теоретически может быть использована не только в MD5.

Цитата:

Сообщение от Xserg

Зы но 9 лет вместо 10 почти не радует :(.

Подумалось, нельзя ли еще побыстрее? Оказалось можно.

Необходимые компоненты:

[+] Microsoft Visual Studio 2005 или старше (в смысле поновее)
[+] CUDA for Windows Тут
[-] Видеокарта Nvidia GeForce8800 Ultra … [+]GeForce8500GT (1.8т.руб) в десять раз медленнее
[+] немного мозгов , для написания программы

Вот так не сложно запускается 128 потоков одновременно

Код:

 unsigned int * data;

  cudaMalloc((void**)&data, sizeof(hdata));

  cudaMemcpy(data, hdata, sizeof(hdata), cudaMemcpyHostToDevice);

  md5<<<16,8>>>(data);//16-мультипроцуссоров * 8 шейдеров =128 threads

  cudaMemcpy(hdata, data, sizeof(hdata), cudaMemcpyDeviceToHost);

Так пишется программа для синхронного выполнения 128 шейдерными процессорами.

Код:

__global__ void md5(unsigned int * data)

{

unsigned int Pdata[16];

for (int i=0;i<16;i++) Pdata[i]=data[(blockIdx.x*16 + threadIdx.x*8) +i];

__syncthreads();

unsigned int a=0x67452301;

unsigned int b=0xefcdab89;

unsigned int c=0x98badcfe;

unsigned int d=0x10325476;

a= a + (d ^ (b & (c ^ d))) + Pdata[ 0] + 0xd76aa478; a=(a<< 7)|(a>>(32- 7)); a= b + a;

d= d + (c ^ (a & (b ^ c))) + Pdata[ 1] + 0xe8c7b756; d=(d<<12)|(d>>(32-12)); d= a + d;

c= c + (b ^ (d & (a ^ b))) + Pdata[ 2] + 0x242070db; c=(c<<17)|(c>>(32-17)); c= d + c;

b= b + (a ^ (c & (d ^ a))) + Pdata[ 3] + 0xc1bdceee; b=(b<<22)|(b>>(32-22)); b= c + b;

// и т.д.

Совсем не сложно ;) .

Получаем перебор 320 000 000 паролей в секунду.

Зы 2 месяца вместо 9 лет уже радует. :)

Цитата:

Сообщение от Xserg

Получаем перебор 320 000 000 паролей в секунду.

ММм а можно поинтересоваться это на каком железе ?
и с какими вениками ?

Цитата:

Сообщение от Nova

на каком железе ?

http://www.nvidia.com/page/geforce8.html
GeForce 8800 Ultra - 320 млн.пас/cek (10т.руб накапливаю)
GeForce 8800 GTX - 288 млн.пас/cek
GeForce 8800 GTS(1) - 192 млн.пас/cek, SLI(2) - 384 млн.пас/cek

У меня в наличии:
GeForce 8500 GT - 27 млн.пас/cek , но это не предел оптимизирую до 32. тогда данные выше станут реальными, а не предполагаемыми.
+ вся оптимизация затачивается на нахождение одного пароля.
Универсальная программа будет поскромнее. :)

молодец, конечно, что подкинул такую идею..
жаль, что у меня на ноуте стоит какая-то непохек-видюха и неначем поэксперементировать.. +)

Кто нибудь протестил? Реально такая скорость?
У меня видюха 8800gtx, но не смог откомпилировать, видно что то не так делаю.

Народ кому нетрудно, залейте куданебуть собранный исходник, а то что-то неполучается самому собрать

Небольшое FAQ по программированию на CUDA

1. что нужно чтобы начать ?
Microsoft Visual Studio
CUDA Toolkit version 1.1 CUDA SDK version 1.1

2. можно ли программировать на Delphi ?
Можно, но игра не стоит свеч от геморроя, который вы получите.

3. у меня нет Nvidia GF8x00, а попробовать хочется
Можно и без видеокарты. Есть эмулятор видеокарты.

4. у меня есть Nvidia GF8x00, но нечего не работает
Установите драйвера для видеокарты с поддержкой CUDA.

5. можно ли задать вопрос посложнее ?
Нет нельзя. Я сам эту тему изучаю всего неделю. И многие вещи пока просто не понимаю.

6. Какая реальная скорость ?
Есть платная программа распределенного перебора.
NTLM перебирает со скоростью 350 млн.п/c , MD5 приблизительно в два раза длиннее.

7. У меня не компилятся исходники
Для начала нужно выполнить первый пункт этого FAQ.
Затем найти исходники. (то что выложено – это ~1%).

Этож боян уже?:)
http://www.passwords.ru/edpr.html - все уже давно реализовано и работает- не надо изобретать велосипед. да и в приватных кругах уже проходили исходники..

Цитата:

Сообщение от grinay

MD5 с аппаратным ускорением не реализовано.

А также я знаю приватный круг , где нужный мне пароль знают, а хрен ли толку.

Тема в одностороннем прядке закрыта.