Xserg
24.01.2008, 21:40
Побрутив мд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:=$1032547 6;
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 почти не радует :(.
Подумалось, нельзя ли побыстрее? Оказалось можно.
Пример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:=$1032547 6;
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 почти не радует :(.