Приветствую уважаемое собрание.

Пусть имеется следующий decrypt-алгоритм:

for(i=0; i < sizeof(code); i++)
  code[i] ^= getxor(&key1, &key2, &key3);

if(goodcrc == getcrc(code))
 // Ok
else
 // Fail

где key1, key2, key3 - некоторые константы (суть ключ), а getxor() - генератор предопределенной последовательности, зависящей от начальных key1, key2 и key3. Разумеется, это функция с side-effect'ом, т.е. значения ключей меняются после каждого вызова.

Собственно вопрос.
Возможно ли, зная алгоритмы getxor(), getcrc() и правильную crc определить правильные key1, key2 и key3?

Навеяло аттачем.

С уважением, Игорь.

_1991134399__hackme02.zip

Все зависит от того что за алгоритмы getxot и getcrc. Если они являются односторонними функциями, то определить значения ключей можно только полным перебором. Как я понял в твоем случае длина ключей 56 байт. Так что если в твоем алгоритме односторонние функции, то похоже определить значения ключей будет невозможно. Кстати, например CRC32 не является односторонней функцией и его можно обратить.

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

Обращение CRC практически ничего не даст, по нему код не востановить.
Сейчас смотрю чего можно сделать.

и вариант атаки №2.
Как формируеться ключ?
возможна атака на PRNG...

Длина ключа всего 6 байт, т.е. 3 WORD'а aka key1, key2, key3. Все остальное это криптованный ими код. Если интересно и не лень, гляньте в attach, он всего 628 байт.

Спасибо.

Первое, что следует попробовать - дифференциальный криптоанализ (поиск смещений в функциях).

„Первое, что следует попробовать - дифференциальный криптоанализ (поиск смещений в функциях).“

чтобы были ответы по теме, публикую код.

{
	ULONG t;

	t    = key1 * 171 + 11213;
	key1 = t % key2;
	t    = key0 * ((key1 * 65536 + t / key2) % key2);
	r    = t / key2 + (t % key2) & 1;

	return r;
}

Помоему реверснул правильно (не проверял на данных...)

А вот getcrc():
[code]
WORD getcrc() {
WORD ax = 0, dx = 0;

for(int i = 0; i < 0x32; i++) {
ax = (code[i] << 8) & 0xff00;
dx ^= ax;
for(int j = 0; j < 8; j++) {
if(dx & 0x8000)
dx = (dx << 1) ^ 0x1021;
}
}
return dx;
}
[\code]

Так, надеюсь, посимпатичнее будет

WORD getcrc() { 
  WORD ax = 0, dx = 0;

  for(int i = 0; i < 0x32; i++) { 
    ax = (code[i] << 8) & 0xff00; 
    dx ^= ax; 
    for(int j = 0; j < 8; j++) { 
      if(dx & 0x8000) 
        dx = (dx << 1) ^ 0x1021; 
    } 
  } 
  return dx; 
}

Все вроде посмотрел.
Без плаинт текста, тут тока полный перебор поможет.
Можно конечно предположить что первая команда после джампа будет mov dx, nnnn, или mov ah, 9
и попытаться построить вектора для востановления значений.

Я займусь этим тока завтра. Седня на работе меня нагрузили. Результаты сообщу как проверю.

Мне кажется, что полный перебор можно ограничить хотя бы key0 >= F2BEh.

Пусть код начинается с команд / в шифрованном виде:

mov dx,ofs ; BA ?? 01 / 3F 14 BF
mov ah,9 ; B4 09 / 46 35
int 21h ; CD 21 / C6 B1

Тогда, поскольку ксор идет словами и второе слово в коде будет B401h, шифротекст - 46BFh, то гамма равна: 46BFh xor B401h = F2BEh.

Теперь можно вспомнить, чему равно окончательное выражение для гаммы:

g = ((((K1*AB+2BCD)/K2) mod K2)*K0) / K2.

Определим, чему равна g max. Это можно определить так:
max (((K1*AB+2BCD)/K2) mod K2) = K2. Но тогда:

max g = K2*K0 / K2 >= любой гамме, в т.ч. F2BEh. Отсюда уже:

K0 >= F2BEh.

_Chingachguk_
вторым шагом будет добавление отсеивания для k2 относительно k0*(...), и почемуто у меня ощущения, что перебор сведеться очень близко к 32 битам (но это все предположения, из того что известены первые байты).
Если это не подтвердиться, то нужно идти в середину шифрованного текста, там почти наверняка текст. И используя частотный анализ сброшенного 7 бита и думать как это применить.

и почемуто у меня ощущения, что перебор сведеться очень близко к 32 битам

Да, у меня тоже так :)

Тут мне еще идейка в голову пришла - опять на max/min.

Запишем выражение для результата гаммы еще раз:

(K1*AB+2BCD) / K2 = AX:DX;
res_Gamma ~= (((DX*65536+AX) mod K2) * K0) / K2; // Еще есть +0/+1

Обозначим модуль (DX*65536+AX) mod K2 = M. M=func(K1,K2), причем из свойств конгруэнтного генератора следует, что K1<K2 - по крайней мере на любом шаге кроме 1-го (входное K1).

Так вот, я прогнал на нескольких K2 вычисления min M и max M, 0=<K1<K2:

K2 / Min M / Max M

1000h 2 ADh
2000h 1 ACh
3000h 2000h 20ABh
8000h 0 ABh
C000h 8000h 800ABh
...

Нетрудно заметить, что M всегда имеет значения в пределах от некоторого M min до M min + ABh. Видимо, это следует из свойств конгруэнтного генератора.

Что это дает ? Если верно мое предположение о начале кода, то второй гаммой будет F2BEh, а третьей - 0BC3h (команды mov ah,9, int 21h). Т.е. мы имеем два ограничителя - сверху и снизу:

gamma ~= M*K0 / K2;

(M min *K0)/K2 <= 0BC3h
(M min + ABh)/K2 >= F2BEh

К тому же имеем, что K0 >= F2BEh. Решаем эту систему уравнений (M==Mmin):

K0 >= F2BEh*K2 / (M+AB);
-K0 >= -K2*0B3Ch / M;

Откуда получаем:

K2 * (0B3Ch/M - F2BEh/(M+AB)) >= 0;

Или:

M <= (0B3C * ABh) / (F2BE-B3C) = 8 !!!

Мне кажется, это определенно что-то означает. Счас еще подумаю....

Не, последняя мысль была полностью отстойной. Для хорошего выбора коэффициентов конгруэнтного генератора такого эффекта не будет. Насчет первого ограничения вроде верно.

Если это "настоящий" генератор вида (Ax+B) mod M, то для него должно быть: M > A, M > B, тогда отсюда вроде следует, что K2 > 2BCDh.

Вроде как придумал кое-что получше. Если перебирать ключи в таком порядке: K2 - K1 - K0, причем K0 даже не перебирать, а получать приближение, то можно получить вычислительную сложность порядка E000^2/2 * 10 или около того в следующем алгоритме:

var
  M,IM,K0,K0max,K2,K2min,K2max,tmp,stopK2,K1,K1test,K0est,K0test: word;

function get_gamma:word;
  begin
    asm
    mov  bx,K0                  { Key0 }
    mov  ax,0ABh
    mul  word ptr K1            { Key1 * 0ABh }
    add  ax,2BCDh               { Key1 * 0ABh + 2BCDh }
    adc  dx,0h
    div  word ptr K2            { (Key1 * 0ABh + 2BCDh) / Key2 }
    mov  K1,dx                  { Key1 }
    div  word ptr K2            { mod Key2 }
    mov  ax,dx
    mov  word ptr M,ax
    mul  bx
    div  word ptr K2
    and  dx,1h
    add  ax,dx
    mov  @Result,ax
    end;
  end;
begin
  K2min:=$FFFF;
  K2max:=0;
  K0max:=0;

  K0:=$0202;
  K1:=$0202;
  K2:=$0202;
  writeln('get_gamma=',get_gamma);
  for K2:=$AD{2BCD} to $FFFF do
    begin
      writeln('K2=',K2);
      for K1test:=1 to K2-1 do
        begin
          { Get K0 estimate }
          K1:=K1test;
          get_gamma;
          asm
          mov  K0est,0
          mov  ax,1D8Bh{0F2BDh}
          mul  word ptr K2
          { Overflow ? }
          cmp  dx,word ptr M
          ja   @@OverFlow
          jb   @@NoOver
          test ax,ax
          jnz  @@OverFlow
@@NoOver:
          div  word ptr M
          mov  K0est,ax
@@OverFlow:
          end;
          if K0est = 0 then continue;
          for K0test:=K0est-2 to K0est+2 do
            begin
              K0:=K0test;
              K1:=K1test;
              if get_gamma=$1D8B{F2BD} then
                begin
                  if (get_gamma and $FF)=$05 then
                    begin
                      if get_gamma = $0B37 then
                        begin
                          writeln('Found: K2=',K2,' K0=',K0test,' K1=',K1test);
                          readln;
                        end;
                    end;
                end;
            end;
        end;
    end;

Здесь K0 вычисляется по следующей оценке: мы знаем K2, K1 - следовательно, знаем результат t = key0 * ((key1 * 65536 + t / key2) % key2), а окончательный результат для гаммы равен r ~= t*K0/K2 - отсюда оценка для K0 по известной r (скажем, из r=F2BDh на втором шаге).

По крайней мере, таким образом я верно расшифровываю второе и третье слово шифротекста.

Не, не прокатило ;(

Вчера попробовал вышеописанным алгоритмом (в аттаче) проверить то, что код начинается либо с

mov dx,offset xxx BA XX 02
mov ah,09h        B4 09
int 21h           CD 21
int 20h           CD 20

Либо с

mov ah,09h        B4 09
mov dx,offset xxx BA XX 02
int 21h           CD 21
int 20h           CD 20

И ничего не нашел (те набора {K0,K1,K2}).

Пробовал вот еще какую идею: как-то на форуме bugtraq.ru я спрашивал у Relf'а про свойства конгруэнтного генератора:

> Вопрос такой: есть ли какие - то предпочтения в выборе a и
> b ? 

Вот теорема из "Искусства программирования" Кнута: 
Длина периода линейной конгруэнтной последовательности (т.е. последовательности, вида X = (a*X+c) % m) равна m тогда и только тогда, когда: 
1. HОД(c,m) = 1 (т.е. c и m взаимно просты) 
2. b=a-1 кратно p для всех простых p - делителей m 
3. b кратно 4, если m кратно 4 

В алгоритме шифрования в данном случае есть такой генератор:

key1= (key1 * 171 + 11213) % key2;

Если предположить, что выбор key2 сделан в соответствии с вышеприведенными свойствами, то:

1-е свойство особо ничего не дает, поскольку c=11213 простое число.

3-е свойство дает b=171-1=170 делиться на 4, если key2 кратно 4 => key2 не делиться на 4.

2-е свойство: b=171-1=170=2*5*17 должно быть кратно всем простым делителям key2. Это может означать две ситуации: key2 - простое или key2 имеет при разложении на множители только числа 2,5 и 17. Вот все такие числа в интервале {~ADh,FFFFh}: 850,2890,4250,14450,21250,49130.

Последнее число 49130=BFEAh я проверил несколькими вариантами, но тоже глухо.



_1995069031__Get_m4.pas