Необычный старый крякми (crackme)

Давно еще, со времен фидо, остался у меня один нерешенный крякми. Суть в том, что даже дан исходный код, необходимо соответственно узнать пароль. Используется crc32. Мне в голову, ничего кроме прямого брута не лезет. Да и брутом тоже не могу, долго перебирается. Может быть у кого-то какие-нибудь мысли есть?
Привожу оригинальный пост из фидо доисторических лет:

Код (Text):

1. const
2.   right_crc32:array [0..7] of longint = ($073EE641, $6E40EADF,
3.   $7A8EC36F, $92D0CF8E, $15FCE913, $16A8E48B, $1E01F3B0, $B1A61BFD);
4. var
5.   table: array [byte] of longint;
6.   i,n,l:longint;
7.   crc32:array [0..7] of longint;
8.   pwd:string;
9. begin
10.   write('enter your password: ');
11.   readln(pwd);
12.   for i:=0 to 255 do     {заполняем массив полиномов}
13.   begin
14.     l:=i;
15.     for n:=0 to 7 do
16.     begin
17.       if l and 1 = 1 then
18.         l:=(l shr 1) xor $EDB88320
19.       else
20.         l:=l shr 1;
21.     end;
22.     table[i]:=l;
23.   end;
24.   fillchar(crc32, sizeof(crc32), #$ff);  {считаем 8 CRC32 от пароля}
25.   for i:=0 to 7 do
26.   begin
27.     for n:=1 to length(pwd) do
28.     begin
29.       crc32[i]:=table[BYTE(crc32[i] xor longint(ord(pwd[n])))] xor (crc32[i]
30. shr 8);
31.       if ord(pwd[n]) and 1 = 0 then    {циклически сдвигаем вправо}
32.         pwd[n]:=chr(ord(pwd[n]) shr 1)
33.       else
34.         pwd[n]:=chr(ord(pwd[n]) shr 1 + $80);
35.     end;
36.     crc32[i]:=not crc32[i];
37.   end;
38.   for i:=0 to 7 do   {проверяем полученные CRC32 с правильными}
39.     if crc32[i]<>right_crc32[i] then
40.     begin
41.       writeln('invalid password');
42.       exit;
43.     end;
44.   writeln('valid password')
45. end.

Ну и соответственно мой брутфорс этого крякми. Писал в Virtual Pascal, может быть соберется и под Free Pascal. Основной цикл repeat until false практически весь на ассемблере, не смотрите на середину - это закаментированные строки паскалевские, просто чтобы понимать что происходит.... Мог конечно и ошибится при написании где-нибудь и уверен, что можно еще оптимизировать сильно, но моего скила хватило только на это:

Код (Text):

1. uses crt;
2. const
3.   right_crc32:array [0..7] of longint = ($073EE641, $6E40EADF,
4.   $7A8EC36F, $92D0CF8E, $15FCE913, $16A8E48B, $1E01F3B0, $B1A61BFD);
5.   Alphabet : String = 'abcdefghijklmnopqrstuvwxyz';
6. var
7.       szAlphabet : Array [0..255] of Char;
8.       szPassword : Array [0..255] of Char;      // текущий паpоль
9.       bAlphabet  : Array [0..255] of Char;      // таблица
10.       k : Byte;
11.   table: array [byte] of longint;
12.   i,n,l:longint;
13.   crc32:array [0..7] of longint;
14.   pwd : string;
15.   cnt : cardinal; //password length
16.  
17. begin
18.       For i := 1 to Length(Alphabet) do szAlphabet[i-1] := Alphabet[i];
19.       i := 0;
20.       k := 0;
21.       repeat
22.         bAlphabet[k] := szAlphabet[i];
23.         if szAlphabet[i] = chr(0) then
24.             break;
25.         k := Ord(szAlphabet[i]);
26.         Inc(i);
27.       until false;
28.  
29. {  write('enter your password: ');
30.   readln(pwd);}
31.   for i:=0 to 255 do     {заполняем массив полиномов}
32.   begin
33.     l:=i;
34.     for n:=0 to 7 do
35.     begin
36.       if l and 1 = 1 then
37.         l:=(l shr 1) xor $EDB88320
38.       else
39.         l:=l shr 1;
40.     end;
41.     table[i]:=l;
42.   end;
43.  
44.   cnt := 0;
45.   writeln('Bruteforce started. Press any key for info...');
46.  
47.       repeat
48.             asm
49.                   push eax
50.                   push ebx
51.                   push ecx
52.                   push edx
53.  
54.                   // generate next password
55.                   mov edi,offset szPassword
56.                   mov edx,edi
57.                   mov ebx,offset bAlphabet
58.             @L1:  movzx eax,byte ptr [edi]
59.                   xlat
60.                   cmp al,0
61.                   je @L3
62.                   mov [edi],al
63.                   jmp @L5
64.  
65.             @L3:  xlat
66.                   stosb
67.                   jmp @L1
68.             @L5:
69.                   // copy szPassword to pwd
70.                   //mov edi,edx //curent password
71.                   //mov ecx,255
72.                   //xor al,al
73.                   //repne scasb //find zero chr
74.                   //sub edi,edx
75.                   //mov ecx,edi
76.                   //dec ecx     //ecx - str length
77.  
78.                   //mov esi,edx
79.                   //mov edi,offset pwd
80.                   //mov byte ptr [edi],cl
81.                   //inc edi
82.                   //rep movsb
83.                   inc cnt // inc counter
84.  
85.                   // fill crc32 with $FF
86.                   mov edi, offset crc32
87.                   mov eax, $FFFFFFFF
88.                   mov ecx, 8
89.                   rep stosd
90.  
91. {            end;
92.       i := 0;
93.       pwd := '';
94.       repeat
95.             pwd := pwd + szPassword[i];
96.             inc(i);
97.       until Ord(szPassword[i]) = 0;
98.       writeln(pwd,len);
99.       readln;}
100.  
101. //  fillchar(crc32, sizeof(crc32), #$ff);  {считаем 8 CRC32 от пароля}
102. {  for i:=0 to 7 do
103.   begin
104.     for n:=1 to length(pwd) do
105.     begin
106.       crc32[i]:=table[BYTE(crc32[i] xor longint(ord(pwd[n])))] xor (crc32[i]
107. shr 8);
108.       if ord(pwd[n]) and 1 = 0 then
109.         pwd[n]:=chr(ord(pwd[n]) shr 1)
110.       else
111.         pwd[n]:=chr(ord(pwd[n]) shr 1 + $80);
112.     end;
113.     crc32[i]:=not crc32[i];
114.   end;
115.  
116.       asm
117.             pusha}
118.  
119.             mov esi,offset crc32
120.             mov ecx,8
121.             mov edi,offset szPassword
122.       @i_lup:
123.             push ecx
124.             push edi
125.  
126.       @n_lup:
127.             mov eax,[esi]
128.             mov ecx,eax  // save crc32[i]
129.             xor edx,edx
130.             mov dl,[edi]
131.             test dl,dl
132.             jz @done_p
133.             xor eax,edx //eax = crc32[i] xor pwd[n]
134.  
135.             mov ebx,offset table
136.             and eax, $000000FF //eax = al
137.             shl eax,2 // eax= eax*2
138.             mov eax,[ebx+eax] // eax= table[crc32[i] xor pwd[n]]
139.  
140.             shr ecx,8   //ecx = crc32[i] shr 8
141.             xor eax,ecx
142.             mov [esi],eax //crc32[i] = ...
143.  
144.             mov eax,edx
145.             shr eax,1
146.             and edx,1
147.             test edx,edx
148.             jz @if1
149.             add al,$80
150.       @if1:
151.             mov [edi],al
152.             mov i,eax
153.  
154.             inc edi
155.             jmp @n_lup
156.       @done_p:
157.             not dword ptr [esi]
158.  
159.             pop edi
160.             pop ecx
161.             add esi,4
162.             loop @i_lup
163.  
164.                   mov k,0 // check new CRC32
165.                   mov esi,offset crc32
166.                   mov edi,offset right_crc32
167.                   mov ecx,8
168.                   repe cmpsd
169.                   je @done
170.                   mov k,1
171.             @done:
172.                   pop edx
173.                   pop ecx
174.                   pop ebx
175.                   pop eax
176.  
177.       end;
178. //      k := 0;
179. //  for i:=0 to 7 do   {проверяем полученные CRC32 с правильными}
180. //    if crc32[i]<>right_crc32[i] then k := 1;
181.  
182.   If k = 0 then writeln('valid password ',pwd);
183.   If keypressed then
184.       begin
185.             write('cur pwd: ');
186.             for i := 1 to 255 do if szPassword[i] <> #0 then
187.             Write(szPassword[i]) else break;
188.             writeln('  cnt: ',cnt);
189.             readkey;
190.       end;
191.   until false;
192.   writeln('pwd: ', pwd);
193.   readln;
194. end.

 

а какие еще могут быть мысли? ищи уязвимости алгоритма црц32. Или делай перебор. Твой (да не важно чей) друг по сути спорил, что нельзя взломать црц32. Кроме перебора или коллизии вариантов не существует (если мне ни с кем не изменяет память)

 

xlat и stosb уже немодно, новые процессоры слишком долго вспоминают, как исполнять столь архаичные команды.

 

Для инкриментного перебора паролей я руководствовался статьей с этого сайта: http://www.wasm.ru/print.php?article=cycle_pwd

Плюс ко всему, я сомневаюсь, что генерация пароля занимает много времени по сравнению с расчетом новых crc. Вот они то и тормозят весь процесс. А генерация нового пароля - фи, ничто по сравнению с ...

 

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

 

Я тоже думал об этом, но загвозка в том, что там меняется ксорится crc текущая с каждым сиволом, потом еще крутятся сами символы. То-есть все взаимосвязано. Если бы оно просто считало crc32 от строки, то конечно, можно было бы создать таблицы.. А так, даже не знаю.
Наверное все-таки задача из разряда не решаемых за приемлемое время.

 

Внимательно не читал, но совсем не сложно обратить crc32, те по заданному CRC32_E найти такое x что CRC32(x)=CRC32_E всего за два цикла по 32 итерации ... ну или таблицу построить заранее.

 

напишите под CUDA )

 

PSR1257 Очень интересная мысль... А не поделитесь процедуркой? Или где почитать про обращение crc32?

spa Увы, не на чем выполнять (древняя ati x1650 pro), да и полный ноль в паралельном программинге.

 

Tronix
я выполню на своем gts 250

 

Криптостойкость crc32 равна 2^0, ничего перебирать не нужно тоесть. Это известно всем, так как алгос полностью обратим. Можно мгновенно пропатчить четыре байта длинного файла

и получить любой нужный crc без малейшего перебора.

 

persicum
Ну так покажите нам строку на крк32 0x073EE641 и вы взломаете крякми. Я не сомневаюсь что так можно, даже где-то читал про такую возможность, просто интересно посмотреть, да и про перебор, тоже интересно)

 

Здесь 8 параллельных CRC32 над битами строки в разном порядке (с циклическим сдвигом).

Следовательно, данный кракми представляет собой линейную систему с 64 неизвестными.
Если пароль автора 8 символов или меньше, он будет определен однозначно за миллисекунды.

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

Практического интереса задание не представляет.

 

Смотря какой алгоритм... Мой не дает. Дошел до 8 символов алфавита a-z, дальше сложно с моим процессором )

 

Tronix
перепишешь на си попробую у себя) ну можешь кинуть и скомпилированную версию

имхо лучше перебирай все байты. а потом можно хоть на глаз определить строка или нет. Прост со своими a-z не факт что ты себе и процу облекаешь задачу.

Можно подробней почему так? Просто заинтересовало почему-то)

ну это само собой.

 

Скомпилиная версия брута, алфавит 0-9. Там же и исходник.
ЗЫ: Только как всякий человек мог где-то ошибиться когда на асм переводил (( Но вроде все правильно должно быть...

 

Tronix
нафиг 0-9? я имел ввиду перебор ВСЕХ байт

 

Всех это совсем жесть... Вот алфавит "a-z"

 

Tronix
А если пароль AAff5533ff%%**? А вот если верить OLS то существует пароль который состоит из 8 байт, так что сделайте перебор по всем байтам и выводите в % готовность, я думаю это хоть и не быстро, но вполне можно дождаться

 

И еще надо бы распараллелить. Хотя бы сделайте все байты, и вывод в %-ах, завтра часа на 3-4 запустить могу)