Date: Sun, 26 Feb 2006 23:01:33 +0500
From: gazlan <gazlan@yandex.ru>
To: solme <solme@yahoogroups.com>
Subject: A known plain text attack on the juicy_emad's Junk Stream Cipher


Предистория:
------------

На форуме www.cracklab.ru неким juicy_emad было предложено
вознаграждение за дешифровку файла:

> juicy_emad
> Ранг: 2 (гость)
> Статус: Участник
> Дата: Фев 11, 2006 04:07:05
>
> Нужно расдекодировать файло. $
>
> Код писал не я, но я могу обьяснить смысл (примерно это работает так):
> Последовательно берётся каждый байт(символ) кодируемого файла, и изменяется
> в зависимости от:
>
> 1) Кода символа последовательно взятого символа из строки с паролем.
> 2) Длины строки с паролем.
> 3) Суммы кодов символов всего пароля.
> 4) Кода символа пред. символа(байта) кодируемого файла.
>
> Судя по пункту 4 можно сказать, что раскодирование должно происходить
> с конца закодированного файла. И если мы не знаем пароль, то мы
> закодированный файл ВООБЩЕ никак не раскодируем (2 критерия зависят от
> знания ВСЕГО и 1 от знания некоторого символа).
>
> Есть очень нужный мне *.doc файл, который зашифрован с помощью этого
> кода (экзаменационные ответы).
>
> У меня есть эта прога (ну или эта функция). В ней собственно самая суть.
> Этот важный *.doc файл (2003 офис.). Знание того, что пароль 8-ми
> символьный. Несколько недель...
>
> Идей у меня просто нету. Даже не знаю как подступиться. Очевидно нужно
> посмотреть, на то, какие заголовки и какие одинаковые во всех документах
> блоки ставит 2003 ворд... и от этого плясать...
>
> *Так что в архиве с этим сообщением лежит проект проги с рилизом (С++;
> VC6 SP5). Этот важный файл. (Там есть пример f.txt и f_code.txt - это то,
> что получилось, в результате кодирования)
>
> (*Файл закодирован без архивации дополнительной и без прочей байды,
> которая есть в программе, так как она просто не работает. 8-)
>
> *Скиньте на моё мыло ответы скажем на первый билет. Тогда я буду уверен,
> что вы действительно это сделали. juicy_emad@mail.ru . А о 'бумажках'
> договоримся...


> bkslash
> Ранг: 47.4 (посетитель)
> Статус: Участник
> Дата: Фев 11, 2006 13:09:49 New!
>
> хахаха... фиговая стойкость ;D вот что там внутри:


> BlindChaos
> Ранг: 7 (гость)
> Статус: Участник
> Дата: Фев 11, 2006 14:49:26 New!
>
> делать нечего автору этого творения, только зря время потратил.
> qaz50134


> juicy_emad
> Ранг: 2 (гость)
> Статус: Участник
> Дата: Фев 11, 2006 15:44:02 New!
>
> Ну вы просто боги криптования!
> Я в это не верю!
>
> Наверняка вы вычислили меня по IP, обошёли файрволл и нашёли нужный файл...
> хотя я юзаю мегафон, и IP там один на неск. человек... Итак, неважно.
>
> Вобщем извиняюсь перед всеми людьми, которые потратили время на этот
> кусок. 8-) Ибо я на 99 процентов был уверен в том, что у вас ничего не
> получится. 8-)))
>
> Я только понять не могу... КАК???! Я думал об этом... но я так запарился,
> что решил, что это невозможно.
>
> Намекните хотябы! Что вам помогло? Длина пароля? Знание того, что этот
> файл, является файлом ворда? Вы написали брутфорсер что-ли? Подскажите!!!
> Дайте намёк! 8-))) Дайте линков на литературу, которую читали вы...
>
> Я просто в шоке... невероятно... РЕСПЕКТ вам! Больше ничего не могу
> сказать...
>
>
> (*Когда я печатал что я дам денег, которых у меня в данный момент нет 8-)),
> то мне было стыдно просто... но я успакаивал себя на мысле, что у вас
> ничего не получится, и в ваших постах я увижу, что на разгадку подобного
> файла нужно несколько миллионов лет. 8-))) Так что мир всем. Я ничего
> такого не хотел. 8-))))


> Нужно расдекодировать файло. $ Part 2
>
> juicy_emad
> Ранг: 4 (гость)
> Статус: Участник
> Дата: Фев 20, 2006 02:11:22
>
> Итак, хочу задать некоторый вопрос. Всё это время я думал, и пытался
> взломать собственнонаписанный (а также его писал ХЕЁС) шифратор
> файлов EHCodeFile. Никто мне так и не сказал как именно это делать.
> И у меня появилась следующая идея:
> Написать проект EHCodeFileCracker, который работает примерно так:
> Введим некоторые символы, которые будут использоваться для подбора
> пароля, и начинаем брутфорсный подбор, при каждой генерации мы
> передаём в функцию декодирования файла собственно данный Кодированный
> файл, сгенерированный пароль. На каждом этапе получения след. символа
> в функции декодера сравниваем этот символ с символом файла, часть
> которого предположительно похожа (идентична) той, над которой мы про-
> водим процесс декодинга. Дело в том, что у файлов WORD'а очень много
> повторяющихся блоков, возмём начальный, и увидим, что практически
> 10 килобай совпадают у разных файлов.
> Это основной подход. Но дело в том, что программа даёт что-то около
> 2-х миллионов парлей в сек. на 1 466 MHZ (1700+ ATHLON). Такой подбор
> малоэффективен при пароле больше 6-ти символов. У меня процесс подбора
> пароля (qaz50134) к тому же файлу занял у меня где-то часов 30. Так
> что я не представляю как вы это сделали менее чем за 12 часов.
> Расскажете может.


> Mario555
> Ранг: 245.2 (наставник)
> Статус: Модератор
> •Pr0tEcToRs KiLLeR•
> Дата: Фев 20, 2006 10:05:14
>
> Что-то много стало кодеров которые пытаются нахаляву тестить тут свои
> "неломаемые" защиты, надоели... а этот, как я понял, вообще на***л людей
> на деньги. Так что топик закрыт.


Intro:
------

Люди сведущие знают, что криптография - дело тонкое, а конструирование
хорошего криптоалгоритма даже не столько наука, сколько искусство. Невежды,
однако, бесстрашно заявляют об изобретении все новых и новых "непобедимых"
алгоритмов. И вот очередная "сладкая парочка": 'emadt-heios' громко объявляет
на CrackLab об очередном "шедевре":

> Программа предназначенная для того чтобы кодить файлики с паролем, и в
> итоге чего получались файлы которые можно раскодировать этой же прогой, но
> без знания полного пароля разкодить эти файлы ПРОСТО НЕРЕАЛЬНО!!!
>
> Это мы вам как криптографы говорим!
>
> ПРОСТО НЕРЕАЛЬНО, ЗНАЛИ БЫ ВЫ ХОТЬ КУСОК ЭТОГО КОДА, вы были бы в этом
> уверены не меньше нашего!
>
> ЭТО МЫ ВАМ КАК ПРОГРАМЕРЫ ГОВОРИМ!
>
> Написали же, это чудо-юдо emadt и heios, обезапасить инфу очень легко!
>
> (поправка, разкодить то конечно можно но на это уйдёт три человека,
> которые умеют взламывать программы находить их исходники, капаться в пяти
> килобайтовом ассемблерском скрипте, которые в итоге выведут алгоритм
> проги, да ещё и будут знать весь пароль кроме нескольких символов (3~4),
> или будут иметь на руках исходный файл, то им потребуется примерно: 5К
> литров пива чтобы узнать пароль из: исходника программы + исходного файла.
> 11К литров пива чтобы узнать пароль имея: кусок пароля + исходник проги и
> НЕ имея Исходный файл. поделите пивной эквивалент на количество пива
> которое смогут выпить профессионалы такого уровня при геморойнейшем
> анализе всей этой лабуды, и умножте на (рамер закодированного файла /
> (3,1415926535897932384626433832795 мегабайта <- в случае без
> архивирования) или ( (П/e) ~ 1,157 мегабайта если с архивированием) ), и
> получите количество дней которое потребуется для дешифрации информации.
> Понять-то насколько это сложно, и то сложно, чего уж там говорить о
> сложности переложенной разложенности анализа! Но если вы всё же решились:
> УДАЧИ!!! 8-))) )

За дешифровку тестового файла были обещаны $$$, но как водится, выполнять свои
обещания они и не собирались - и денег-то у них нет и взлом казался им
невыполнимым, так что "за базар не отвечаем".

Поскольку программа написана таки на C (портить глаза дельфийскими исходниками
мне неинтересно), а обиженные неуплатой долга крэкеры процедуру взлома не
раскрыли, то, когда выдался свободный вечер, мне показалось забавным сделать
"разбор полетов" для [solme] - показать возможный подход и пошаговую
реализацию.


Анализ:
-------

Орфография ... кажется, мальчики никогда не учились в школе ... Язык C им
знаком примерно на том же уровне, что и русский ... Избыточные и/или нелепые
конструкции ... Код просто ужасен: форматирование (точнее его отсутствие), нет
проверок на валидность указателей и хэндлов, нет проверок на успешность
выделения динамической памяти (!), затирание "чужой памяти" и тотальная ее
утечка - НИ ОДИН выделенный блок памяти НИКОГДА НЕ ВОЗВРАЩАЕТСЯ системе !

Сама затея с чтение всего файла в динамически выделяемую память - шедевр
абсурда. Как насчет шифрования ISO-образа DVD размером в 4+ Gb ?

Дешифрование ... сделано через известное место - файл дешифруется С КОНЦА -
LOL !!

Понятно, что разработанный двумя умниками (всюду пишущими слово "длина" через
два "н") алгоритм _обязан_ быть плохим и нестойким.


Реализация:
-----------

Что алгоритм "полное фуфло" было понятно еще из описания, поэтому меня очень
удивило, что потребовалось 30+ часов на подбор 8-символьного пароля. Хороший
крэкер, по известному plain text'у при такой длине пароля дешифрует файл
вручную, используя один только встроенный в Windoooz калькулятор за гораздо
меньшее время.

Это побудило меня написать простенький брутфорсер на M$VC (без даже попытки
какой-либо оптимизации). Для указанного файла пароль 'qaz50134' был найден
менее чем за 1 миллисекунду.

Также, менее 1 миллисекунды потребовалось и для подбора 16-символьного пароля
(AbRaCaDaBrA12345) для наугад взятого и зашифрованного этим паролем текстового
файла.

Вообще говоря, все испробованные файлы с ярко выраженной дисперсией
частотностей (TXT,DOC,XLS,HTML) даже при 16-символьном пароле дешифровывались
мгновенно. Для расшифровки псевдослучайных файлов потребуется улучшить
использованный в брутфорсере анализатор коллизий :-)


Code:
-----

Читать оригинальный код попросту невозможно. Я выдрал из него
существенную часть и написал свой Testpad.

Везде дальше я ссылаюсь на этот модифицированный код.


Шифрование:
-----------

Ничего особенного - потоковый шифратор в режиме CBC. Сделан через одно
место...


   // Инициализируем вектор
   _SS = JUNK_BOY_AGE;

   // Update 1
   // K[i] - Очередной символ ключа
   // G[i] - Гамма, используемая при шифровании
   // Для собственного удобства я разделил 1-ую и 2-ую фазы создания
   // гаммы
   for (ii = 0; _pK[ii]; ++ii)
   {
      _SS += _pK[ii];

      _pG1[jj] = (char)(_pK[ii] + _SS + jj++);
      _pG1[jj] = (char)(_pK[ii]       + jj++);
   }

   // Update 2
   // Полученная на первом этапе гамма модифицируется
   // Сейчас, _SS - сумма всех символов пароля
   for (ii = 0; ii < iPswSize2; ++ii)
   {
      _pG2[ii] = (char)(_pG1[ii] + _SS);
   }

   // Самый первый символ файла (де)шифруется не так, как все остальные
   _pBuf[0] = (char)(_pBuf[0] + _pK[0] + _SS);

   // Итерация по остатку файла
   // Опять же, для собственного удобства, я вынес часть кода
   // в отдельные функции F1..F11
   // NEXT и PREV - два последовательных символа потока
   // SUM и DIF - их сумма или разность

   // Какая именно из функций используется для (де)шифрования,
   // определяется некоторыми условиями и зависит от текущей гаммы
   // и/или текущего символа потока

   // CBC Stream Cipher
   for (ii = 1,jj = 1; ii < (int)_dwSize; ii++,jj++)
   {
      jj %= iPswSize2;

      // Switch emulation
      char     _F1  = (char)F1 (ii,jj,_pG2[jj]);
      char     _F2  = (char)F2 (ii,jj,_pG2[jj]);
      char     _F3  = (char)F3 (ii,jj,_pG2[jj]);
      char     _F4  = (char)F4 (ii,jj,_pG2[jj]);
      char     _F5  = (char)F5 (ii,jj,_pG2[jj]);
      char     _F6  = (char)F6 (ii,jj,_pG2[jj]);
      char     _F7  = (char)F7 (ii,jj,_pG2[jj]);
      char     _F8  = (char)F8 (ii,jj,_pG2[jj]);
      char     _F9  = (char)F9 (ii,jj,_pG2[jj]);
      char     _F10 = (char)F10(ii,jj,_pG2[jj]);
      char     _F11 = (char)F11(ii,jj,_pG2[jj]);

      // Case 1
      if (_pG2[jj] <= -55 && _pG2[0] <= -60)
      {
         NEXT = (char)(SUM - _F1);
      }
      // Case 2
      else if ((_pG2[jj] > 70) && (PREV % 2))
      {
         NEXT = (char)(SUM - _F2);
      }
      // Case 3
      else if ((_pG2[jj] > 70) && !(PREV % 2))
      {
         NEXT = (char)(SUM - _F3);
      }
      // Case 4
      else if ((_pG2[1] >= 120 || _pG2[jj] < 10) && (PREV % 2))
      {
         NEXT = (char)(SUM - _F4);
      }
      // Case 5
      else if ((_pG2[1] >= 120 || _pG2[jj] < 10) && !(PREV % 2))
      {
         NEXT = (char)(SUM - _F5);
      }
      // Case 6
      else if ((_pG2[jj] < 50 || _pG2[1] <= -3) && (PREV % 2))
      {
         NEXT = (char)(SUM - _F6);
      }
      // Case 7
      else if ((_pG2[jj] < 50 || _pG2[1] <= -3) && !(PREV % 2))
      {
         NEXT = (char)(SUM - _F7);
      }
      // Case 8
      else if (PREV % 2)
      {
         NEXT = (char)(DIF - _F8);
      }
      // Case 9
      else
      {
         NEXT = (char)(NEXT - randminmax(PREV,_F10,_F11) - _F9);
      }
   }


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

Дешифрования выполняется зеркально.

   _SS = JUNK_BOY_AGE;

   // Update 1
   for (ii = 0; _pK[ii]; ++ii)
   {
      _SS += _pK[ii];

      _pG1[jj] = (char)(_pK[ii] + _SS + jj++);
      _pG1[jj] = (char)(_pK[ii]       + jj++);
   }

   // Update 2
   for (ii = 0; ii < iPswSize2; ++ii)
   {
      _pG2[ii] = (char)(_pG1[ii] + _SS);
   }

   BYTE     Keep = _pBuf[0];

   _pBuf[0] = (char)(_pBuf[0] - _pK[0] - _SS);

   // CBC Stream Cipher
   for (ii = 1,jj = 1; ii < (int)_dwSize; ii++,jj++)
   {
      BYTE     Cipher = _pBuf[ii];

      jj %= iPswSize2;

      // Switch emulation
      char     _F1  = (char)F1 (ii,jj,_pG2[jj]);
      char     _F2  = (char)F2 (ii,jj,_pG2[jj]);
      char     _F3  = (char)F3 (ii,jj,_pG2[jj]);
      char     _F4  = (char)F4 (ii,jj,_pG2[jj]);
      char     _F5  = (char)F5 (ii,jj,_pG2[jj]);
      char     _F6  = (char)F6 (ii,jj,_pG2[jj]);
      char     _F7  = (char)F7 (ii,jj,_pG2[jj]);
      char     _F8  = (char)F8 (ii,jj,_pG2[jj]);
      char     _F9  = (char)F9 (ii,jj,_pG2[jj]);
      char     _F10 = (char)F10(ii,jj,_pG2[jj]);
      char     _F11 = (char)F11(ii,jj,_pG2[jj]);

      // Case 1
      if (_pG2[jj] <= -55 && _pG2[0] <= -60)
      {
         NEXT = (char)(IDIF + _F1);
      }
      // Case 2
      else if ((_pG2[jj] > 70) && (KEEP % 2))
      {
         NEXT = (char)(IDIF + _F2);
      }
      // Case 3
      else if ((_pG2[jj] > 70) && !(KEEP % 2))
      {
         NEXT = (char)(IDIF + _F3);
      }
      // Case 4
      else if ((_pG2[1] >= 120 || _pG2[jj] < 10) && (KEEP % 2))
      {
         NEXT = (char)(IDIF + _F4);
      }
      // Case 5
      else if ((_pG2[1] >= 120 || _pG2[jj] < 10) && !(KEEP % 2))
      {
         NEXT = (char)(IDIF + _F5);
      }
      // Case 6
      else if ((_pG2[jj] < 50 || _pG2[1] <= -3) && (KEEP % 2))
      {
         NEXT = (char)(IDIF + _F6);
      }
      // Case 7
      else if ((_pG2[jj] < 50 || _pG2[1] <= -3) && !(KEEP % 2))
      {
         NEXT = (char)(IDIF + _F7);
      }
      // Case 8
      else if (KEEP % 2)
      {
         NEXT = (char)(ISUM + _F8);
      }
      // Case 9
      else
      {
         NEXT = (char)(NEXT + randminmax(KEEP,_F10,_F11) + _F9);
      }

      Keep = Cipher;
   }


Атака:
------

Из приведенных фрагментов очевидно, что для дешифровки достаточно только
знания гаммы G2. Нужная функция F1..F11 будет применена автоматически.

Знание того, что зашифрованный файл является документом M$Word, дает нам около
40 известных байт в начале файла - при длине пароля 8 символов (то есть, 16
символах гаммы), этого более чем достаточно для атаки.

Для начала, "выпишем" в две колонки 33 байта исходного и зашифрованного
текста, и для каждой строчки найдем все допустимые значения гаммы G2,
переводящие одно в другое.

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


Brute force
-----------
по всему диапазону допустимых значений для гаммы G2 (0..255) для блока
размером PASSWORD_LENGTH * 2 (не включая самый первый символ файла)

   BYTE     pGamma0[MAX_PASSWORD_SIZE_2][ASCII_SIZE + 1];
   BYTE     pGamma1[MAX_PASSWORD_SIZE_2][ASCII_SIZE + 1];
   BYTE     pGamma2[MAX_PASSWORD_SIZE_2][ASCII_SIZE + 1];

   memset(pGamma0,0,MAX_PASSWORD_SIZE_2 * (ASCII_SIZE + 1));
   memset(pGamma1,0,MAX_PASSWORD_SIZE_2 * (ASCII_SIZE + 1));
   memset(pGamma2,0,MAX_PASSWORD_SIZE_2 * (ASCII_SIZE + 1));

   FetchCandidates((BYTE*)pGamma1, 1,iPswSize2);

Фрагмент процедуры FetchCandidates()
------------------------------------

   char     Keep = CIPHER_TEXT[iStart - 1];

   for (ii = iStart,jj = iStart; ii < (iStart + iPswSize2); ++ii,++jj)
   {
      char     Cipher = CIPHER_TEXT[ii];

      jj %= iPswSize2;

      for (int kk = 0; kk < ASCII_SIZE; ++kk)
      {
         // Switch emulation
         char     _F1  = (char)F1 (ii,jj,kk);
         char     _F2  = (char)F2 (ii,jj,kk);
         char     _F3  = (char)F3 (ii,jj,kk);
         char     _F4  = (char)F4 (ii,jj,kk);
         char     _F5  = (char)F5 (ii,jj,kk);
         char     _F6  = (char)F6 (ii,jj,kk);
         char     _F7  = (char)F7 (ii,jj,kk);
         char     _F8  = (char)F8 (ii,jj,kk);
         char     _F9  = (char)F9 (ii,jj,kk);
         char     _F10 = (char)F10(ii,jj,kk);
         char     _F11 = (char)F11(ii,jj,kk);

         char     Test = 0;
         //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
         // Case 1
         Test  = (char)((Cipher - Keep) + _F1);
         pList[jj * (ASCII_SIZE + 1) + kk] |= ((Test == PLAIN_TEXT[ii]) && (kk <= -55));
         //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
         // Case 2
         Test = (char)((Cipher - Keep) + _F2);
         pList[jj * (ASCII_SIZE + 1) + kk] |= ((Test == PLAIN_TEXT[ii]) && ((kk > 70) && (Keep % 2)));
         //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
         // Case 3
         Test = (char)((Cipher - Keep) + _F3);
         pList[jj * (ASCII_SIZE + 1) + kk] |= ((Test == PLAIN_TEXT[ii]) && ((kk > 70) && !(Keep % 2)));
         //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
         // Case 4
         Test = (char)((Cipher - Keep) + _F4);
         pList[jj * (ASCII_SIZE + 1) + kk] |= (Test == PLAIN_TEXT[ii]);
         //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
         // Case 5
         Test = (char)((Cipher - Keep) + _F5);
         pList[jj * (ASCII_SIZE + 1) + kk] |= (Test == PLAIN_TEXT[ii]);
         //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
         // Case 6
         Test = (char)((Cipher - Keep) + _F6);
         pList[jj * (ASCII_SIZE + 1) + kk] |= ((Test == PLAIN_TEXT[ii]) && (Keep % 2));
         //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
         // Case 7
         Test = (char)((Cipher - Keep) + _F7);
         pList[jj * (ASCII_SIZE + 1) + kk] |= ((Test == PLAIN_TEXT[ii]) && !(Keep % 2));
         //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
         // Case 8
         Test = (char)((Cipher + Keep) + _F8);
         pList[jj * (ASCII_SIZE + 1) + kk] |= ((Test == PLAIN_TEXT[ii]) && (Keep % 2));
         //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
         // Case 9
         Test = (char)(Cipher + randminmax(Keep,_F10,_F11) + _F9);
         pList[jj * (ASCII_SIZE + 1) + kk] |= (Test == PLAIN_TEXT[ii]);
         //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
      }

      Keep = Cipher;
   }

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

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

   FetchCandidates((BYTE*)pGamma2,iPswSize2 + 1,iPswSize2);

Вычеркнем все несовпадающие значения из обоих списков:

   // Intersection
   int      iMaxCnt = 0;

   int      ii = 0;
   int      jj = 0;

   for (ii = 0; ii < iPswSize2; ++ii)
   {
      for (jj = 0; jj < ASCII_SIZE; ++jj)
      {
         pGamma0[ii][jj] = pGamma1[ii][jj] && pGamma2[ii][jj];

         if (pGamma0[ii][jj])
         {
            ++pGamma0[ii][ASCII_SIZE];
         }
      }

      iMaxCnt = max(iMaxCnt,pGamma0[ii][ASCII_SIZE]);
   }

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

В силу ограниченности полученного пространства ключей, несложен его прямой
перебор.

         ПРИМЕР:
         -------

         Пусть, размер гаммы 16 = 2^4 и в каждой строке не более 4 = 2^2
         вариантов. Тогда пространство ключей не более чем 16^4 = 2^16 !

Для перебора всех возможных вариантов сочетаний гаммы, создадим итератор,
"знающий" о количестве вариантов в каждой строке и обеспечивающий
последовательный перебор всех значений.

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

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


   int      iMxSize = (iMaxCnt + 1) * iPswSize2;

   BYTE*    pKeyMatrix = new BYTE[iMxSize];

   memset(pKeyMatrix,0,iMxSize);

   BYTE     pMxIterator[MAX_PASSWORD_SIZE_2];

   memset(pMxIterator,0,sizeof(pMxIterator));

   for (ii = 0; ii < iPswSize2; ++ii)
   {
      for (jj = 0; jj < ASCII_SIZE; ++jj)
      {
         if (pGamma0[ii][jj])
         {
            pKeyMatrix[ii * (iMaxCnt + 1) + 1 + pKeyMatrix[ii * (iMaxCnt + 1)]] = (BYTE)jj;
            ++pKeyMatrix[ii * (iMaxCnt + 1)];
         }
      }
   }

   bool     bFinished = false;
   bool     bFound    = false;

   while (!bFinished)
   {
      // Set Gamma to current set
      for (ii = 0; ii < iPswSize2; ++ii)
      {
         _pG2[ii] = pKeyMatrix[ii * (iMaxCnt + 1) + 1 + pMxIterator[ii]];
      }

      // Do Decode
      if (GammaTest(iPswSize2,iPswSize2 * 2 + 1))
      {
         bFound = true;
         break;
      }

      // Try next combination
      bool     bCarry = false;

      for (int ii = 0; ii < iPswSize2; ++ii)
      {
         ++pMxIterator[ii];

         if (!pKeyMatrix[ii * (iMaxCnt + 1)])
         {
            // Fool Proof
            continue;
         }

         pMxIterator[ii] %= pKeyMatrix[ii * (iMaxCnt + 1)];

         bCarry = pMxIterator[ii] == 0;

         if (!bCarry)
         {
            break;
         }
         else
         {
            if (ii == (iPswSize2 - 1))
            {
               // Nothing found
               bFinished = true;
            }
         }
      }
   }


GammaTest() просто декодирует блок текста, используя текущую гамму и
сравнивает результат с исходным текстом. При совпадении, считаем, что мы нашли
искомый вектор гаммы G2.

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

Займемся его восстановлением.

Для этого необходимо просто реверсировать вычисление гаммы G2. Именно это и
было причиной, по которой я разбил вычисление гаммы на две фазы - так удобнее
восстанавливать пароль.

Вот исходная процедура:
-----------------------

   // Инициализируем вектор
   _SS = JUNK_BOY_AGE;

   // Update 1
   // K[i] - Очередной символ ключа
   // G[i] - Гамма, используемая при шифровании
   // Для собственного удобства я разделил 1-ую и 2-ую фазы создания
   // гаммы
   for (ii = 0; _pK[ii]; ++ii)
   {
      _SS += _pK[ii];

      _pG1[jj] = (char)(_pK[ii] + _SS + jj++);
      _pG1[jj] = (char)(_pK[ii]       + jj++);
   }

   // Update 2
   // Полученная на первом этапе гамма модифицируется
   // Сейчас, _SS - сумма всех символов пароля
   for (ii = 0; ii < iPswSize2; ++ii)
   {
      _pG2[ii] = (char)(_pG1[ii] + _SS);
   }

А вот обратная к ней:
---------------------

   // Recover password
   BYTE     SS_Last = (BYTE)(_pG2[iPswSize2 - 2] - _pG2[iPswSize2 - 1] + 1);

   // Вычисляем  G1 по G2
   for (ii = 0; ii < iPswSize2; ++ii)
   {
      _pG1[ii] = (char)(_pG2[ii] - SS_Last);
   }

   // Вычисляем  K по G1
   for (ii = 0, jj = 0; ii < (iPswSize2 / 2); ++ii)
   {
      _pK[ii] = (char)(_pG1[++jj] - jj++);
   }

Осталось вывести результат и потребовавшееся для подбора время (на моем P4 2.4
GHz - менее 1 миллисекунды).


Эпилог:
-------

Если что-то еще осталось неясным, пройдите сомнительное место в отладчике -
полный исходный код и скомпилированное приложение (а также весь авторский
материал) находятся в эташе.

Crypto Challenge I 180,680
Crypto Challenge II 235,054
Encoder 23,154
Cracker 43,061
-- gazlan <gazlan@yandex.ru>

© Gazlan 2009 * gazlan@yandex.ru
Сайт управляется системой uCoz